Pentru inceput am introdus majoritatea programelor invatate pana acum la backtracking. Site-ul este interzis urmatorilor indivizi: Neacsu VLADut Ramboi IONut Deorece contine elemente cu continut pornographic( pentru ei). Probleme rezolvate prin backtracking. 1.Permutari 2.Aranjamente 3.Combinari 4.Problma celor n dame 5.Produs cartezian 6.Problema colorarii hartilor (1)Problema permutarilor #include <iostream.h> #include <conio.h> int n,k,st[100]; void tipar(){ for(int i=1;i<=n;i++) cout<<st[i]<<' '; cout<<endl;} int e_valid(){ for(int i=1;i<=k-1;i++) if(st[i]==st[k]) return 0; return 1; } int am_succesor(){ if(st[k]<n){st[k]++;return 1;} else return 0; } int solutie(){ return k==n;} void init(){st[k]=0;} void back(){ int as; k=1; init(); while(k>0){ do{}while((as=am_succesor())&&!e_valid()); if(as) if(solutie()) tipar(); else{k++;init();} else k--; } } void main() { clrscr(); cin>>n; back(); getch(); } (2)Problema aranjamentelor #include <iostream.h> #include <conio.h> int n,k,st[100],p; void tipar(){ for(int i=1;i<=p;i++) cout<<st[i]<<' '; cout<<endl;} int e_valid(){ for(int i=1;i<=k-1;i++) if(st[i]==st[k]) return 0; return 1; } int am_succesor(){ if(st[k]<n){st[k]++;return 1;} else return 0; } int solutie(){ return k==p;} void init(){st[k]=0;} void back(){ int as; k=1; init(); while(k>0){ do{}while((as=am_succesor())&&!e_valid()); if(as) if(solutie()) tipar(); else{k++;init();} else k--; } } void main() { clrscr(); cin>>n; cin>>p; back(); getch(); } (3) Problema combinarilor #include <iostream.h> #include <conio.h> int n,k,st[100],p; void tipar(){ for(int i=1;i<=p;i++) cout<<st[i]<<' '; cout<<endl;} int e_valid(){ for(int i=1;i<=k-1;i++) if(st[i]==st[k]) return 0; return 1; } int am_succesor(){ if(st[k]<n-p+k){st[k]++;return 1;} else return 0; } int solutie(){ return k==p;} void init(){ if(st[k]>1) st[k]=st[k-1]; else st[k]=0;} void back(){ int as; k=1; init(); while(k>0){ do{}while((as=am_succesor())&&!e_valid()); if(as) if(solutie()) tipar(); else{k++;init();} else k--; } } void main() { clrscr(); cin>>n; cin>>p; back(); getch(); } (4) Problema celor n dame #include <iostream.h> #include <conio.h> #include <math.h> int n,k,st[100]; void tipar(){ for(int i=1;i<=n;i++) cout<<st[i]<<' '; cout<<endl;} int e_valid(){ for(int i=1;i<=k-1;i++) if(st[i]==st[k] || abs(st[k]-st[i])==abs(k-i))return 0; return 1; } int am_succesor(){ if(st[k]<n){st[k]++;return 1;} else return 0; } int solutie(){ return k==n;} void init(){st[k]=0;} void back(){ int as; k=1; init(); while(k>0){ do{}while((as=am_succesor())&&!e_valid()); if(as) if(solutie()) tipar(); else{k++;init();} else k--; } } void main() { clrscr(); cin>>n; back(); getch(); } (5) Problema produsului cartezian #include <iostream.h> #include <conio.h> int n,k,st[100],a[100]; void tipar(){ for(int i=1;i<=n;i++) cout<<st[i]<<' '; cout<<endl;} int e_valid(){ return 1; } int am_succesor(){ if(st[k]<a[k]){st[k]++;return 1;} else return 0; } int solutie(){ return k==n;} void init(){st[k]=0;} void back(){ int as; k=1; init(); while(k>0){ do{}while((as=am_succesor())&&!e_valid()); if(as) if(solutie()) tipar(); else{k++;init();} else k--; } } void main() { clrscr(); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; back(); getch(); } (6)Problema colorarii hartilor #include <iostream.h> #include <conio.h> int n,k,st[100],a[50][50]; void tipar(){ for(int i=1;i<=n;i++) cout<<"Tara "<<i<<" culoarea "<<st[i]<<' '; cout<<endl;} int e_valid(){ for(int i=1;i<=k-1;i++) if(st[i]==st[k]&&a[i][k]==1) return 0; return 1; } int am_succesor(){ if(st[k]<4){st[k]++;return 1;} else return 0; } int solutie(){ return k==n;} void init(){st[k]=0;} void back(){ int as; k=1; init(); while(k>0){ do{}while((as=am_succesor())&&!e_valid()); if(as) if(solutie()) tipar(); else{k++;init();} else k--; } } void main() { clrscr(); cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i-1;j++){ cout<<"a["<<i<<"]["<<j<<"]="; cin>>a[i][j]; a[j][i]=a[i][j];} back(); getch(); } |