WorksheetsTest BKT
Total questions: 10
Worksheet time: 10mins
Utilizând metoda backtracking sunt generate numerele de 3 cifre, având toate cifrele în ordine strict crescătoare şi cu proprietatea că 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 9-lea număr generat?
169
167
234
189
Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d,e,f}, cuvinte care nu conţin două vocale alăturate. Primele nouă cuvinte generate sunt, în ordine: abab, abac, abad, abaf, abba, abbb, abbc, abbd, abbe. Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e?
20
15
24
18
Un elev a scris un program care, folosind metoda backtracking, generează toate numerele de câte 4 cifre, cifrele fiind în ordine strict crescătoare. Scrieţi în ordine crescătoare, separate prin câte un spațiu toate numerele generate de program care au prima cifră 5.
(a)
Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte din mulţimea {1,2,4,6}, numere cu cifrele în ordine strict crescătoare, obţinându-se, în ordine: 124, 126, 146, 246. Dacă se utilizează exact aceeaşi metodă pentru a genera numerele naturale cu patru cifre distincte din mulţimea {1,2,3,4,5,6,7,8,9}, câte dintre numerele generate au prima cifră 2 şi ultima cifră 8?
6
5
15
10
Utilizând metoda backtracking se generează, în ordine crescătoare, toate numerele de câte 5 cifre, toate din mulțimea {1,2} cu proprietatea că nu există mai mult de două cifre 1 pe poziții consecutive. Primele 5 soluții generate sunt, în această ordine: 11211, 11212, 11221, 11222, 12112. Indicaţi cea de a 9-a soluţie generată.
12211
12122
12221
12212
Utilizând metoda backtracking se generează toate posibilitățile de a scrie numărul 10 ca sumă de numere prime. Soluțiile generate sunt, în această ordine: 2+2+2+2+2, 2+2+3+3, 2+3+5, 3+7, 5+5. Folosind aceeași metodă se generează toate posibilitățile de a scrie numărul 9 ca sumă de numere prime. Indicați a doua soluție generată.
2+2+2+3
2+7
3+3+3
2+2+5
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:
submulţimilor unei mulţimi cu 5 elemente
produsului cartezian a unor mulţimi de cifre
aranjamentelor de 9 elemente luate câte 5
combinărilor de 9 elemente luate câte 5
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.
65987 şi 67985
65978 şi 67988
65978 şi 67958
65987 şi 67958
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:
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
Următoarele probleme se referă la mulţimea de numere reale M={x1, x2, …, xn} (n≤15). Care dintre acestea, comparativ cu celelalte, admite un algoritm care se încheie după un număr maxim de paşi?
sortarea elementelor mulţimii M
generarea elementelor produsului cartezian M x M x M
determinarea elementului minim al mulţimii M
generarea tuturor permutărilor mulţimii M
