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}

problema damelor

Problema damelor

Considerandu-se o tabla de sah de dimansiune nXn, sa se determine toate modalitatile de amplasare a n regine pe tabla de sah astfel incat sa nu se atace doua cate doua(doua regine se ataca daca se afla pe aceeasi linie, coloana, sau diagonala).

 

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

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]  || abs(st[k]-st[i])==abs(k-i)) 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–;
}
}

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

{module orizontal600}

{joscommentenable}

 

SECVENTE LITERE

Scrieti un program care afiseaza pe ecran toate secventele de n litere (n numar natural par citit de la tastatura) din multimea {A,R,G,V), secvente care se pot construi respectand urmatoarele reguli: nu plasam doua litere identice una langa alta;trebuie sa utilizam exact n/2 litere R

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

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

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

int valid()
{int i,nr;

if(k>1)  if(st[k]==st[k-1]) return 0;
if(k==n)

{nr=0; for(i=1;i<=n;i++) if(a[st[i]]==’R’) return 0;}

return 1;}

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

void tipar()
{for(int i=1;i<=n;i++) cout<<a[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;
a[1]=’A’;a[2]=’R’;a[3]=’G’;a[4]=’V’;
bkt();
}

{joscommentenable}