Волк, коза и капуста. На берегу реки стоит крестьянин с лодкой, а рядом с ним находятся волк, коза и капуста.
Крестьянин должен переправиться сам и перевезти волка, козу и капусту на другой берег. Однако в лодку кроме крестьянина помещается либо только волк, либо только коза, либо только капуста.
Оставлять же волка с козой или козу с капустой без присмотра нельзя — волк может съесть козу, а коза — капусту.
Как должен вести себя крестьянин?
Решение задачи Волк, коза и капуста
В данной задаче крестьянин может следовать одному из двух алгоритмов:
Алгоритм 1
1) сначала переправляются крестьянин и коза
2) крестьянин оставляет козу и возвращается обратно
3) крестьянин переправляет волка
4) крестьянин возвращается с козой
5) крестьянин переправляет капусту
6) крестьянин возвращается один
7) крестьянин забирает козу и отправляется на другой берег
Алгоритм 2
1) сначала переправляются крестьянин и коза
2) крестьянин оставляет козу и возвращается обратно
3) крестьянин переправляет капусту
4) крестьянин возвращается с козой
5) крестьянин переправляет волка
6) крестьянин возвращается один
7) крестьянин забирает козу и отправляется на другой берег