Question

Am o nelamurire in legatura cu urmatorul program scris in c++.
In poza este vorba depre, generarea permutarilor folosind metoda backtracking.
Ce nu inteleg este de ce se intoarce 'k' la o valoare anterioara.
Ex:
Daca n = 3, atunci x1[] se va modifica la x1[1], x1[2], x1[3]
x1[1] x1[2] x1[3]
0 0 0 asa arata lista initial la indexurile 1, 2, 3 (celelalte valori din x1 vor
ramane 0).
1 0 0 k = 1;
1 1 0 k = 2;
1 2 0 k = 2;
1 2 1 k = 3;
1 2 2 k = 3;
1 2 3 k = 3; acum se va apela functia Afisare()
bucla din BackRec1 se opreste pentru ca i == n1
dar programul merge mai departe si eu nu inteleg de ce
poate sa imi explice cineva de ce?
asa va arata lista daca continuam
1 3 3 k = 2;
1 3 2 k = 3;
.........................................

Answer 1

Răspuns:

Hai că încerc să iți explic cât mai ușor ca să înțelegi.

Variabila „k” este de fapt nivelul stivei cu care lucrezi. Primele soluții iți sunt logice, așa că voi trece direct la cazul (1,2,3) care este prima soluție generată de algoritmul tău.

Suntem în cazul în care k = 3, după afișarea soluției (1,2,3) se caută în continuare pentru un succesor și nu se respectă condiția pentru că succesorul lui 3 este 4, prin urmare nivelul stivei scade cu o unitate ( k = 2 ). De aici se caută succesor pentru x1[2] (care este 1) și îl face 3, deci avem permutarea (1,3,3). Permutarea aceasta nu respectă condiția de valid care ne impune să nu avem elemente identice în permutare. Prin urmare se reapelează funcția, deci nivelul stivei crește cu o unitate ( BackRec1(k + 1) ).

Funcția se va apela dinou, și se inițializează elementul de pe nivelul 3 cu 1 (x1[3] = 1), deci avem permutarea (1,3,1). Permutarea nu este validă datorită funcției Valid (avem două elemente identice), se caută succesor și îl va inițializa pe x1[3] cu 2, deci avem permutarea (1,3,2), care respectă și condiția de soluție și afișează soluția (1,3,2). După soluția aceasta k va fi 1 și soluția imediat următoare după (1,3,2) este (2,1,3), iar apoi iar se repetă ce am făcut anterior și se obține (2,3,1) ș.a.m.d.

Ca să îți răspund la întrebarea ta mai pe scurt. Nivelul stivei scade ( adică „k” )dacă nu se respectă condiția de Succesor (adică acea structură repetitivă de la 1 la n).

Poate că înțelegi mai bine dacă ai face mai întâi varianta iterativă decât cea recursivă.

În cazul în care mai ai nelămuriri în legătură cu backtracking nu ezita să mă contactezi.

Îți doresc mult succes în continuare!