a fost răspuns

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}

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

(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 6-a soluție generată.


Eventual daca puteti anexa si o rezolvare explicita, as fi tare recunoscatoare:))

Răspuns :

(cămașă, cravată, pantaloni, sacou, șosete, pantofi), (cămașă, cravată, pantaloni, șosete, pantofi, sacou), (cămașă, cravată, pantaloni, șosete, sacou, pantofi),

4. (cămașă, cravată, sacou, pantaloni, șosete, pantofi),

5. (cămașă, cravată, sacou, șosete, pantaloni, pantofi),

6. (cămașă, cravată, șosete, pantaloni, pantofi, sacou).

Ceea ce am făcut aici a fost să generez soluțiile astfel încât ele să respecte ordinea prevăzută.

După cum se observă, așa cum sunt aranjate inițial în enunț, este încălcată regula pantofilor: șosetele nu preced pantofii. Din acest motiv, NU putem începe o soluție (cămașă, cravată, pantaloni, pantofi...). Vom începe prima soluție cu următorul element, sacou, și verificăm dacă există soluții care respectă astfel regula:

(cămașă, cravată, pantaloni, sacou, pantofi, șosete) NU respectă.

(cămașă, cravată, pantaloni, sacou, șosete, pantofi) respectă.

Dacă ar trebui să generăm toate soluțiile fără regula de ordine, primele ar arăta așa:

1. (cămașă, cravată, pantaloni, pantofi, sacou, șosete),

2. (cămașă, cravată, pantaloni, pantofi, șosete, sacou),

3. (cămașă, cravată, pantaloni, sacou, pantofi, șosete),

4. (cămașă, cravată, pantaloni, sacou, șosete, pantofi),

5. (cămașă, cravată, pantaloni, șosete, pantofi, sacou),

6. (cămașă, cravată, pantaloni, șosete, sacou, pantofi), etc.

dintre care, doar 4, 5 și 6 respectă regula pantofilor, exact cele 3 soluții ce apar în exemplul din enunț.

După ce am epuizat toate posibilitățile care încep cu (cămașă, cravată, pantaloni...), voi lua următorul element, pantofi. Dar pantofii nu trebuie să preceadă pantalonii și șosetele, deci nu e bună soluția. Iau următorul element, sacoul și încep să generez:

(cămașă, cravată, sacou, pantaloni, pantofi, șosete) nu merge.

(cămașă, cravată, sacou, pantaloni, șosete, pantofi) merge.

(cămașă, cravată, sacou, pantofi...) nu merge.

(cămașă, cravată, sacou, șosete, pantaloni, pantofi) merge.

(cămașă, cravată, sacou, șosete, pantofi, pantaloni) nu merge.

Astfel, am mai generat două soluții.

Se trece la soluțiile (cămașă, cravată, șosete...) unde imediat o găsesc și pe cea de-a 6.

Cam greuț de explicat, dar sper că se înțelege. =)

Andrei750238ask

E destul de dificil sa rezolvam problema in acest format, mult mai usor e sa tranformam itemele in numere :

cămașă = 1

cravată = 2

pantaloni = 3

pantofi = 4

sacou = 5

șosete = 6

Restrictii :

1 inainte de 2

2 inainte de 5

3 si 6 inainte de 4

Primele 3 solutii ale lor :

1 2 3 5 6 3

1 2 3 6 4 5

1 2 3 6 5 4

Observam ca sunt in solutiile sunt in ordine crescatoare, cele care indeplinesc toate cele 3 conditii. Incercam sa generam in continuare si vedem daca solutiile  noastre in ordine indeplinesc conditii

Generari :

1 2 4 . . .- > Nu se poate, trebuie ca 3 si 6 inainte de 4. In ordinea aceasta 3 si 6 ar fi obligatoriu dupa 4, ceea ce nu e bine. Deci abandonam toate solutiile de forma 1 2 4 ? ? ?

1 2 5 3 4 .-> Nu se poate, trebuie ca 3 si 6 inainte de 4

1 2 5 3 6 4

1 2 5 4 . .-> NU se poate, trebuie ca 3 si 6 inainte de 4

1 2 5 6 3 4

1 2 5 6 4 . -> NU se poate, trebuie ca 3 si 6 inainte de 4

1 2 6 3 4 5

Deci a sasea solutie generata este 1 2 6 3 4 5, ceea ce decodificat inseamna : ( camasa, cravata, sosete, pantaloni, pantofi, sacou )