Strona główna » Algorytmy » Artykuły » Problem transportowy
 

Problem transportowy

Zagadka

Mężczyzna wracał do domu ze swoim lisem, kurczakiem i paczką siana. Musi on przebyć rzekę w małej łódce, gdzie mieści się on i coś. Niestety, jeśli lis zostanie z kurczakiem na jednym brzegu to go zje. Podobnie kurczaka nie można zostawić z samym sianem, bo je rozgrzebie. Jak mężczyzna może wszystko przetransportować na drugą stronę rzeki?

Rozwiązanie

Odpowiedź

W poniższym rozwiązaniu przyjęto następujące oznaczenia: M - mężczyzna, K - kurczak, L - lis oraz S - siano.

Brzeg źródłowyŁódkaBrzeg docelowyAkcja
M, K, L, S--Mężczyzna przewozi kurczaka na drugi brzeg
L, SM, K-.
L, S-M, Ki wraca sam
L, SMK.
M, L, S-KMężczyzna przewozi lisa na drugi brzeg
SM, LK.
S-M, K, LMężczyzna wraca z kurczakiem
SM, KL.
M, K, S-LMężczyzna przewozi siano, a zostawia kurczaka
KM, SL.
K-M, S, LMężczyzna wraca teraz po kurczaka i przewozi na drugi brzeg
KMS, L.
M, K-S, L.
-M, KS, L.
--M, K, S, Lgotowe!

Zagadkę można też rozwiązać innym sposobem. Czy umiesz wskazać, które kroki można wykonać inaczej?