backtracking cifre pare crescatoare

Backtracking cifre pare crescatoare

Folosind metoda backtracking, sa se scrie un program care genereaza toate nr din 3 cifre pare,cifrele strict in ordine crescatoare

#include<iostream.h>
#include<math.h>
int st[20],i,p,v[]={0,2,4,6,8};

int valid(int p)
{
for(i=1;i<p;i++)
if(st[p]<=st[i])return 0;
if(p==1 && st[p]==0)return 0;
return 1;
}

int sol(int p)
{return (p==3);}

void tipar(int p)
{              
int i;
for(i=1;i<=p;i++)
cout<<st[i]<<” “;
cout<<endl;
}

void bkt(int p)
{int val;
for(val=0;val<=4;val++)
{
st[p]=v[val];
if(valid(p))
if (sol(p))
tipar(p);
else bkt(p+1);
}}

void main()
{
bkt(1);
}

problema labirintului backtracking

Problema labirintului backtracking

Se dă un labirint sub formă de matrice de m linii şi n coloane. Fiecare element al matricii reprezintă o cameră. Într-una din camerele labirintului se găseşte un om. Se cere să se afle toate soluţiile ca acel om să iasă din labirint, fără să treacă de două ori prin aceeaşi cameră.Se utilizeaza metoda backtracking.

#include<iostream.h>
#include<fstream.h>

int st[20][20],i,m,n,v[20][20],a[20][20];

void tipar(int k)
{for(i=1;i<=k;i++)
cout<<st[i][1]<<”  “<<st[i][2]<<”      “;
cout<<endl;}
int valid(int k)
{if(v[st[k][1]][st[k][2]]==0)
return 0;
for(i=1;i<k;i++)
if((st[k][1]==st[i][1])&&(st[k][2]==st[i][2]))
return 0;
return 1;
}
int solutie(int k)
{return((st[k][1]==1)||(st[k][1]==m)||(st[k][2]==1)||(st[k][2]==n));}
void bk(int k)
{int val;
for(val=1;val<=4;val++)
{st[k][1]=st[k-1][1]+a[val][1];
st[k][2]=st[k-1][2]+a[val][2];
if(valid(k))
if(solutie(k))
tipar(k);
else
bk(k+1);}}

void main()
{int j,k,r;
fstream f(“labirint.in”,ios::in);
f>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
f>>v[i][j];
for(i=1;i<=4;i++)
for(j=1;j<=2;j++)
f>>a[i][j];
cin>>k;cin>>r;
st[1][1]=k;
st[1][2]=r;
bk(2);}

 

problema calului backtracking

Problema calului backtracking

Fiind dată o tablă de şah de dimensiunea nxn şi un cal în colţul stânga sus al acesteia, se cere să se afişeze toate posibilităţile de mutare a calului astfel încât să treacă o singură dată prin fiecare pătrat al tablei.

#include<iostream.h>
#include<fstream.h>
long st[100][100],vec[20][20],i,n;

int valid(int k)
{if((st[k][1]<1)||(st[k][1]>n)||(st[k][2]<1)||(st[k][2]>n))
return 0;
for(i=1;i<k;i++)
if((st[i][1]==st[k][1])&&(st[i][2]==st[k][2]))
return 0;
return 1;}

int solutie(int k)
{return (k==n*n);}

void tipar(int k)
{for(i=1;i<=k;i++)
cout<<st[i][1]<<” “<<st[i][2]<<”      “;
cout<<endl<<endl;}

void bkt(int k)
{int val;
for(val=1;val<=8;val++)
{st[k][1]=st[k-1][1]+vec[val][1];
st[k][2]=st[k-1][2]+vec[val][2];
if(valid(k))
{if(solutie(k))
tipar(k);
else
bkt(k+1);
}}}
void main()
{int j;
fstream f(“datee.in”,ios::in);
for(i=1;i<=8;i++)
for(j=1;j<=2;j++)
f>>vec[i][j];
cin>>n;
st[1][1]=1;
st[1][2]=1;
bkt(2);}

 

masa rotunda backtracking

Masa rotunda backtracking

