Backtracking

Utilizând metoda backtracking se generează toate modalitățile de a prepara o băutură din câte 3 sau 4 tipuri de fructe distincte din mulțimea {căpșune, mere, pepene, pere, portocale}. Primele patru soluții generate sunt, în această ordine: (căpșune, mere, pepene), (căpșune, mere, pepene, pere), (căpșune, mere, pepene, portocale), (căpșune, mere, pere). Indicați cea de a șasea soluție generată.

• (pepene, pere, portocale)

• (căpșune, mere, pere, pepene)

• (căpșune, mere, portocale)

• (mere, pepene, pere, portocale)

Utilizând metoda backtracking, se generează toate meniurile care cuprind câte patru feluri distincte de mâncare din mulțimea {aperitiv, desert, legume, paste, salată, supă}, fiecare meniu respectând următoarele condiții: • dacă există aperitiv, este servit primul; • dacă există desert, este servit ultimul; • NU sunt servite legume și salată în același meniu; • dacă există paste și supă în același meniu, pastele NU sunt servite înainte de supă. Două meniuri sunt distincte dacă diferă prin cel puțin un fel de mâncare sau prin ordinea servirii acestora. Primele cinci meniuri generate sunt, în această ordine: (aperitiv, legume, paste, desert), (aperitiv, legume, supă, desert), (aperitiv, legume, supă, paste), (aperitiv, paste, legume, desert), (aperitiv, paste, salată, desert). Indicați al șaselea meniu generat!

• (aperitiv, salată, paste, desert)

• (aperitiv, salată, supă, desert)

• (aperitiv, salată, supă, paste)

• (aperitiv, supă, legume, desert)

Utilizând metoda backtracking se generează toate variantele prin care patru persoane pot plăti o consumație totală de 200 de lei în următoarele condiții: • fiecare plătește o sumă nenulă, divizibilă cu 10; • primul plătește mai mult decât al doilea, al doilea mai mult decât al treilea, iar acesta mai mult decât al patrulea. O soluție constă în patru valori, reprezentând, în ordine, sumele plătite de fiecare dintre cele patru persoane. Primele patru soluții generate sunt, în această ordine: (70, 60, 40, 30), (70, 60, 50, 20), (80, 50, 40, 30), (80, 60, 40, 20). Indicați cea de a șasea soluție, în ordinea generării acestora.

• (80,60,45,15)

• (80,60,50,10)

• (80,70,30,20)

• (80,70,40,10)

Având la dispoziție cinci tipuri de prăjituri, cu caise, cu căpșune, cu prune, cu piersici, respectiv cu cireșe, se utilizează metoda backtracking pentru a obține toate posibilitățile de a forma platouri cu câte trei tipuri de prăjituri diferite, știind că în cadrul unui platou nu contează ordinea de așezare a prăjiturilor și că prăjiturile cu căpșune nu vor fi plasate pe același platou cu prăjiturile cu piersici. Primele patru soluții obținute sunt, în această ordine: (caise, căpșune, prune), (caise, căpșune, cireșe), (caise, prune, piersici), (caise, prune, cireșe). A șasea soluție generate este:

• {caise, prune, căpșune}

• {caise, piersici, cireșe }

• {prune, piersici, cireșe}

• {căpșune, prune, cireșe}

Utilizând metoda backtracking, se generează toate numerele impare de cel mult trei cifre din mulţimea {0, 1, 2, 3}. Primele 8 soluţii generate sunt, în această ordine: 1, 101, 103, 11, 111, 113, 121, 123. Cea de a 12-a soluţie generată este:

• 13

• 201

• 133

• 31