Imprimă pagina - Metoda backtracking

Titlul: Metoda backtracking
Scris de: Maria Alexandra din Februarie 25, 2014, 15:36:41

Sa se genereze toate numerele prime de n cifre(n<10),formate cu cifrele c1,c2,c3 citite de la tastatura.
Ex: n=4; c1=1; c2=5; c3=3; Solutii: 1151,1153,1511,1553,...

Titlul: RÄƒspuns: Metoda backtracking
Scris de: Radu Szasz din Februarie 25, 2014, 21:54:50

Si unde mai exact nu te-ai descurcat?

Titlul: RÄƒspuns: Metoda backtracking
Scris de: Maria Alexandra din Februarie 25, 2014, 22:20:58

De fapt am scris programul ,dar nu afiseaza nici o solutie.

#include <iostream>

using namespace std;
int st[100],i,n,k,numara=0,c1,c2,c3;
void init()
{
if(k==1)
st[k]=0;
else
st[k]=1;
}
int succesor()
{
if(st[k]<n)
{
st[k]=st[k]+1;
return 1;
}
else
return 0;
}
int valid()
{
if(((st[k]==c1)||(st[k]==c2)||(st[k]==c3)))
return 0;
return 1;
}
int solutie()
{
long x=0,p=1,ok=0;
for(i=1;i<=k;i++)
{
x=x*p+st;
p*=10;
}
for(i=2;i<=x/2 && ok;i++)
if(x%i==0)
ok=0;
return(k==n && ok);
}
void tipar()
{
numara++;
for(i=1;i<=k;i++)
cout<<st<<' ';
cout<<endl;
}
void back()
{
int as,ev;
k=1;
init();
while(k>0)
{
do
{
as=succesor();
if(as)
ev=valid();
}
while(as && (!as || !ev));
if(as)
if(solutie())
tipar();
else
{
k++;
init();
}
else
k--;
}
}
int main()
{
cout<<"dati n:";
cin>>n;
cout<<"dati numerele:";
cin>>c1>>c2>>c3;
back();
cout<<"nr solutii:"<<numara<<endl;
return 0;

}

Titlul: RÄƒspuns: Metoda backtracking
Scris de: Prehari Romica din Februarie 25, 2014, 22:36:17

mi-e greu sa imi dau seama cum faci...
uite o varianta mai simpla:

Cod:

#include<iostream>
#include<math.h>
using namespace std;
long n,x[25],v[4];

int prim(long long nr)
{
    long d;
    for(d=2;d<sqrt(nr);d++)
        if(nr%d==0)
        return 0;
    return 1;
}
int sol (int k)
{
    long long nr=0;
    int i;
    nr=x[1];
    for(i=2;i<=k;i++)
      {nr*=10;
      nr+=x[i];
      }
    if(prim(nr))
        return 1;
    return 0;
}
void print (int i)
{
    int l;
    for (l = 1; l <= i; l++)
        cout<<x[l];
        cout<<endl;

}
void back (int k)
{
    int j;
    for (j = 1; j <= 3; j++)
    {
            x[k] = v[j];
            if(k==n)
            {if(sol(k))
            {
                print(k);
            }}
            else
            back(k+1);
    }
}
int main()
{
  cout<<"n=";cin>>n;
  cout<<"c1=";cin>>v[1];
  cout<<"c2=";cin>>v[2];
  cout<<"c3=";cin>>v[3];

  back(1);
    return 0;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Maria Alexandra din Februarie 25, 2014, 15:36:41