Задача про вовка, козу і капусту – одна з найвідоміших і популярних завдань про переправу. У даній статті ми розглянемо рішення цієї задачі.
Формулювання.
Одного разу селянинові знадобилося перевезти через річку вовка, козу і капусту. У селянина є човен, в якому може поміститися, крім самого селянина, тільки одна істота або предмет — або вовк, або коза, або капуста. Якщо селянин залишить без нагляду вовка з козою, то вовк з’їсть козу; якщо селянин залишить без нагляду козу з капустою, коза з’їсть капусту. Як селянину перевезти на інший берег все своє майно в цілості й схоронності?
Рішення.
Варто відразу зауважити, що коза взаємодіє відразу з двома об’єктами: і вовком, і капустою. Тому першою з собою варто взяти саме її.
- Беремо козу і перевозимо її на інший берег, висаджуємо.
- Повертаємося назад, беремо вовка і перевозимо його на інший берег.
- Висаджуємо вовка, забираємо козу і веземо її назад.
- Висаджуємо козу, забираємо капусту і веземо її на інший берег.
- Висаджуємо капусту і повертаємося назад, беремо козу і веземо її на інший берег
- Висаджуємо козу – всі в зборі.
У цій задачі є й інший не дуже принципово відмінне рішення: капусту і вовка можна поміняти місцями. Основна ідея – не залишати козу з вовком або капустою.
