Teste de informatică pentru liceu, articole C#, C/C++, PHP
Voi considera în acest articol faptul că cititorii cunosc noţiunile teoretice legate de metoda backtracking. Voi prefera implementarea utilizând varianta recursivă a problemelor menţionate.
Problema 1. Se citeşte un număr natural n. Se cere să se afişeze toate permutările mulţimii {1, 2, ..., n}.
Soluţia, ca orice problemă de backtracking liniar, este o stivă. Lungimea stivei este n, iar pe orice nivel al stivei vom depune elementele distincte ale mulţimii {1,2,...,n}. Pentru a evita memorarea într-o soluţie a aceleiaşi valori, utilizăm vectorul viz de lungime n, în care viz[i] = 0 dacă i nu a fost pus încă pe stivă şi viz[i]=1 dacă i este deja pe stivă. Aceasta înseamnă că dacă de exemplu pe stivă am memorat deja valorile 3, 6, 2, atunci în vectorul viz avem viz[3] = 1, viz[6] = 1, viz[2] = 1, restul componentelor fiind 0. Pentru nivelul 4 al stivei vom putea depune acum orice valoare i în care viz[i]=0.
#include<iostream> using namespace std; int a[20], n, viz[20]; void PrintSol() { int i; for (i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n"; } void Back(int top) { int i; if (top == n + 1) PrintSol(); else for (i = 1; i <=n; i++) if (!viz[i]) { viz[i] = 1; a[top] = i; Back(top + 1); viz[i] = 0; } } int main() { cout << "n = "; cin >> n; Back(1); return 0 ; }
Problema 2. Se citeşte un număr natural n. Să se genereze partiţiile mulţimii {1,2,...,n}. O partiţie a unei mulţimi A se defineşte ca fiind un set de mulţimi A1, A2, ..., Ap nevide, distincte două câte două, iar reuniunea celor p mulţimi este A. De exemplu, mulţimea {1,2,3,4,5} are ca partiţie setul {1,3,4}{2,5} sau setul {1,4} {2} {3,5}.
Utilizăm în rezolvare o stivă de lungime n, în care st[i] = j are semnificaţia că elementul i aparţine mulţimii Aj. De exemplu, pentru mulţimea {1,2,3,4,5}, partiţia {1,3,4}{2,5} se memorează astfel: st = (1,2,1,1,2). Ideea va fi în continuare ca la fiecare nivel top al stivei să trebuiască pusă o valoare cuprinsă între 1 şi 1 + maxim(st[i], 1 <= i < top}. De ce această restricţie? Pentru că st = (1,2,1,1,2) este aceeaşi cu st = (1,3,1,1,3). Este memorată aceeaşi partiţie. Îentru aceasta, vom utiliza un vector suplimentar maxim, în care maxim[i] va memora valoarea maximă din subvectorul st[1.. i-1].
#include<iostream> using namespace std; int a[20], n, viz[20], maxim[20]; void PrintSol() { int i, j; for (i = 1; i <= maxim[n]; i++) { cout << "{ "; for (j = 1; j <= n; j++) if (a[j] == i) cout << j << " "; cout << "}"; } cout <<"\n"; } void Back(int top) { int i; if (top == n + 1) PrintSol(); else for (i = 1; i <= maxim[top - 1] + 1; i++) { a[top] = i; maxim[top] = max(maxim[top-1],i); Back(top + 1); } } int main() { cout << "n = "; cin >> n; Back(1); return 0 ; }
Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică