Consolidarea cunostintelor-Metoda Backtracking

Utilizând metoda backtracking se generează,

în ordine crescătoare, toate numerele naturale pare cu trei cifre, cu proprietatea că nu există două cifre egale alăturate și suma cifrelor este 10. Primele cinci numere generate sunt, în această ordine: 136, 154, 172,190, 208.

Al şaselea număr generat este:

• 217

• 226

• 262

• 280

Dacă pe nivelul k (k>1)al stivei am verificat toate valorile posibile, atunci?

• Algoritmul se încheie ;

• Se revine pe nivelul anterior;

• Se trece pe nivelul următor;

Dupa ce s-a găsit o valoare convenabila pentru nivelul k al stivei, următorul pas este:

• Se trece la următorul nivel, k+1 (daca nu s-a ajuns la soluție);

• Se rămâne la nivelul k, căutând in continuare o altă valoare convenabilă;

• Se revine pe nivelul anterior;

In ce condiții se revine la componenta anterioară ?

• După ce s-a găsit o valoare convenabilă pentru nivelul k;

• Dacă valoarea testată pentru componenta k nu convine;

• Dacă nu s-a găsit nicio valoare convenabilă pentru nivelul k;

In ce condiții se trece de la nivelul k la nivelul k+1?

• După ce s-a găsit o valoare convenabilă pentru nivelul k;

• După ce au fost testate toate valorile posibile pentru nivelul k;

• S-au testat toate valorile posibile pentru primul nivel;

Inițializarea componentei x[k] se realizează:

• Când se trece de pe nivelul k-1 pe nivelul k;

• Când se revine de pe nivelul k pe nivelul k-1;

• Când pe nivelul k+1 au fost testate toate valorile posibile;

Algoritmul se încheie dacă:

• stiva este vidă (i.e. k=0);

• S-au testat toate valorile posibile pentru ultimul nivel;

• S-au testat toate valorile posibile pentru primul nivel;

După găsirea unei soluții, pasul următor este:

• Se revine la nivelul anterior;

• Se rămâne pe același nivel, testându-se următoarea valoare disponibilă;

• Se încheie algoritmul;

Pentru a genera submulțimile mulțimii {1,3,5,7,8} se folosește metoda backtracking. Câte soluții(submulțimii) care obligatoriu conțin elementul 3 si nu conțin elementul 7 a generat?

• 8

• 6

• 16

• 7