11Abacktracking

O clasă de 28 de elevi este la ora de educaţie fizică şi profesorul doreşte să formeze o

echipă de 4 elevi; ordinea elevilor în cadrul echipei nu are importanţă. Algoritmul de

generare a tuturor posibilităţilor de a forma o asfel de echipă este similar cu algoritmul de

generare a tuturor:

Folosind un algoritm de generare putem obţine numere naturale de k cifre care au suma

cifrelor egală cu un număr natural s. Astfel, pentru valorile k=2 şi s=6 se generează, în

ordine, numerele: 15, 24, 33, 42, 51, 60. Care va fi al treilea număr generat pentru k=4 şi

s=5?

Generarea tuturor şirurilor de caractere de 5 litere, fiecare literă putând fi orice element din

mulţimea {p,r,o,b,a}, se realizează cu ajutorul unui algoritm echivalent cu algoritmul de

generare a:

1. Utilizând metoda bactracking se generează toate submulţimile cu cel mult patru instrumente muzicale din mulţimea {clarinet, corn, flaut, oboi, saxofon}. Primele șase soluţii generate sunt, în această ordine: {clarinet}, {clarinet, corn}, {clarinet, corn, flaut}, {clarinet, corn, flaut, oboi}, {clarinet, corn, flaut, saxofon}, {clarinet, corn, oboi}. Cea de a opta soluţie este:

1. Utilizând metoda backtracking, se generează toate drapelele formate din câte 3 culori distincte din mulţimea {alb, galben, negru, roșu, verde}. Două drapele sunt distincte dacă diferă prin cel puțin o culoare sau prin ordinea culorilor. Primele patru soluţii obţinute sunt, în această ordine: (alb, galben, negru), (alb, galben, roșu), (alb, galben, verde) şi (alb, negru, galben). Indicaţi soluția generată imediat înainte de (galben, verde, alb).

1. Utilizând metoda backtracking se generează toate variantele prin care patru persoane pot plăti o consumație totală de 200 de lei în următoarele condiții: • fiecare plătește o sumă nenulă, divizibilă cu 10; • primul plătește mai mult decât al doilea, al doilea mai mult decât al treilea, iar acesta mai mult decât al patrulea. O soluție constă în patru valori, reprezentând, în ordine, sumele plătite de fiecare dintre cele patru persoane. Primele patru soluții generate sunt, în această ordine: (70, 60, 40, 30), (70, 60, 50, 20), (80, 50, 40, 30), (80, 60, 40, 20). Indicați cea de a șasea soluție, în ordinea generării acestora.

1. Având la dispoziție cinci tipuri de prăjituri, cu caise, cu căpșune, cu prune, cu piersici, respectiv cu cireșe, se utilizează metoda backtracking pentru a obține toate posibilitățile de a forma platouri cu câte trei tipuri de prăjituri diferite, știind că în cadrul unui platou nu contează ordinea de așezare a prăjiturilor și că prăjiturile cu căpșune nu vor fi plasate pe același platou cu prăjiturile cu piersici. Primele patru soluții obținute sunt, în această ordine: (caise, căpșune, prune), (caise, căpșune, cireșe), (caise, prune, piersici), (caise, prune, cireșe). A șasea soluție generate este: