Pentru rezolvarea cărei probleme dintre cele enumerate mai jos se poate utiliza metoda backtracking?
Varianta 1 |
determinarea reuniunii a |
Varianta 2 |
determinarea tuturor divizorilor unui număr din |
Varianta 3 |
determinarea tuturor elementelor mai mici decât |
Varianta 4 |
determinarea tuturor variantelor în care se pot genera steagurile cu |
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:
Varianta 1 |
elementelor produsului cartezian |
Varianta 2 |
submulţimilor cu |
Varianta 3 |
permutărilor mulţimii |
Varianta 4 |
partiţiilor mulţimii |
Problema generării tuturor codurilor formate din exact 4
cifre nenule, cu toate cifrele distincte două câte două, este similară cu generarea tuturor:
Varianta 1 |
aranjamentelor de |
Varianta 2 |
permutărilor elementelor unei mulţimi cu |
Varianta 3 |
elementelor produsului cartezian |
Varianta 4 |
submulţimilor cu |
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:
Varianta 1 |
aranjamentelor de |
Varianta 2 |
combinărilor de |
Varianta 3 |
partiţiilor unei mulţimi cu |
Varianta 4 |
elementelor produsului cartezian |
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:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
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:
Varianta 1 |
elementelor produsului cartezian |
Varianta 2 |
aranjamentelor |
Varianta 3 |
permutărilor |
Varianta 4 |
submulţimilor |
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:
Varianta 1 |
submulţimilor unei mulţimi cu |
Varianta 2 |
produsului cartezian a unor mulţimi de cifre |
Varianta 3 |
aranjamentelor de |
Varianta 4 |
combinărilor de |
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:
Varianta 1 |
elementelor produsului cartezian |
Varianta 2 |
elementelor produsului cartezian |
Varianta 3 |
aranjamentelor de |
Varianta 4 |
combinărilor de |
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
?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
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:
0
;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:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|