InformaticăbacalaureatClasa 11dificil
Backtracking în C++ - Algoritm și Probleme Rezolvate
Învață tehnica backtracking: permutări, combinări, problema reginelor, labirint - cu cod și explicații.
27 zile în urmă
0 vizualizări
50 minute
Backtracking în C++
Ce este Backtracking?
Backtracking = tehnică de rezolvare a problemelor prin încercare și revenire.
Principiu: construim soluția pas cu pas, și când ajungem într-un punct mort, revenim (back) și încercăm altă variantă.
Structura Generală
1void backtrack(int pas) { 2 if (pas == n) { 3 // Afișăm soluția 4 return; 5 } 6 7 for (fiecare valoare posibilă v) { 8 if (esteValid(v)) { 9 solutie[pas] = v; 10 backtrack(pas + 1); 11 // revenire automată 12 } 13 } 14}
Problema 1: Permutări
Generează toate permutările de n elemente.
1#include <iostream> 2using namespace std; 3 4int n, sol[20]; 5bool folosit[20]; 6 7void afiseaza() { 8 for (int i = 0; i < n; i++) 9 cout << sol[i] << " "; 10 cout << endl; 11} 12 13void permutari(int pas) { 14 if (pas == n) { 15 afiseaza(); 16 return; 17 } 18 19 for (int i = 1; i <= n; i++) { 20 if (!folosit[i]) { 21 sol[pas] = i; 22 folosit[i] = true; 23 permutari(pas + 1); 24 folosit[i] = false; 25 } 26 } 27} 28 29int main() { 30 cin >> n; 31 permutari(0); 32 return 0; 33}
Problema 2: Combinări
Generează toate combinările de n elemente luate câte k.
1int n, k, sol[20]; 2 3void combinari(int pas, int start) { 4 if (pas == k) { 5 for (int i = 0; i < k; i++) 6 cout << sol[i] << " "; 7 cout << endl; 8 return; 9 } 10 11 for (int i = start; i <= n; i++) { 12 sol[pas] = i; 13 combinari(pas + 1, i + 1); 14 } 15} 16 17// Apel: combinari(0, 1);
Problema 3: Problema Reginelor
Plasează n regine pe o tablă n×n fără să se atace.
1int n, col[20]; 2 3bool esteValid(int linie, int coloana) { 4 for (int i = 0; i < linie; i++) { 5 // Verifică coloana 6 if (col[i] == coloana) return false; 7 // Verifică diagonalele 8 if (abs(col[i] - coloana) == abs(i - linie)) return false; 9 } 10 return true; 11} 12 13void regine(int linie) { 14 if (linie == n) { 15 // Afișează soluția 16 for (int i = 0; i < n; i++) 17 cout << col[i] + 1 << " "; 18 cout << endl; 19 return; 20 } 21 22 for (int j = 0; j < n; j++) { 23 if (esteValid(linie, j)) { 24 col[linie] = j; 25 regine(linie + 1); 26 } 27 } 28}
Când să folosești Backtracking?
- •Generare permutări/combinări/aranjamente
- •Probleme de optimizare cu spațiu mic
- •Căutare în labirint
- •Jocuri (Sudoku, N-regine)
- •Când nu există altă metodă mai eficientă
Exerciții BAC/Olimpiadă
- •Generează toate submulțimile unei mulțimi
- •Problema labirintului (găsește drumul)
- •Partiționarea unui număr în sumă de numere
Găsește un profesor de informatică pentru pregătire BAC/Olimpiadă!
Tutorialul te-a ajutat?
Dacă ai nevoie de ajutor personalizat, găsește un profesor calificat pentru meditații
