Clasa a XI-a Unitatea de nvare: Backtracking

Cu ct este mai dificil problema,

cu att mai mulumit vei fi cnd o vei rezolvaFi de lucru nr.1

a. Completati spatiile libere:

1. Se cere determinarea tuturor modalitilor distincte de aezare n linie a tuturor celor n sportivi

aflai la o festivitate de premiere. Problema este echivalent cu generarea:_________________

______________________________________________________________________________

2. Metoda Backtracking const n efectuarea unor _____________________________, n

vederea gsirii soluiilor, ____________________________________________n caz de esec.

3. Condiiile de continuare deriv din ________________________.

4. Algoritmii cu revenire (algoritmi de tip backtracking) se aplic problemelor care

ndeplinesc simultan urmtoarele condiii:

soluia lor poate fi pus sub forma--------------------------------------___________________________________________

__________________________________________________________, iar elementele lor se consider c se afl ntr-o relaie de ordine bine stabilit;

nu se dispune de o alt metod de rezolvare, mai rapid; __________________________pot fi la rndul lor vectori; A1, A2 , An pot coincide.

b. Alegeti varianta corecta de raspuns:

1.Daca pentu nivelul k oarecare al vectorului solutie am verificat toate valorile posibile:a) algoritmul se incheie;b) se revine pe nivelul anterior;c) se trece pe nivelul urmator;2.Dupa ce s-a gasit o valoare convenabila pentu componenta k,urmatorul pas este:a) se trece la componenta urmatoare,k+1;b) se ramane la componenta k,cautand in continuare o alta valoare convenabila;c) se revine la componenta k-1.3.In ce conditii se revine la componenta anterioara?a) dupa ce am gasit o valoare convenabila pentru componenta k;b) daca valoarea testata pentru componenta k nu convine;c) daca am testat toate valorile posibile pentru componenta k.4. In ce conditii se trece de la componenta k la componenta k+1?a) dupa ce am gasit o valoare convenabila pentru componenta k;b) dupa ce am testat toate valorile posibile pentru comp k;c) daca nu am gasit nici o valoare convenabila pentru componenta k 5.Initializarea componentei x[k] se realizeaza:a) cand se trece de pe nivelul k-1 pe nivelul k

b) cand se revine de pe nivelul k+1 pe nivelul kc) cand pe nivelul k+1 au fost testate toate valorile posibile

c. Subprogramul descrie strategia generala Backtracking, explicati in spatiile libere indicate

mecanismul functionarii metodei.

void back (){k=1; init(); while (k>0 {as=1;ev=0; while (as && !ev) {as=succesor(); if (as) ev=valid();

} if (as) if (solutie()) tipar(); else {k++;

init();} else k--; } }