luni, 15 decembrie 2008

Alizeea's Puzzles

Misionarii si canibalii

De data aceasta va voi propune o problema clasica a Inteligentei Artificiale, o problema cu care m-am reintalnit de curand, mai exact saptamana trecuta, cand Cezar (gasiti blogul echipei lui aici) ne-a amintit Monicai (blogul echipei ei este aici) si mie aceasta problema. Am gasit pe net chiar o aplicatie cu aceasta problema si va invit sa o rezolvati chiar acolo .

Dar sa va spun despre ce este vorba. Trei misionari si trei canibali se afla de partea unui rau si vor sa treaca de cealalta parte. Pentru aceasta, au la dispozitie o barca in care intra doua persoane. Dar problema este ca daca pe un mal raman mai multi canibali decat misionari atunci canibalii vor manca misionarii/misionarul deoarece misionarii/misionarul se afla in inferioritate numerica. Daca pe un mal raman mai multi misionari decat canibali nu se intampla nimic. In ce ordine trebuie sa treaca cei trei misionari si cei trei canibali astfel incat sa ajunga cu totii pe celalalt mal "safe and sound"?

Have fun :)

Un comentariu:

Alina spunea...

Presupunem ca pe malul drept sunt toti cei 3 M si cei 3 C si vrem sa ii ducem pe malul stang
Prescurtari: M-misionar, C-canibal
Solutia:
1.urca in barca M+C
2. e lasat C si M se intoarce
(pe malul drept se afla 3 M si 2 C)
(pe malul stang: 1 C)
3. M coboara; urca in barca C + C
4. se intoarce un C
(pe malul drept: 3 M + 1 C)
(pe malul stang: 2 C)
5. coboara C; se urca 2 M
6. pe malul stang, coboara un M si se urca un C
7. se intoarce barca, avand inauntru un M si un C
(pe malul drept: 2 M si 2 C)
(pe malul stang: 1 M si 1 C)
8. se urca in barca cei 2 M
9. coboara cei doi M si se intoarce C
(pe malul drept: cei 3 C)
(pe malul stang: cei 3 M)
10. se urca 2 C
11. lasa un C si se intoarce
(pe malul drept: 2 C)
(pe malul stang: 3M + 1 C)
12. C din barca ia si ultimul C
13. coboara cei doi C
(pe malul drept: nothing)
(pe malul stang: 3M + 3C)

Sper ca v-ati distrat cu acea aplicatie online :)