Informatică Programare
Exercitii rezolvate backtracking C++
Backtracking-ul în C++ este o tehnică de programare care explorează toate soluțiile posibile ale unei probleme prin încercare și revenire. Este folosit pentru probleme combinatorii ca generarea permutărilor sau rezolvarea Sudoku. Vom rezolva două exerciții tipice pas cu pas.
Exercițiu 1: Generarea permutărilor de n elemente
- 1 Pasul 1: Definirea funcției backtracking Creăm o funcție recursivă care primește un vector pentru soluție și unul pentru elementele folosite. Exemplu: void backtrack(vector<int>& sol, vector<bool>& used, int n).
- 2 Pasul 2: Condiția de oprire Dacă lungimea soluției este n, afișăm permutarea. Altfel, pentru fiecare element de la 1 la n, dacă nu e folosit, îl adăugăm și apelăm recursiv.
- 3 Pasul 3: Revenirea (backtracking) După apelul recursiv, eliminăm ultimul element și marcăm elementul ca nefolosit pentru a încerca alte variante.
Exercițiu 2: Problema reginelor pe tabla de șah
- 1 Pasul 1: Reprezentarea soluției Folosim un vector sol de lungime n, unde sol[i] = coloana reginei de pe linia i. Verificăm atacul pe diagonale.
- 2 Pasul 2: Funcția de validare La fiecare pas, verificăm dacă regina nou plasată nu atacă pe diagonală cele anterioare: abs(sol[i] - sol[k]) != abs(i - k).
- 3 Pasul 3: Implementarea backtracking Parcurgem liniile, încercăm coloanele de la 0 la n-1, validăm și apelăm recursiv pentru linia următoare.
Exersează scriind codul complet pentru aceste exerciții și rulează-l pe un compilator online ca să vezi rezultatele.