Backtracking1

Utilizând metoda backtracking, se generează toate posibilitățile de a forma cutii cu dulciuri de tipuri distincte din mulțimea {bomboane, drajeuri, jeleuri, praline}. Într-o cutie sunt cel puțin două tipuri de dulciuri, dar nu pot fi și jeleuri și praline simultan. Două cutii sunt distincte dacă ele conțin cel puțin un tip diferit de dulciuri. Primele patru soluţii generate sunt, în această ordine, (bomboane, drajeuri), (bomboane, drajeuri, jeleuri), (bomboane, drajeuri, praline), (bomboane, jeleuri). Indicați a șasea soluție, în ordinea generării acestora.

• (bomboane, praline)

• (drajeuri, jeleuri)

• (drajeuri, praline)

• (jeleuri, praline

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 11 ca sumă de numere prime. Indicați a treia soluție generată.

• 2+2+2+5

• 2+2+7

• 2+3+3+3

• 3+3+5

Utilizând metoda backtracking se generează toate modalitățile de a scrie numărul 9 ca sumă de numere naturale prime. Termenii fiecărei sume sunt în ordine crescătoare. Cele patru soluții sunt obținute în această ordine: 2+2+2+3; 2+2+5; 2+7; 3+3+3.

Aplicând același algoritm, se doreste generarea solutiilor pentru n=15.Care este solutia generata imediat dupa solutia 2+2+2+3+3+3?

• 2+2+2+2+2+5

• 2+3+3+7

• 2+2+2+3+5

• 2+2+3+3+5

Utilizând metoda backtracking, se generează toate posibilitățile de a expune câte trei mașini produse în România, din gama Dacia, din mulţimea {Dokker (negru), Duster (negru), Lodgy (gri), Logan (alb), Sandero (roșu)}, astfel încât să nu fie expuse simultan două mașini de aceeași culoare, Sandero să NU apară pe prima poziție, iar Logan să NU fie înainte de Dokker sau Duster. Două soluții sunt distincte dacă au cel puțin o mașină diferită sau dacă ordinea mașinilor este diferită.

Primele cinci soluţii generate sunt, în această ordine (Dokker, Lodgy, Logan), (Dokker, Lodgy, Sandero), (Dokker, Logan, Lodgy), (Dokker, Logan, Sandero), (Dokker, Sandero, Lodgy). Indicaţi penultima soluție, în ordinea generării acestora.

• Logan, Lodgy, Sandero

• Logan, Sandero, Lodgy

• Lodgy, Dokker, Logan

• Lodgy, Logan, Dokker

Utilizând metoda backtracking, se generează toate posibilitățile de a forma platouri de câte trei fructe distincte din mulţimea {măr, gutuie, prună, caisă, piersică}, astfel încât pe același platou nu se află o gutuie și o piersică simultan. Două platouri sunt distincte dacă ele conțin cel puțin un fruct diferit.

Primele patru soluţii generate sunt, în această ordine, (măr, gutuie, prună), (măr, gutuie, caisă), (măr, prună, caisă), (măr, prună, piersică).

Indicați soluţia generată imediat după (gutuie, prună, caisă).

• (caisă, piersică, măr)

• (gutuie, prună, piersică)

• (mar, caisă, piersică)

• (prună, caisă, piersică)

Utilizând metoda bactracking se generează toate șirurile de 5 litere distincte din mulțimea {A, M, U, R, G}, astfel încât în fiecare șir litera R precede literele A și M. Primele cinci soluții generate sunt, în această ordine: URAMG, URAGM, URMAG, URMGA, URGAM. Indicați soluția generată imediat după GURMA.

• GARUM

• GRAMU

• GRAUM

• GRUAM

Utilizând metoda backtracking, se generează toate modalitățile de forma un grup de patru persoane din mulțimea {Ana, Ioana, Lia, Maria, Miruna, Simona}. Două grupuri diferă prin cel puțin o persoană. Primele cinci soluții generate sunt, în această ordine: (Ana, Ioana, Lia, Maria), (Ana, Ioana, Lia, Miruna), (Ana, Ioana, Lia, Simona), (Ana, Ioana, Maria, Miruna), (Ana, Ioana, Maria,Simona). Indicați o enumerare generată ca soluție, în această formă.

• (Ana, Lia, Maria, Miruna, Simona)

• (Ioana, Maria, Miruna, Simona)

• (Lia, Ioana, Maria, Simona)

• (Maria, Miruna, Lia, Simona)

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 8-a soluţie generată.

• 12122

• 12211

• 12212

• 12221

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 treia soluție generată.

• 2+2+2+3

• 2+2+5

• 2+7

• 3+3+3

Pe parcursul vacanței au loc mai multe reprezentații online ale unei piese de teatru; pentru o reprezentație sunt necesari trei copii, unul pentru rolul principal, iar fiecare dintre ceilalți doi pentru câte un rol secundar. Pentru oricare două reprezentații distincte cel puțin un rol este atribuit, în cele două distribuții, unor copii diferiți. În urma audițiilor au fost selectați șase copii, Alex, Cezar, Tudor, Daria, Ela și Maria:doar Alex poate primi rolul principal, iar fiecare dintre ceilalți cinci copii poate interpreta oricare dintre cele două roluri secundare. De exemplu, pentru patru reprezentații sunt distribuiți, în ordinea rolurilor, copiii: (Alex, Ela, Maria), (Alex, Maria, Ela), (Alex, Maria, Cezar), (Alex, Cezar, Tudor). Indicați numărul maxim de reprezentații distincte în care poate fi distribuită Daria.

• 5

• 8

• 16

• 24