Metoda backtracking (modele de subiecte)

1. [Cuvinte]
Urmatorul enunt este comun pentru intrebarile i)- iv). “Utilizând metoda
backtracking se generează în ordine lexicografică cuvintele de câte patru
litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale
alăturate. Primele opt cuvinte generate sunt, în ordine: abab, abac, abad,
abba, abbb, abbc, abbd, abbe. “
i) Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e?
a. 9 b. 15 c. 12 d. 20
ii) Care este ultimul cuvânt generat?
a. edcb b. eeee c. edde d. eded
iii) Care este penultimul cuvânt generat?
a. edec b. eded c. edde d. edcb
iv) Care este antepenultimul cuvânt generat?
a. edde b. eddb c. edeb d. edcb
v) Se generează, utilizând metoda bactracking, cuvintele cu exact 3 litere din
mulţimea {a,x,c,f,g}. Dacă primele patru cuvinte generate sunt, în ordine,
aaa, aax, aac, aaf, scrieţi ultimele trei cuvinte care încep cu litera a, în
ordinea în care vor fi generate.
vi) Se utilizează metoda backtracking pentru a genera toate cuvintele
formate din două litere distincte din muţimea {w,x,z,y} astfel încât niciun
cuvânt să nu înceapă cu litera x şi niciun cuvânt să nu conţină litera w lângă
litera z. Cuvintele vor fi generate în ordinea wx, wy, zx, zy, yw, yx, yz.
Folosind aceeaşi metodă se generează toate cuvintele de două litere
distincte din mulţimea {w,x,z,y,t} astfel încât niciun cuvânt să nu înceapă cu
litera x şi niciun cuvânt să nu conţină litera w lângă litera z. Care este a treia
şi a patra soluţie generată?
2. [Combinari]
i) Folosind modelul combinărilor se generează numerele naturale cu câte trei
cifre distincte din mulţimea {1, 2, 3, 7}, numere cu cifrele în ordine strict
crescătoare, obţinându-se, în ordine: 123, 127, 137, 237. Dacă se utilizează
exact aceeaşi tehnică pentru a genera numerele naturale cu patru cifre
distincte din mulţimea {1,2,3,4,5,6,7,8}, câte dintre numerele generate au
prima cifră 2 şi ultima cifră 7?
a. 8 b. 3 c. 4 d. 6
ii) Utilizând metoda backtracking se generează toate submuţimile mulţimii
{3,6,2,5}.
Primele şase submulţimi generate sunt, în ordine: {3}, {3,6}, {3,6,2},
{3,6,2,5},
{3,6,5}, {3,2}. Care sunt, în ordinea obţinerii, ultimele trei submulţimi,
generate după
această regulă?
iii) Folosind modelul combinărilor se generează numerele naturale cu câte
trei cifre distincte din mulţimea {1,2,3,4}, numere cu cifrele în ordine strict
crescătoare, obţinându-se, în ordine: 123, 124, 134, 234. Dacă se utilizează
exact aceeaşi tehnică pentru a genera numerele naturale cu câte patru cifre
distincte din mulţimea {1,2,3,4,5}, câte dintre numerele generate au prima
cifră 1 şi ultima cifră 5?
a. 4 b. 2 c. 6 d. 3
3. [Numere cu trei cifre]
i) Utilizând metoda backtracking sunt generate numerele de 3 cifre, având
toate cifrele distincte şi cu proprietatea că cifrele aflate pe poziţii
consecutive sunt de paritate diferită. Ştiind că primele şase soluţii generate
sunt, în această ordine, 103, 105, 107, 109, 123, 125, care este a zecea
soluţie generată?
a. 145 b. 147 c. 230 d. 149
ii) Utilizând metoda backtracking sunt generate numerele de 3 cifre care au
cifrele în ordine crescătoare, iar cifrele aflate pe poziţii consecutive sunt de
paritate diferită. Ştiind că primele cinci soluţii generate sunt, în această
ordine, 123, 125, 127, 129, 145, care este cel de al 8-lea număr generat?
a. 169 b. 149 c. 167 d. 147
iii) Utilizând metoda backtracking, sunt generate toate numerele de 3 cifre,
astfel încât cifrele sunt în ordine crescătoare, iar cifrele aflate pe poziţii
consecutive sunt de paritate diferită. Ştiind că primele trei soluţii generate
sunt, în această ordine, 123, 125, 127, câte dintre toate numerele generate
au suma cifrelor egală cu 6?
iv) Utilizând metoda backtracking se generează numerele formate din câte 3
cifre distincte din mulţimea {1, 3, 5, 7}. Dacă primele trei numere generate
sunt, în acestă ordine: 135, 137, 153 care este cel de-al patrulea număr
generat?
a. 157 b. 173 c. 315 d. 357
v) Folosind cifrele {1,2,3} se generează, în ordinea crescătoare a valorii,
toate numerele pare formate din trei cifre distincte. Astfel, se obţin în ordine,
numerele: 132, 312. Folosind aceeaşi metodă, se generează numerele pare
formate din patru cifre distincte din mulţimea {1,2,3,4}. Care va fi al 4-lea
număr generat ?
a. 2134 b. 1432 c. 2314 d. 1423
vi) Folosind cifrele {2,3,4} se generează, în ordinea crescătoare a valorii,
toate numerele impare formate din trei cifre distincte. Astfel se obţin, în
ordine, numerele: 243, 423. Folosind aceeaşi metodă, se generează
numerele pare formate din patru cifre distincte din mulţimea {2,3,4,5}. Care
va fi al 5-lea număr generat?
a. 3452 b. 3524 c. 2534 d. 3542
vii) Folosind cifrele {1,2,3} se generează, în ordinea crescătoare a valorii,
toate numerele formate din exact trei cifre, în care cifrele alăturate au valori
consecutive. Astfel se obţin în ordine, numerele: 121, 123, 212, 232, 321 şi
323. Folosind aceeaşi metodă se generează numere de patru cifre din
mulţimea {1, 2, 3, 4} care îndeplinesc aceeaşi condiţie. Care va fi al 5-lea
număr generat?
a. 2121 b. 2123 c. 3121 d. 2323
viii) Folosind cifrele {2,3,4} se generează, în ordinea crescătoare a valorii,
toate numerele pare formate din trei cifre distincte. Astfel se obţin, în ordine,
numerele: 234, 324, 342, 432. Folosind aceeaşi metodă, se generează
numerele impare formate din patru cifre distincte din mulţimea {2,3,4,5}.
Care va fi al 5-lea număr generat?
a. 3425 b. 2543 c. 4235 d. 3245
ix) Folosind cifrele {1,2,3} se generează, în ordinea crescătoare a valorii,
toate numerele impare formate din trei cifre distincte. Astfel se obţin, în
ordine, numerele: 123, 213, 231, 321. Folosind aceeaşi metodă, se
generează numerele impare formate din patru cifre distincte din mulţimea
{1, 2, 3, 4}. Care va fi al 5-lea număr generat ?
a. 2413 b. 1423 c. 2431 d. 3241
4. [Numere de orice lungime]
i) Folosind tehnica backtracking, in timpul pregatirii examenului, ati scris un
program care generează toate numerele de câte n cifre (0<n≤9), cifrele fiind
în ordine strict crescătoare.
a) Dacă n este egal cu 5, câte numere au fost generate de catre program?
__________
b) Pentru n egal cu 5, câte dintre numerele generate au prima cifră 4?
___________
ii) Un algoritm generează în ordine crescătoare toate numerele de n cifre,
folosind doar cifrele 3, 5 şi 7. Dacă pentru n=5, primele 5 soluţii generate
sunt 33333, 33335, 33337, 33353, 33355, precizaţi care sunt ultimele 3
soluţii generate, în ordinea generării. ____________________
iii) Un algoritm generează în ordine descrescătoare toate numerele de 5
cifre, fiecare dintre ele având cifrele în ordine strict crescătoare. Ştiind că
primele 5 soluţii generate sunt 56789, 46789, 45789, 45689, 45679,
precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.
______________________
iv) Un algoritm generează în ordine crescătoare, toate numerele de n cifre
(n<9), cu cifre distincte, care nu au două cifre pare alăturate. Dacă pentru
n=5, primele 5 soluţii generate sunt 10325, 10327, 10329, 10345, 10347,
precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor.
______________________
v) Un algoritm generează în ordine descrescătoare, toate numerele de n cifre
(n<9), cu cifrele în ordine strict crescătoare, care nu au două cifre pare
alăturate. Dacă pentru n=5, primele 5 soluţii generate sunt 56789, 45789,
45679, 45678, 36789, precizaţi care sunt următoarele 3 soluţii generate, în
ordinea obţinerii lor. ______________
vi) Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,
2, 8} se
utilizează un algoritm backtracking care, pentru n=2, generează, în ordine,
numerele
20, 22, 28, 80, 82, 88. Dacă n=4 şi se utilizează acelaşi algoritm, precizaţi
câte numere generate sunt divizibile cu 100?
a. 601 b. 100 c. 6 d. 10
vii) Pentru generarea numerelor cu n cifre formate cu elementele mulţimii
{0, 4, 8} se
utilizează un algoritm backtracking care, pentru n=2, generează, în ordine,
numerele
40, 44, 48, 80, 84, 88. Dacă n=4 şi se utilizează acelaşi algoritm, care este
numărul generat imediat după numărul 4008 ?
a. 4040 b. 4004 c. 4080 d. 8004
viii) Un program generează, în ordine crescătoare, numerele naturale de
exact 5 cifre din mulţimea {1, 2, 3, 4, 5}. Fiecare dintre numerele generate
are cifrele distincte două câte două. Primele 3 numere astfel generate sunt:
12345, 12354, 12435. Care este numărul generat imediat după 12543?
a. 15342 b. 12534 c. 13245 d. 13452
ix) Se generează în ordine crescătoare, toate numerele naturale de 5 cifre
distincte, care se pot forma cu cifrele 2,3,4,5 şi 6. Să se precizeze numărul
generat imediat înaintea şi numărul generat imediat după secvenţa
următoare : 34256, 34265, 34526, 34562:
a. 32645 şi 34625
b. 32654 şi 34655
c. 32654 şi 34625
d. 32645 şi 34655
x) Se generează în ordine crescătoare, toate numerele naturale de 5 cifre
distincte, care se pot forma cu cifrele 5,6,7,8 şi 9. Să se precizeze numărul
generat imediat înaintea şi numărul generat imediat după secvenţa
următoare : 67589,67598,67859,67895.
a. 65987 şi 67958
b. 65978 şi 67988
c. 65978 şi 67958
d. 65987 şi 67988
xi) Se generează în ordine crescătoare toate numerele de exact 4 cifre care
se pot forma cu elementele mulţimii {0, 1, 2, 3, 4}. Primele 8 soluţii
generate sunt, în ordine: 1000, 1001, 1002, 1003, 1004, 1010, 1011, 1012.
Care sunt primele trei numere ce se vor genera imediat după numărul 3443?
a. 4000, 4001, 4002
b. 3444, 4443, 4444
c. 3444, 4444, 4000
d. 3444, 4000, 4001
xii) Se generează în ordine crescătoare toate numerele de 4 cifre, cu cifre
distincte, astfel încât diferenţa în valoare absolută dintre prima şi ultima,
respectiv a doua şi a treia cifră este egală cu 2. Primele 11 soluţii generate
sunt, în ordine: 1023, 1203, 1243, 1423, 1463, 1573, 1643, 1683, 1753,
1793, 1863. Care dintre următoarele numere se va genera imediat înaintea
numărului 9317?
a. 9247 b. 9357 c. 9207 d. 8976
xiii) Se generează în ordine crescătoare toate numerele de 4 cifre, cu cifre
distincte, astfel încât diferenţa în valoare absolută dintre ultimele două cifre
ale fiecărui număr generat este egală cu 2. Primele opt soluţii generate sunt,
în ordine: 1024, 1035, 1042, 1046, 1053, 1057, 1064, 1068. Care dintre
următoarele numere se va genera imediat după numărul 8975?
a. 8979 b. 9013 c. 8957 d. 9024
xiv) Având la dispoziţie cifrele 0, 1 şi 2 se pot genera, în ordine crescătoare,
numere care au suma cifrelor egală cu 2. Astfel, primele 6 soluţii sunt 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?
a. 130 b. 301 c. 220 d. 103
5. [Siruri de biti]
i) Un algoritm de tip backtracking generează, în ordine lexicografică, toate
şirurile de 5 cifre 0 şi 1 cu proprietatea că nu există mai mult de două cifre 0
pe poziţii consecutive. Primele 7 soluţii generate sunt: 00100, 00101, 00110,
00111, 01001, 01010, 01011. Care este a 8-a soluţie generată de acest
algoritm?
a. 01110 b. 01100 c. 01011 d. 01101
ii) Un algoritm generează, în ordine lexicografică, toate şirurile alcătuite din
câte n cifre binare (0 şi 1). Ştiind că pentru n=5, primele 4 soluţii generate
sunt 00000, 00001, 00010, 00011, precizaţi care sunt ultimele 3 soluţii
generate, în ordinea obţinerii lor. _____________________
iii) Un program citeşte o valoare naturală nenulă pentru n şi apoi generează
şi afişează, în ordine crescătoare lexicografic, toate combinaţiile formate din
n cifre care aparţin mulţimii {0,1}. Astfel, pentru n=2, combinaţiile sunt
afişate în următoarea ordine: 00, 01, 10, 11. Dacă se rulează acest program
şi se citeşte pentru n valoarea 9, imediat după combinaţia 011011011 va fi
afişată combinaţia:
a. 011100100 b. 011011100 c. 011011011 d. 011100000
iv) Un program citeşte o valoare naturală nenulă pentru n şi apoi generează
şi afişează, în ordine descrescătoare lexicografic, toate combinaţiile de n
cifre care aparţin mulţimii {0,1}. Astfel, pentru n=2, combinaţiile sunt afişate
în următoarea ordine: 11, 10, 01, 00. Dacă se rulează acest program şi se
citeşte pentru n valoarea 8, imediat după combinaţia 10101000 va fi afişată
combinaţia:
a. 01010111 b. 10100111 c. 01010100 d. 10100100
6. [Secvente de suma data]
i) Pentru a scrie valoarea 10 ca sumă de numere prime se foloseşte metoda
backtracking şi se generează, în această ordine, sumele distincte:
2+2+2+2+2, 2+2+3+3, 2+3+5, 3+7, 5+5. Folosind exact aceeaşi metodă,
se scrie valoarea 9 ca sumă de numere prime. Care sunt primele trei soluţii,
în ordinea generării lor? ______
ii) 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?
a. 1301 b. 1022 c. 2201 d. 1031
iii) Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a
scrie numărul 9 ca sumă a cel puţin două numere naturale nenule distincte.
Termenii descompunerii sunt în ordine strict crescătoare. Soluţiile se
generează în ordinea:
1+2+6, 1+3+5, 1+8, 2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi
metodă pentru scrierea lui 12. Scrieţi, în ordinea generării, toate soluţiile de
forma 2+...
iv) Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a
scrie numărul 9 ca sumă a cel puţin două numere naturale nenule distincte.
Termenii fiecărei sume sunt în ordine strict crescătoare. Soluţiile se
generează în ordinea: 1+2+6, 1+3+5, 1+8, 2+3+4, 2+7, 3+6 şi 4+5. Se
aplică exact aceeaşi metodă pentru scrierea lui 8. Câte soluţii vor fi
generate?
a. 3 b. 4 c. 6 d. 5
v) 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
fiecărei sume 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?
a. 3+3+3 b. 3+6 c. 4+5 d. 2+7
vi) 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
fiecărei sume 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. Câte soluţii de forma
2+... vor fi generate?
a. 2 b. 3 c. 4 d. 5
vii) Utilizând metoda backtracking, se generează numerele naturale formate
din exact 3 cifre şi care au suma cifrelor egală cu 4, în această ordine: 103,
112, 121, 130, 202, 211, 220, 301, 310, 400. Dacă utilizăm acelaşi algoritm
pentru a genera toate numerele de 4 cifre care au suma cifrelor egală cu 7,
precizaţi care este numărul generat imediat după 1222.
a. 1231 b. 1223 c. 1213 d. 1321
ix) Utilizând metoda backtracking pentru afişarea tuturor modalităţilor de
descompunere a unui număr natural ca o sumă de numere naturale nenule,
pentru n=3 se obţin, în ordine, soluţiile: 1+1+1; 1+2; 2+1; 3. Ordinea de
scriere a termenilor dintr-o descompunere este semnificativă. Folosind
aceeaşi metodă pentru n=10, care este soluţia generată imediat după
1+1+3+5?
a. 1+1+4+1+1+1+1 b. 1+1+7+1 c. 1+2+7 d. 1+1+4+4
7. [Permutari]
i) 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:
a. x[k]∉{x[1], x[2], …, x[k-1]} b. x[k]≠x[k-1]
c. x[k]∉{x[1], x[2], …, x[n]} d. x[k]≠x[k-1] şi x[k]≠x[k+1]
ii) Se utilizează un algoritm pentru a genera în ordine lexicografică inversă
toate permutările mulţimii {1,2,3,4,5}. Primele patru permutări generate
sunt: 54321, 54312, 54231, 54213. A cincea permutare este:
a. 53421 b. 54321 c. 54132 d. 54123
iii) 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.
a. 3421 b. 3413 c. 4123 d. 3214
iv) Utilizând metoda backtracking se generează permutările cuvântului info.
Dacă primele trei soluţii generate sunt: fino, fion, fnio care este cea de-a
cincea soluţie?
a. foin b. fnoi c. foni d. ifon
v) Dacă se utilizează metoda backtracking pentru a genera toate permutările
de 4 obiecte şi primele 5 permutări generate sunt, în această ordine, 4 3 2 1,
4 3 1 2, 4 2 3 1, 4 2 1 3, 4 1 3 2, atunci a 6-a permutare este:
a. 3 2 1 4 b. 3 4 2 1 c. 1 4 3 2 d. 4 1 2 3
8. [Recunoasterea mecanismelor enumerative]
i) 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:
a. submulţimilor unei mulţimi cu 5 elemente
b. produsului cartezian a unor mulţimi decifre
c. aranjamentelor de 9 elemente luate câte 5
d. combinărilor de 9 elemente luate câte 5
ii) 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:
a. produsului cartezian
b. combinărilor
c. aranjamentelor
d. permutărilor
iii) Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie
cifrele de la 1 la 9, se poate utilza un algoritm echivalent cu algoritmul de
generare a:
a. permutărilor de 5 elemente
b. submulţimilor mulţimii {1,2,3,4,5,6,7,8,9}
c. combinărilor de 9 elemente luate câte 5
d. aranjamentelor de 9 elemente luate câte 5
iv) 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:
a. aranjamentelor de 4 obiecte luate câte 10
b. combinărilor de 10 obiecte luate câte 4
c. permutărilor a 10 obiecte
d. permutărilor a 4 obiecte
v) 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:
a. combinărilor
b. permutărilor
c. aranjamentelor
d. produsului cartezian
vi) Pentru rezolvarea cărei probleme dintre cele enumerate mai jos se poate
utiliza metoda backtracking ?
a. determinarea reuniunii a 3 mulţimi
b. determinarea tuturor divizorilor unui număr din 3 cifre
c. determinarea tuturor elementelor mai mici decât 30000 din şirul lui
Fibonacci
d. având 3 culori (”roşu”, ”galben”, ”albastru”), determinarea tuturor
variantelor în care se pot genera toate steagurile cu 3 culori având la mijloc
culoarea ”galben”
vii) La un concurs sportiv sunt 5 echipe, iar în fiecare echipă sunt câte 10
elevi. Problema determinării tuturor grupelor de câte 5 elevi, câte unul din
fiecare echipă, este similară cu generarea tuturor:
a. elementelor produsului cartezian AxAxAxAxA, unde A={1,2,…,10}
b. submulţimilor cu 5 elemente ale mulţimii {1,2,…,10}
c. permutărilor mulţimii {1,2,3,4,5}
d. partiţiilor mulţimii {1,2,…,10}
viii) Problema generării tuturor codurilor formate din exact 4 cifre nenule, cu
toate cifrele distincte două câte două, este similară cu generarea tuturor:
a. aranjamentelor de 9 elemente luate câte 4
b. permutărilor elementelor unei mulţimi cu 4 elemente
c. elementelor produsului cartezian AxAxAxA unde A este o mulţime cu 9
elemente
d. submulţimilor cu 4 elemente ale mulţimii {1,2,3,4,5,6,7,8,9}
ix) Cu studentii unei grupe 28 de studenti se doreşte formarea unei echipă
de 4 persoane. Ordinea studentilor î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:
a. aranjamentelor de 28 de elemente luate câte 4
b. combinărilor de 28 de elemente luate câte 4
c. partiţiilor unei mulţimi
d. elementelor produsului cartezian AxAxAxA, A fiind o mulţime cu 28 de
elemente
x) La examenul de licenta, un absolvent 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 50 de variante, algoritmul de generare a tuturor
posibilităţilor de a forma un test este similar cu algoritmul de generare a:
a. elementelor produsului cartezian
b. aranjamentelor
c. permutărilor
d. submulţimilor
xi) Trei studenti vor să înfiinţeze o echipa pentru a participa la un concurs de
informatica formată dintr-un programator PHP, un specialist multimedia şi un
specialist in baze de date. Toţi trei ştiu să cânte atât la PHP, cât şi la
multimedia, şi se pricep cu toţii şi la baze de date. Algoritmul de generare a
tuturor posibilităţilor de a forma echipa este similar cu algoritmul de
generare a:
a. aranjamentelor
b. permutărilor
c. elementelor produsului cartezian
d. submulţimilor
9. [Siruri de caractere]
i) 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 după BAE?
a. BCA
b. CAB
c. BC
d. BEA
ii) Utilizând metoda backtracking se generează toate cuvintele de câte 3
litere din mulţimea {a,b,c}. Dacă primele patru cuvinte generate sunt, în
acestă ordine: aaa, aab, aac, aba, care este cel de-al optulea cuvânt
generat?
a. acb b. acc c. aca d. bca
iii) Se utilizează metoda backtracking pentru a genera toate cuvintele de
câte patru litere distincte din mulţimea {d,a,n,s}. Ştiind că al doilea cuvânt
generat este dans, iar al treilea este dsan, care va fi ultimul cuvânt obţinut?
a. nsad b. snad c. snda d. dans
iv) Se utilizează metoda backtracking pentru a genera toate cuvintele de
câte trei litere distincte din mulţimea {i,n,f,o}. Ştiind că ultimele trei cuvinte
generate sunt, în ordine, ion, inf şi ino, care este cel de-al doilea cuvânt
obţinut?
a. ofn b. ifo c. foi d. nif
v) Se utilizează metoda backtracking pentru a genera toate cuvintele care
conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară
exact o dat într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al
treilea este ionf, care este ultimul cuvânt obţinut?
a. nifo b. ofni c. ofin d. foni
vi) Se utilizează metoda backtracking pentru a genera toate cuvintele care
conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară
exact o dat într-un cuvânt şi literele n şi o să nu se afle pe poziţii vecine.
Ştiind că primul cuvânt generat este info, iar al treilea este nifo care este cel
de-al doilea cuvânt obţinut?
a. iofn b. inof c. ionf d. niof
10 [Numarare …]
i) Câte numere cu exact 3 cifre pot fi construite folosind doar cifre pare?
a. 125 b. 100 c. 64 d. 128
ii) În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocalele
apar pe
poziţii consecutive?
a. 24 b. 6 c. 12 d. 4
iii) Se consideră un număr natural nenul x având exact 8 cifre, distincte două
câte două; printer cifrele sale se găseşte şi cifra 0. Permutând cifrele lui x se
obţin alte numere naturale. Câte dintre numerele obţinute, inclusiv x, au
exact 8 cifre? ______
iv) Utilizând metoda backtracking, se generează în ordine lexicografică toate
anagramele cuvântului caiet ( cuvinte formate din aceleaşi litere, eventual în
altă ordine). Câte cuvinte vor fi generate?
a. 60 b. 100 c. 200 d. 120
v) Se generează, prin metoda backtracking, toate partiţiile mulţimii
A={1,2,3} obţinându-se următoarele soluţii: {1}{2}{3}; {1}{2,3};
{1,3}{2}; {1,2}{3}; {1,2,3}. Se observă că dintre acestea, prima soluţie e
alcătuită din exact trei submulţimi. Dacă se foloseşte aceeaşi metodă pentru
a genera partiţiile mulţimii {1,2,3,4} stabiliţi câte dintre soluţiile generate
vor fi alcătuite din exact trei submulţimi.
a. 3 b. 12 c. 6 d. 5
vi) Se utilizează metoda backtracking pentru a genera toate submulţimile cu
p elemente ale unei mulţimi cu m elemente. Dacă m=7 şi p=4 atunci
numărul de submulţimi generate este:
a. 60 b. 35 c. 5 d. 15
vii) Prin metoda backtracking se generează toate anagramele (cuvintele
obţinute prin permutarea literelor) unui cuvânt dat. Ştiind că se aplică
această metodă pentru cuvântul pescar, precizaţi câte cuvinte se vor genera
astfel încât prima şi ultima literă din fiecare cuvânt generat să fie vocală
(sunt considerate vocale caracterele a, e, i , o, u)?
a. 96 b. 24 c. 48 d. 12
viii) În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocala ‘I’
apare pe prima poziţie?
a. 1 b. 24 c. 6 d. 12
11. [Probleme diverse]
i) 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:
- conţin doar valori pozitive sau nule;
- î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 executa acest program şi se citeşte pentru n valoarea 7,
imediat după combinaţia 0101210 va fi afişată combinaţia:
a. 0121210 b. 0123210 c. 0111210 d. 0121010
ii) Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,
2, 8} se
utilizează un algoritm backtracking care, pentru n=2, generează, în ordine,
numerele
20,22,28,80,82,88. Dacă n=4 şi se utilizează acelaşi algoritm, care este
numărul generat imediat după numărul 2008 ?
a. 2002 b. 2020 c. 2080 d. 8002
iii) 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 ?
a. 103 b. 301 c. 220 d. 130
iv) Completarea unui bilet de LOTO presupune colorarea a 6 numere dintre
cele 49, înscrise pe bilet. O situaţie statistică pe o anumită perioadă de timp
arată că cele mai frecvente numere care au fost extrase la LOTO sunt: 2, 20,
18, 38, 36, 42, 46, 48. Câte
bilete de 6 numere se pot completa folosind doar aceste valori, ştiind că
numărul 42 va fi colorat pe fiecare bilet?
a. 21 b. 6! c. 42 d. 56
v) Se generează prin metoda backtracking mulţimile distincte ale căror
elemente sunt numere naturale nenule şi care au proprietatea că suma
elementelor fiecărei mulţimi este egală cu 7. Astfel, sunt generate, în
această ordine, mulţimile: {1, 2, 4}, {1, 6}, {2, 5}, {3, 4}, {7}. Folosind
aceeaşi metodă pentru a genera mulţimile distincte ale căror elemente sunt
numere naturale nenule şi care au proprietatea că suma elementelor fiecărei
mulţimi este egală cu 9, stabiliţi în ce ordine sunt generate următoarele
mulţimi: M1={2, 3, 4}; M2={3, 6}; M3={2, 7}; M4={4, 5}.
vi) Se generează în ordine strict crescătoare numerele de câte şase cifre care
conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se
obţin, în această ordine, numerele: 122333, 123233, 123323, …, 333221.
Câte numere generate prin această metodă au prima cifră 1 şi ultima cifră 2?
________________
vii) Se generează în ordine strict crescătoare toate numerele de câte şase
cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei
ori. Se obţin, în această ordine, numerele: 122333, 123233, 123323, …,
333221. Ce număr se generează imediat după 332312?
viii) Utilizând metoda backtracking se generează în ordine lexicografică toate
anagramele cuvântului caiet ( cuvinte formate din aceleaşi litere, eventual în
altă ordine). Care este a şasea soluţie?
a. catei
b. actie
c. actei
d. catie
ix) Utilizând metoda backtracking se generează toate matricele pătratice de
ordinul 4 ale căror elemente aparţin mulţimii {0,1}, cu proprietatea că pe
fiecare linie şi pe fiecare coloană există o singură valoare 1. Primele 3 soluţii
generate sunt, în această ordine:
1000
0100
0010
0001
1000
0100
0001
0010
1000
0010
0100
0001
Care este penultima soluţie?
a.
0001
0010
1000
0100
b.
0100
1000
0010
0001
c.
0001
0100
0010
1000
d.
0010
1000
0100
0001
x) Se generează, prin metoda backtracking, toate modalităţile de aşezare a
numerelor naturale de la 1 la 5, astfel încât oricare 2 numere consecutive să
nu se afle pe poziţii alăturate. Dacă primele două soluţii sunt: (1,3,5,2,4) şi
(1,4,2,5,3), care este prima soluţie generată în care primul număr este 4?
a. (4, 1, 3, 2, 5) b. (4, 2, 5, 1, 3) c. (4, 3, 5, 3, 1) d. (4, 1, 3, 5, 2)
xi) Se generează, prin metoda backtracking, toate modalităţile de aşezare a
numerelor naturale de la 1 la 5 astfel încât oricare două numere consecutive
să nu se afle pe poziţii alăturate. Dacă primele două soluţii sunt: (1,3,5,2,4)
şi (1,4,2,5,3), care este prima soluţie generată care începe cu 2?
a. (2, 4, 1, 3, 5) b. (2, 5, 4, 3, 1) c. (2, 4, 1, 3, 1) d. (2, 3, 5, 4, 1)
xii) Construim anagramele unui cuvânt c1c2c3c4 prin generarea în ordine
lexicografică a permutărilor indicilor literelor cuvântului şi obţinem c1c2c3c4
c1c2c4c3 c1c3c2c4 … c4c3c1c2 c4c3c2c1. Pentru anagramele cuvântului rateu,
după şirul raetu, raeut, raute cuvintele imediat următoare sunt:
a. rauet şi rtaeu
b. rtaeu şi rtaue
c. rauet şi rtaue
d. rtaeu şi ratue
xiii) Trei baieti, Alin, Bogdan şi Ciprian, şi trei fete, Delia, Elena şi Felicia,
trebuie să formeze o echipă de 3 studenti, care să participe la un concurs de
prezentare software. Echipa trebuie să fie mixtă (adică să conţină cel puţin o
fată şi cel puţin un băiat). Ordinea copiilor în echipă este importantă
deoarece aceasta va fi ordinea de intrare a studentilor în concurs (de
exemplu echipa Alin, Bogdan, Delia este diferită de echipa Bogdan, Alin,
Delia). Câte echipe se pot forma, astfel încât din ele să facă parte simultan
Alin şi Bogdan? _______________
xiv) În vederea participării la un concurs de programare, studentii din anii 2
si 3 au dat o probă de selecţie, în urma căreia primii 6 au obţinut punctaje
egale. În câte moduri poate fi formată echipa selecţionată ştiind că poate
avea doar 4 membri, aleşi dintre cei 6, şi că ordinea acestora în cadrul
echipei nu contează?
a. 24 b. 30 c. 15 d. 4
xv) Un program construieşte şi afişează elementele produsului cartezian
AxBxC pentru mulţimile A={1,2,3,4}, B={1,2,3}, C={1,2}. Care dintre
următoarele triplete NU va fi afişat?
a. (3,2,1) b. (1,3,2) c. (1,2,3) d. (2,2,2)
Probleme diverse
(recursivitate, greedy, divide et impera, programare dinamica)
1. [Permutari] Sa se genereze permutarile multimii {1, 2, …, n}, cu n fixat. Se vor considera
algoritmi iterative si recursive.
2. [Recursivitate] Se considera o fotografie specificata printr-o matrice patratica care contine ‘0’
si ‘1’ (0 – pentru puncte albe si 1 – pentru puncte negre). Se considera fondul alb, obiectele
negre, iar daca punctele negre sint vecine pe linie, coloana sau diagonala atunci apartin aceluiasi
obiect. Sa se numere cite obiecte distincte apar in fotografie.
3. Sa se plaseze pe o tabla de sah (cu n randuri si n coloane) n dame astfel incit san u se atace
reciproc. Sa se genereze toate solutiile.
4. Sa se genereze toate partitiile multimii {1, 2, …, n} cu n fixat.
5. Se dau n tipuri de monezi. Sa se plateasca o suma data s, folosind un numar minim de monezi
din tipurile date. Se considera ca exista un numar sufficient de monezi din fiecare tip.
6. Se considera trei tije, pe prima dintre ele fiind asezate n discuri de dimensiuni diferite, astfel
incit cel mai mare este jos, si, peste el, in ordine descrescatoare a dimensiunii, celelalte discuri.
Discurile pot fi mutate de pe o tija pe alta, luind intotdeauna un disc care nu are deasupra sa alte
discuri si avind grija ca niciodata sa nu fie asezat un disc mai mare peste unul mai mic. Sa se
scrie un program care genereaza o secventa de mutari prin care discurile sint mutate de pe tija 1
pe tija 2.
7. Se considera un numar natural n (3<n<15). Sa se genereze cel mai scurt sir format din 0 si 1 de
lungime 2n+n-1, astfel incit oricare ar fi doua secvente de lungime n ale acestui sir, acestea sa fie
diferite.
8. Se considera o stiva de case de bani sub forma de piramida. Astfel, pe primul nivel vor fi n
case, pe urmatorul n-1 case, apoi n-2, …, pina la ultimul nivel unde va fi o singura casa de bani.
Deci, fiecare casa se va sprijini pe doua case de bani din etajul anterior, mai putin cele din etajul
de baza care se vor sprijini direct pe podea. Se dau n(n+1)/2 saci cu bani, fiecare continind o
anumita suma. Sa se distribuie acesti saci, fiecare intr-o casa, astfel incit in fiecare casa sa fie
exact atitia bani cit in cele doua cutii pe care se sprijina la un loc. Pentru casele din stratul de
baza nu exista nicio conditie. Ca date de intrare se utilizeaza: n (numarul de cutii din stratul de
baza) si s1, s2, …., unde si reprezinta suma de bani din sacul i (i= 1, 2, …, n(n+1)/2).
9. Se dau doua siruri de caractere. Sa se determine daca ele sint anagrame, adica sint formate din
aceleasi litere, dar puse in alta ordine.
10. Se da o lista cu n cuvinte. Sa se formeze un cel mai lung sir in care fiecare cuvint incepe cu
litera cu care se termina predecesorul sau (mai putin primul cuvint care poate fi oricare).
11. Intr-un grup de n personae se precizeaza perechi de personae care se considera prietene.
Folosind principiul ca “prietenul prietenului meuimi este prieten” sa se determine grupurile cu
numar maxim de persoane intre care se pot stabili relatii de prietenie directe sau indirecte.
12. Intr-o statiune de odihna s-au intilnit n sahisti, codificati prin numare naturale de la 1 la n,
care au jucat p partied de sah. Pentru fiecare partida se precizeaza cei doi jucatori. Sa se
determine un grup cit mai mare de jucatori, care prin jocurile pe care le-au desfasurat, au format
o grupare de tip turneu (in care fiecare a jucat cu fiecare).
13. Reteaua de distribuire a apei calde pentru o centrala termica zonala este formata dintr-un
sistem de conducte care leaga centrala de blocuri si blocurile intre ele. Blocurile din retea sunt
numerotate cu numere intregi de la 1 la n, centrala fiind
etichetata cu 0. Se cunosc distantele de la centrala la blocuri precum si distantele dintre blocuri.
Sa se determine perechile de numere desemnand punctele de distribuire intre care trebuie sa se
monteze conducte astfel incat fiecare bloc sa fie alimentat cu apa calda (nu neaparat direct de la
centrala) si lungimea totala a conductelor necesare sa fie minima.
14. Un student doreste sa calatoreasca din localitatea X in localitatea Y. Daca in tara exista n
localitati si timpul necesar pentru a ajunge dintr-o localitate in alta (in cazul in care se poate
ajunge direct) se cere sa se determine timpul minim in care studentul poate sa ajunga din X in Y.
15. Fiind date n orase si costurile tuturor drumurilor directe care exista intre orase, sa se afle
costul minim pentru a ajunge dint-un oras in oricare altul.
16. Fie un arbore cu n varfuri. In fiecare nod al arborelui se afla cate un bec. Prin atingerea unui
bec acesta isi schimba starea (din stins in aprins si invers), la fel si vecinii lui directi.
Considerand ca initial toate becurile sunt stinse, sa se scrie un program care genereaza o secventa
de “atingeri” prin care pomul este aprins complet. Datele de intrare se citesc din fisierul
[Link] cu formatul: pe prima linie numarul de noduri, sip e urmatoarele n-1 linii se afla
muchiile arborelui.
17. Sa presupunem, ca un graf neorientat este format din n varfuri si m arce. Se stie ca sunt
folosite toate muchiile pentru a lega varfuri si ca doua varfuri pot fi legate direct prin cel mult o
muchie. Sa se determine valoarea maxima a expresiei S = suma patratelor gradelor varfurilor,
unde gradul unui varf este reprezentat de numarul de muchii legate de acesta.
18. Un om doreste sa urce o scara cu N trepte (N dat initial). El poate urca una sau doua trepte la
un moment. Fiind o fire curioasa, acest om isi pune problema in cate moduri poate urca aceasta
scara.
19. Se da un sir de numere a[0], a[1], …, a[n-1], cu n dat initial. Sa se afle un cel mai lung subsir
crescator.
20. Se dau doua siruri a[0], a[1], …, a[n-1] si b[0], b[1], …, b[m-1]. Sa se gaseasca un cel mai
lung subsir comun al acestora.
21. Se considera o tabla de sah, de dimensiune standard 8x8, pe care se afla diverse piese de sah.
Un cal se afla pe pozitia (i,j). Se doreste mutarea calului in pozitia (k,l) – daca acest lucru este
posibil – folosind oricare dintre cele 8 mutari posibile ale calului in orice succesiune, astfel incat
numarul de mutari sa fie minim.
22. Se considera o pereche de numere de forma (a, b) asupra careia se pot efectua urmatoarele
operatii: (a, b) -> (a-b, b); (a, b) -> (a+b, b), (a, b) -> (b, a). Fiind date valorile (a, b) sa se
determine numarul minim de operatii pe care trebuie sa le facem astfel incat sa se ajunga la
perechea (c, d), daca acest lucru este posibil.
23. Se considera o bara de lungime n (n >0, n<40001). Se doreste taierea acesteia in bucati de
dimensiuni prestabilite. Se dau m astfel de dimensiuni in care putem taia bara. Problema consta
in ataia asemenea bucati din bara, de dimensiuni date, astfel incat sa ramana cat mai putin
material care nu mai poate fi folosit (nu corespunde nici unei dimensiuni).
24. Inmultirea optimala a matricelor si rezolvarea recurentei f(n)=7f(n/2)+18(n/2)2 [1, pag. 216]
25. Problema colorarii hartilor [1, pag. 219].
26. Problema comis-voiajorului [1, pag. 220]
27. Generarea obiectelor combinatoriale [1, pag. 221]
28. Problema rucsacului [1, pag. 225]
29. Executarea lucrarilor cu termen final [1, pag. 226]
30. Prelucrarea expresiilor cu ajutorul structurilor arborescente [1, 190]