WorksheetsTest 11B backtracking
Total questions: 13
Worksheet time: 15mins
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.
(a)
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ă.
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.
(a)
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 ?
(a)
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?
(a)
Se consideră algoritmul care determină toate permutările distincte de n obiecte (numerotate de la 1 la n), în care pe orice poziţie de rang par se află o valoare pară. De exemplu, pentru n=5, primele trei permutări generate sunt: (1,2,3,4,5), (1,2,5,4,3), (1,4,3,2,5). Scrieți numărul total de astfel de permutări.
(a)
Utilizând metoda backtracking, se generează toate modalitățile de a pregăti o ținută, luând, într-o anumită ordine, articolele din mulțimea {cămașă, cravată, pantaloni, pantofi, sacou, șosete}, având în vedere următoarele restricții: cămașa va fi luată înaintea cravatei, cravata înaintea sacoului și atât șosetele, cât și pantalonii, înaintea pantofilor. Primele trei soluții generate sunt, în această ordine: (cămașă, cravată, pantaloni, sacou, șosete, pantofi), (cămașă, cravată, pantaloni,șosete, pantofi, sacou), (cămașă, cravată, pantaloni, șosete, sacou, pantofi). Indicați cea de a șasea soluție generată.
(a)
