11Abacktracking

Utilizând metoda backtracking se generează toate permutările mulţimii {1,2,3,4}. Dacă

primele trei permutări generate sunt, în acestă ordine: 1234, 1243, 1324 precizaţi care

este permutarea generată imediat după 3412.

• 3421

• 3413

• 4123

• 3214

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:

• aranjamentelor de 28 de elemente luate câte 4

• combinărilor de 28 de elemente luate câte 4

• partiţiilor unei mulţimi cu 28 de elemente

• elementelor produsului cartezian AxAxAxA, A fiind o mulţime cu 28 de elemente

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?

• 1301

• 1022

• 2201

• 1031

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:

• aranjamentelor

• permutărilor

• submulţimilor

• produsului cartezian

Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca

sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine

crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3,

1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea

lui 9. Care este penultima soluţie?

• 3+3+3

• 3+6

• 4+5

• 2+7

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:

• {corn}

• {clarinet, flaut}

• {clarinet, corn, saxofon}

• {clarinet, corn, oboi, saxofon}

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).

• (negru, roșu, verde)

• (negru, alb, galben)

• (galben, verde, roșu)

• (galben, roșu, verde)

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.

• (80,60,45,15)

• (80,60,50,10)

• (80,70,30,20)

• (80,70,40,10)

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:

• {caise, prune, căpșune}

• {caise, piersici, cireșe }

• {căpșune, prune, cireșe}

• {prune, piersici, cireșe}