masaLa o petrecere sunt invitate un numar de perechi, sot si sotie.Ei trebuie asezati in jurul unei mese rotunde astfel incat membrii aceleasi perechi sa nu fie unul langa altul,dar in acelasi timp fiecare femeie sa aiba vecini doi barbati si fiecare barbat sa aiba vecini doua femei.

Femeile vor avea numere impare iar barbatii numere pare.Perechile vor fi de forma (1,2),(3,4),(5,6) etc

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n;
void init()
{
int j;
st[1]=1;
cout<<“n=”;cin>>n;
for(j=2;j<=n;j++)
st[j]=0;
}

int valid(int p)
{
int i;
for(i=1;i<p;i++)
if(st[i]==st[p]) return 0;
if ((st[p]-st[p-1])%2==0) return 0;
if(st[p]%2==0 && st[p]-st[p-1]==1) return 0;
if(st[p]%2==1 && st[p]-st[p-1]==-1) return 0;
if (p==n && st[p]==2) return 0;
return 1;
}

int sol(int p)
{return (p==n);}

void tipar(int p)
{
int j;
for(j=1;j<=p;j++) cout<<st[j]<<” “;
cout<<endl;
}

void bkt(int p)
{int val;
for(val=2;val<=n;val++)
{
st[p]=val;
if(valid(p))
if (sol(p))
tipar(p);
else bkt(p+1);
}}

void main()
{
init();
bkt(2);
}

suma cifrelor s backtracking

Suma cifrelor s backtracking

Sa se afiseze toat numerele formate din cifre distincte cu proprietatea ca suma cifrelor este s, unde s se citeste de la tastatura.

Sa se folosesca metoda backtracking.

#include<iostream.h>
#include<conio.h>
int st[20],n,k,s,c;

void init(int k)
{st[k]=-1;}

int succesor(int k)
{if((st[k]<9)&&(st[k]<s))
{st[k]++;
return 1;
}
else return 0;}

int valid(int k)
{int suma=0;
for(int i=1;i<k;i++)
if(st[k]==st[i]) return 0;
for(i=1;i<=k;i++) suma=suma+st[i];
if(suma>s) return 0;
if((k==1)&&(st[k]==0)) return 0;
return 1;}

int sol(int k)
{int suma=0;
for(int i=1;i<=k;i++)suma=suma+st[i];
return(suma==s);}

void tipar(int k)
{
//c++;cout<<“solutia”<<c<<“: “;
for(int i=1;i<=k;i++) cout<<st[i];
cout<<endl;
//if(c%20==0) {cout<<“enter”;getch();}
}

void bkt()
{int as,k=1;
init(k);
while(k>0)
{
do{} while((as=succesor(k)) && !valid(k));
if (as) {
if(sol(k)) tipar(k);
if(st[k]!=0) {k++;init(k);}
else {k++;init(k);}
}
else k–;
}
}

void main()
{cout<<“s=”;cin>>s;
//c=0;
bkt();
getch();
}

PERMUTARI ITERATIV

PERMUTARI ITERATIV metoda backtarcking

PERMUTĂRI. Se citeşte un număr natural n. Să se genereze permutările mulţimi {1, 2, …, n}

 

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,p;

void init()
{st[k]=0;}

int succesor()
{if (st[k]<n)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{for(int i=1;i<k;i++)
if(st[i]==st[k]) return 0;
return 1;}

int sol()
{return (k==n);}

void tipar()
{for(int i=1;i<=n;i++) cout<<st[i];
cout<<endl;
}

void bkt()
{int as;
k=1;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k–;
}
}

void main()
{
cout<<“n=”;cin>>n;
bkt();
}

 

problema comis voiajorului

Problema comis-voiajorului

Un comis voiajor trebuie să viziteze un număr n de oraşe. Iniţial, el se află într-unul dintre ele, notat 1. Comis voiajorul doreşte să nu treacă de două ori prin acelaşi oraş, iar la întoarcere să revină în oraşul din care a plecat. Cunoscând legăturile existente între oraşe, se cere să se tipărească toate drumurile posibile pe care le poate efectua comis voiajorul.Drumurile dintre orase sunt date sub forma unei matrici a[i][j]=1 daca intre orasul i si j exista drum si a[i][j]=0 daca nu exista drum intre orasul i si orasul j.

 

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,a[10][10];

