Exerciții 18

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:

Generând şirurile de maximum 3 caractere distincte din mulţimea {A,B,C,D,E}, ordonate lexicografic, obţinem succesiv: A, AB, ABC, ABD, … . Ce şir va fi generat imediat după BAE?

Un program citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:

• încep şi se termină cu 0;
• modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.

Astfel, pentru n=5, combinaţiile afişate sunt, în ordine, următoarele: 01010, 01210. Dacă se rulează acest program şi se citeşte pentru n valoarea 7, imediat după combinaţia 0101210 va fi afişată combinaţia:

Generarea tuturor cuvintelor de trei litere mici, nu neapărat distincte, ale alfabetului englez, se poate realiza cu ajutorul unui algoritm echivalent cu cel de generare a:

Având la dispoziţie cifrele 0, 1 şi 2 putem genera, în ordine crescătoare, numere care au suma cifrelor egală cu 2 astfel încât primele 6 numere generate sunt, în această ordine: 2, 11, 20, 101, 110, 200.

Folosind acelaşi algoritm se generează numere cu cifrele 0, 1, 2 şi 3 care au suma cifrelor egală cu 4. Care va fi al 7-lea număr din această generare?