Informatică Programare
Probleme backtracking rezolvate C++
Backtracking este o tehnică algoritmică care explorează toate soluțiile posibile ale unei probleme prin încercări și reveniri. În C++, se implementează folosind funcții recursive care generează combinații sau permutări. Această metodă este utilă pentru probleme de generare sau de căutare exhaustivă.
Probleme rezolvate pas cu pas
- 1 Generarea permutărilor Scrie o funcție recursivă care generează toate permutările unui vector de numere, folosind un vector auxiliar pentru a marca elementele folosite.
- 2 Problema reginelor Plasează n regine pe o tablă de șah de n x n astfel încât să nu se atace, verificând pozițiile pe linii, coloane și diagonale.
- 3 Suma submulțimilor Găsește toate submulțimile unui vector a căror sumă este egală cu o valoare dată, adăugând și eliminând elemente recursiv.
Exemplu numeric: permutări
- Date de intrare Vector v = {1, 2, 3}.
- Soluții generate Permutări: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.
- Cod simplu void backtrack(int k) { if (k == n) afiseaza(); else for (i=0; i<n; i++) if (!folosit[i]) { folosit[i]=1; sol[k]=v[i]; backtrack(k+1); folosit[i]=0; } }
Începe cu probleme simple și urmărește cum funcția revine la stări anterioare pentru a înțelege backtracking-ul.