Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Se citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările mulţimii {1,2,..,n}. Date de intrare Fişierul de intrare permutari.in conţine pe prima linie numărul n. Date de ieşire Fişierul de ieşire permutari.out va conţine pe fiecare linie elementele unei permutări, separate prin câte un spaţiu. Restricţii şi precizări 0 < n < 9 Exemplu permutari.in 3 permutari.out 1 … Read more
Se consideră o tablă de șah de dimensiune n. Să se plaseze pe tablă n regine astfel încât să nu existe două regine care să se atace. Date de intrare Programul citește de la tastatură numărul n. Date de ieșire Programul va afișa pe ecran o singură configurație validă a tablei de șah. Ea va fi alcătuită din n linii cu … Read more
Se dă o tablă de șah formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. În zona de coordonate 1 1 se află un cal care se poate deplasa pe tablă în L, ca la șah, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori … 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