Test BKT

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={x₁, x₂, …, x_n} (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