void init()
{st[k]=1;}

int succesor()
{if (st[k]<n)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{if( a[st[k-1]][st[k]]==0) return 0;
for(int i=1;i<k;i++)
if(st[i]==st[k] ) return 0;
if((k==n) && (a[1][st[k]]==0)) return 0;
return 1;}

int sol()
{return (k==n);}

void tipar()
{for(int i=1;i<=n;i++) cout<<st[i]<<” “;
cout<<endl;
}

void bkt()
{int as;k=2;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k–;
}
}

void main()
{cout<<“numarul de orase=”;cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
st[1]=1;
bkt();
}

problema colorarii hartilor

Problema colorarii hartilor

Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari ce au frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata.

 

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k;

void init()
{st[k]=0;}

int succesor()
{if (st[k]<4)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{for(int i=1;i<k;i++)
if(st[i]==st[k] && a[i][k]==1) return 0;
return 1;}

int sol()
{return (k==n);}

void tipar()
{for(int i=1;i<=n;i++) cout<<“tara numarul”<<i<<” culoarea”<<st[i]<<endl;
cout<<endl;
}

void bkt()
{int as;k=1;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k–;
}
}

main()
{cout<<“numarul de tari=”;cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
bkt();
}

{joscommentenable}

JUCARII MOS CRACIUN

Copiii asteapta jucarii de la Mos Craciun. Scrieti un program care determina toate modurile diferite in care ei pot sa fie asezati in lista, astfel incat sa fie vizitati toti copiii si vizitele sa se faca in orinea descrescatoare a numarului de jucarii dorite de fiecare.Se citesc de la tastatura: n, numarul de copii, apoi numele si numarul de jucarii cerut de fiecare dintre cei n copii.Sa se scrie numele copiilor, in ordinea in care vor fi vizitati de Mos Craciun.

Exemplu: pentru datele de intrare: n=4
Dan 2
Cristina 4
Corina 6
Iulia 4
se scriu urmatoarele solutii:
Corina Iulia Cristina Dan
Corina Cristina Iulia Dan

#include<iostream.h>
struct copil{char nume[10]; int jucarii; };
struct copil v[10];
int st[20],n,k;
void init()
{
st[k]=0;
}
int succesor()
{if(st[k]<n)

{st[k]++;return 1;}

return 0;}

int valid()

{int i;

for(i=1;1<k;i++)

if(st[k]==st[i]) return 0;

for(i=1;i<k;i++)

if(v[st[k]].jucarii>v[st[i]].jucarii) return 0;

return 1;}

int solutie()

{int i;

for(i=1;i<=n;i++)

 cout<<v[st[i]].nume<<” “;

cout<<endl;}

void bkt()

{int as;k=1;

init();

while(k>0)

{

do {} while ((as=succesor() && (!valid()));

if (as)

if (solutie()) tipar();

else

{k++; init();}

else k–;

}

}

void main()

{cout<<“n=”;cin>>n;

for(int i=1;i<=n;i++)

{

cout<<“nume”<<i;cin>>v[i].nume;

cout<<“nr de jucarii pentru copilul “<<i;cin>>v[i].jucarii;

}

bkt();

}

cifre distincte pare alaturate

Backtracking cifre distincte pare alaturate

Folosind metoda backtracking, sa se afiseze toate nr din n cifre distincte a.i. sa nu fie 2 cifre pare alaturate

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,p;

int valid(int p)
{if(p==1 && st[p]==0) return 0;
for(int i=1;i<p;i++)
if(st[i]==st[p]) return 0;
if(p>1 && st[p]%2==0 && st[p-1]%2==0) return 0;
return 1;}

int sol(int p)
{return (p==n);}

void tipar(int p)
{for(int i=1;i<=p;i++) cout<<st[i];
cout<<endl;
}

void bkt(int p)
{
int val;
for(val=0;val<=9;val++)
{
st[p]=val;
if(valid(p)) if(sol(p))
tipar(p);
else bkt(p+1);
}
}

void main()
{cout<<“n=”;cin>>n;
bkt(1);
getch();
}

{joscommentenable}