backtracking

Prezentare teoretică:

Backtracking - CNAMD

Probleme rezolvate:

1. Generarea permutarilor -

O permutare de n elemente este o aranjare a celor n elemente.
Numărul permutărilor de n elemente este n!.
n! = 1*2*3*...*n
Ex. n=3 => 3! = 6 permutări
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
a. varianta iterativa (cu stiva)
1.b. Generarea permutarilor - varianta recursiva

2. Generarea aranjamentelor:

Numim aranjament de n obiecte luate câte k o submulţime ordonată de k obiecte distincte alese dintre cele n.
Numărul aranjamentelor de n obiecte luate câte k este: A(n,k)=n! / (n-k)!
Ex. n=4, k=2 Submulţimi de 2 elemente ale mulţimii {1,2,3,4}
1 2, 1 3, 1 4, 2 1, 2 3, 2 4, 3 1, 3 2, 3 4, 4 1, 4 2, 4 3
a. varianta iterativa

3. Generarea combinarilor:

Numim combinare de n obiecte luate câte k o submulţime de k obiecte distincte dintre cele n.
Numărul combinărilor de n obiecte luate câte k este: C(n,k) = n! / ((n-k)! * k! ) = A(n,k) / P(k)
a. varianta iterativa

C(n,k) <= A(n,k) <= P(n)
Probleme rezolvate :

Probleme clasice rezolvate prin metoda backtracking de Infoarena:
1. Generarea permutarilor arhiva educationala
2. Generarea combinarilor arhiva educationala
3. Generarea submultimilor arhiva educationala

Probleme backtracking varena
4. Aranjamente
5. Permutari unice
6. Partitiile unei multimi
7. Regine

Probleme de concurs :
1. Permfix
2. Paranteze

3. Jocul Flip
4. Inel solutii
5. Regine2 solutii
6. Dame2
7. Problema damelor arhiva de probleme descrierea solutiei


Probleme backtracking varena


Probleme rezolvate prin metoda Backtracking: Backtracking Infoarena
Probleme din arhiva campion: backtracking