Exerciții

Pentru a genera toate numerele naturale cu exact 4 cifre şi care au cifrele în ordine strict descrescătoare, se poate utiliza un algoritm echivalent cu cel pentru generarea:

Generarea matricelor pătratice de ordinul n, cu elemente 0 şi 1, cu proprietatea că pe fiecare linie şi pe fiecare coloană există un singur element egal cu 1, se poate realiza utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:

Pentru rezolvarea cărei probleme dintre cele enumerate mai jos se poate utiliza metoda backtracking?

La un concurs participă 50 de sportivi împărţiţi în 5 echipe, astfel încât în fiecare echipă să fie câte 10 sportivi. Problema determinării tuturor grupelor de câte 5 sportivi, câte unul din fiecare echipă, este similară cu generarea tuturor:

Problema generării tuturor codurilor formate din exact 4 cifre nenule, cu toate cifrele distincte două câte două, este similară cu generarea tuturor:

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 astfel de echipă este similar cu algoritmul de generare a tuturor:

In timpul procesului de generare a permutărilor mulţimii {1,2,…,n} prin metoda backtracking, în tabloul unidimensional x este plasat un element x[k] (1≤k≤n). Acesta este considerat valid dacă este îndeplinită condiţia:

La examenul de bacalaureat, un elev primeşte un test format dintr-un subiect de tip I, unul de tip II şi unul de tip III. Stiind că pentru fiecare tip de subiect sunt elaborate exact 100 de variante, algoritmul de generare a tuturor posibilităţilor de a forma un test este similar cu algoritmul de generare a:

Algoritmul de generare a tuturor numerelor de 5 cifre nenule, fiecare având cifrele ordonate strict crescător, este echivalent cu algoritmul de generare a:

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 astfel de echipă este similar cu algoritmul de generare a tuturor: