Test 11B backtracking

Utilizând metoda backtracking, se generează toate drapelele formate din câte 3 culori distincte din mulţimea {alb, galben, negru, roșu, verde}. Două drapele sunt distincte dacă diferă prin cel puțin o culoare sau prin ordinea culorilor. Primele patru soluţii obţinute sunt, în această ordine: (alb, galben, negru), (alb, galben, roșu), (alb, galben, verde) şi (alb, negru, galben).

Scrieți soluția generată imediat înainte și imediat după soluția (galben, verde, alb).

Fiecare solutie va fi scrisă între paranteze rotunde, separate de 1 spațiu, fără diacritice.

Utilizând metoda backtracking, se generează toate băuturile obținute amestecând sucurile a cel puțin două fructe distincte din mulţimea {afine, caise, lămâi, mere, pere}. Primele cinci soluţii obţinute sunt, în această ordine: (afine, caise), (afine, caise, lămâi), (afine, caise, lămâi, mere),(afine, caise, lămâi, mere, pere) şi (afine, caise, lămâi, pere). A șaptea soluţie este:

• (afine, caise, mere)
• (afine, mere, pere)
• (afine, caise, mere, pere)
• (afine, lămâi, mere, pere)

Punctul din oficiu

• 6 puncte

• 10 puncte

Utilizând metoda backtracking, se generează toate modalitățile de a pregăti clătite, folosind, într-o anumită ordine, toate ingredientele din mulțimea {făină, lapte, ouă} pentru aluat, apoi unul dintre ingredientele din mulțimea {ciocolată, dulceață, urdă} pentru umplutură, și, la final, unul dintre ingredientele din mulțimea {cașcaval, mărar, frișcă} pentru ornare, având în vedere următoarele restricții: frișca se poate folosi numai împreună cu ciocolata și dulceața, iar mărarul și cașcavalul numai împreună cu urda. Primele cinci soluții generate sunt, în această ordine: (făină, lapte, ouă, ciocolată, frișcă), (făină, lapte, ouă, dulceață, frișcă), (făină, lapte, ouă, urdă, cașcaval), (făină, lapte, ouă, urdă, mărar), (făină, ouă, lapte, ciocolată, frișcă).

Indicați a șaptea soluție generată.

• (ouă, lapte, făină, urdă, mărar)
• (făină, ouă, lapte, dulceață, frișcă)
• (lapte, făină, ouă, ciocolată, frișcă)
• (făină, ouă, lapte, urdă, cașcaval)

Algoritmul backtracking se încheie dacă:

• s-au testat toate valorile posibile pentru primul nivel
• s-au testat toate valorile posibile pentru ultimul nivel
• pe un nivel oarecare, k, nu am găsit nici o valoare care sa verifice conditiile de continuare

După ce s-a gasit o valoare convenabilă pentu componenta k, următorul pas este:

• se trece la componenta urmatoare, k+1
• se rămâne la componenta k, căutând în continuare o altă valoare convenabilă
• se revine la componenta k-1

Utilizând metoda backtracking sunt generate toate numerele din intervalul [100,999] cu proprietatea că au cifrele în ordine crescătoare și cifrele aflate pe poziții consecutive sunt de paritate diferită. Primele cinci soluții generate sunt, în această ordine, 123, 125, 127, 129, 145. Indicați cel de al 10-lea număr generat.

• 149
• 167
• 169
• 189

Folosind modelul combinărilor se generează cuvinte cu câte două litere distincte din mulţimea {i,t,e,m} obţinându-se, în ordine: it, ie, im,te, tm, em. Dacă se utilizează exact aceeaşi tehnică pentru a genera toate cuvintele cu patru litere distincte din mulţimea {i,t,e,m,a,x}, scrieți predecesorul şi succesorul cuvântului tema generat la un moment dat.

Pentru generarea în ordine crescătoare a numerelor cu n cifre formate cu elementele mulţimii {0,2,9} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele 20,22,29,90,92,99. Dacă n=4 şi se utilizează acelaşi algoritm, care este numărul generat imediat înainte și imediat după numărul 2009 ?

Se generează, utilizând metoda backtracking, toate modalităţile de aşezare a numerelor naturale de la 1 la 5, astfel încât oricare două numere de aceeaşi paritate să nu se afle pepoziţii alăturate. Dacă primele 3 soluţii generate sunt, în ordine: 12345, 12543 şi 14352 care este a doua soluţie generată ce începe cu 3?