Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Obiective In aceasta lectie, vom explora metoda backtracking in limbajul de programare C++. Vom intelege conceptul de backtracking si cum poate fi aplicat pentru rezolvarea problemelor complexe. Definitie Metoda backtracking este o tehnica de rezolvare a problemelor care implica explorarea sistematica a tuturor solutiilor posibile. Aceasta metoda incepe cu o solutie partiala si o extinde … Read more
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 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 … Read more
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 … Read more
Masa rotunda backtracking La 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 … Read more
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) … Read more
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 … Read more
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ă … Read more
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; … Read more
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 … Read more