Это старинная русская задача. Но она имеется в фольклоре не только русских, но и других народов.
Крестьянину необходимо перевезти через реку три объекта: волка, козу и кочан капусты. Но лодка у мужика мала, она выдерживает самого мужика и, кроме него, только один объект: либо волка, либо козу, либо кочан. Кроме того, волка нельзя оставлять с козой (без мужика), а козу нельзя оставлять с капустой.
Как переправить с этого на тот берег все три объекта?
Для данной задачи существуют два способа решения.
Обозначим этот берег как "берег А", а тот берег — как "берег Б".
Дано: берег А — крестьянин, волк, коза, капуста; берег Б — никого.
Надо: берег А — никого; берег Б — крестьянин, волк, коза, капуста.
Первый алгоритм.
- Крестьянин сажает с берега А в лодку козу. Волк остаётся на берегу А вместе с капустой. Как известно, волки капусту не едят.
- Крестьянин едет с берега А на берег Б вместе с козой.
- Добравшись до берега Б, крестьянин высаживает из лодки на берег Б козу.
- Крестьянин едет с берега Б на берег А один (без объектов).
- Добравшись до берега А, крестьянин сажает с берега А в лодку волка. Капуста пока остаётся на берегу А.
- Крестьянин едет с берега А на берег Б вместе с волком.
- Добравшись до берега Б, крестьянин сажает с берега Б себе в лодку козу. После этого крестьянин сразу же высаживает из лодки на берег Б волка.
- Крестьянин едет с берега Б на берег А вместе с козой.
- Добравшись до берега А, крестьянин берёт с берега А в лодку лежавшую на берегу А капусту. После этого крестьянин сразу же высаживает из лодки на берег Б козу.
- Крестьянин едет с берега А на берег Б вместе с капустой.
- Добравшись до берега Б, крестьянин кладёт из лодки на берег Б капусту. Как мы знаем, на берегу Б к этому времени находится волк. Капусту с волком оставить можно.
- Крестьянин едет с берега Б на берег А один.
- Добравшись до берега А, крестьянин сажает с берега А себе в лодку козу.
- Крестьянин едет с берега А на берег Б вместе с козой.
- Добравшись до берега Б, крестьянин наконец-то высаживается из лодки на берег Б сам. После этого крестьянин благополучно высаживает из лодки на берег Б козу.
Второй алгоритм.
- Крестьянин сажает с берега А в лодку козу. Волк остаётся на берегу А вместе с капустой. Как известно, волки капусту не едят.
- Крестьянин едет с берега А на берег Б вместе с козой.
- Добравшись до берега Б, крестьянин высаживает из лодки на берег Б козу.
- Крестьянин едет с берега Б на берег А один (без объектов).
- Добравшись до берега А, крестьянин берёт с берега А в лодку капусту. Волк пока остаётся на берегу А.
- Крестьянин едет с берега А на берег Б вместе с капустой.
- Добравшись до берега Б, крестьянин сажает с берега Б себе в лодку козу. После этого крестьянин сразу же кладёт из лодки на берег Б капусту.
- Крестьянин едет с берега Б на берег А вместе с козой.
- Добравшись до берега А, крестьянин сажает с берега А в лодку находившегося на берегу А волка. После этого крестьянин сразу же высаживает из лодки на берег Б козу.
- Крестьянин едет с берега А на берег Б вместе с волком.
- Добравшись до берега Б, крестьянин высаживает из лодки на берег Б волка. Как мы знаем, на берегу Б к этому времени находится капуста. Волка с капустой оставить можно.
- Крестьянин едет с берега Б на берег А один.
- Добравшись до берега А, крестьянин сажает с берега А себе в лодку козу.
- Крестьянин едет с берега А на берег Б вместе с козой.
- Добравшись до берега Б, крестьянин наконец-то высаживается из лодки на берег Б сам. После этого крестьянин благополучно высаживает из лодки на берег Б козу.
И в первом, и во втором случае для перевозки трёх объектов крестьянину пришлось совершить по семь переправ через реку на своей лодке (переправы описаны в следующих пунктах обоих алгоритмов: 2, 4, 6, 8, 10, 12, 14).
Алгоритм был бы гораздо проще, если бы лодка помимо крестьянина выдерживала хотя бы два объекта.
Допустим, что мужику удалось найти лодку получше, и теперь она выдерживает не один объект, а два (не считая мужика).
В этом случае алгоритм таков:
- Крестьянин берёт с берега А в лодку волка и капусту. Коза остаётся на берегу А.
- Крестьянин едет с берега А на берег Б вместе с волком и капустой.
- Добравшись до берега Б, крестьянин высаживает из лодки на берег Б оба объекта: и волка, и капусту.
- Крестьянин едет с берега Б на берег А один.
- Добравшись до берега А, крестьянин сажает с берега А себе в лодку козу.
- Крестьянин едет с берега А на берег Б вместе с козой.
- Добравшись до берега Б, крестьянин наконец-то высаживается из лодки на берег Б сам. После этого крестьянин благополучно высаживает из лодки на берег Б козу.
Как видите, в данном случае понадобилось совершить всего лишь три переправы (пункты 2, 4, 6).
Ещё один вариант упрощения задачи: если бы мужик был догадлив, он мог бы (прежде чем делать переправы) надеть намордники на волка и на козу. В этом случае волка уже можно оставить с козой, а козу с капустой. Алгоритм для данного случая писать не буду, поскольку он прост и очевиден.
В своё время я читал эту задачу в индийском варианте. Вместо волка там лев, вместо козы — лань, а вместо кочана — благородная Трава Жизни. Алгоритм, естественно, такой же, как и в русской задаче.
