Backtracking

Folosind modelul combinarilor, se genereaza cuvinte cu trei litere distincte din multimea {a,i,t,e,m}. Care este antepenultimul cuvant generat?

• tem

• iem

• ite

• itm

• aem

Un algoritm generează în ordine descrescătoare toate numerele de 5 cifre, fiecare dintre ele având cifrele în ordine strict crescătoare. Care sunt ultimele 3 soluţii generate, în ordinea generării?

• 12347 12346 12345

• 45678 35678 34678

• 12345 12346 12347

Precizaţi modalitatea de a calcula numărul de posibilităţi de a aranja pe o casetă n melodii astfel încât melodia a să urmeze imediat melodiei b.

• combinări

• aranjamente

• permutari

• produs cartezian

Generând prin metoda backtracking toate drapelele care au culoarea ROŞIE (R) ca ultimă culoare culoare, utilizând culorile ROŞU (R), OCRU (O), AURIU (A) şi TURCOAZ (T) obţinem primele trei soluţii în ordinea: OATR, OTAR, AOTR. Precizaţi ultimul drapel din această serie:

• TAOR

• TOAR

• ATOR

• AOTR

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 ?

Considerând etapele specifice metodei Backtracking, stabiliţi valoarea de adevăr a următorului enunţ :

Dacă valoarea testată pentru un element oarecare al soluţiei respectă condiţiile interne ale problemei, atunci se trece la următorul element al soluţiei pentru a-i testa valorile posibile.

• da

• nu

Pentru care dintre problemele de mai jos, se recomandă utilizarea metodei Backtracking ?

• determinarea intersecţiei a n mulţimi

• generarea tuturor numerelor din intervalul (1,100) cu proprietatea că suma numerelor este un număr prim

• determinarea tuturor şirurilor de n paranteze care se inchid corect

• generarea de n numere aleatoare într-un interval dat

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 asfel 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

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 numar se va genera imediat înaintea numărului 9317?