Волк, коза́ и капу́ста [1] [2] [3] [4] — классическая головоломка на пересечение реки [en] . Головоломка возникла не позже IX века [5] [3] [6] и под разными названиями вошла в фольклор ряда этнических групп [7] [8] .
Содержание
Сюжет [ править | править код ]
Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.
Как крестьянину перевезти на другой берег всё своё имущество в целости и сохранности? [1] [3]
Решение [ править | править код ]
Первым шагом решения должна быть перевозка козы, так как любой другой вариант приведёт к потере части имущества. Вернувшись, крестьянин перевозит капусту (или волка) на другой берег, а козу увозит обратно. Оставляя козу на первом берегу, крестьянин перевозит волка (или капусту) на другой берег, после чего возвращается, чтобы забрать козу [9] [10] .
- Перевезти козу
- Вернуться
- Перевезти волка (или капусту)
- Вернуться с козой
- Перевезти капусту (или волка)
- Вернуться
- Перевезти козу
Упоминания и вариации [ править | править код ]
Головоломка принадлежит к числу задач о переправе [en] [2] [6] (ferry-boat problems [11] , river-crossing puzzle), где задача состоит в том, чтобы перевезти набор предметов через реку с заданными ограничениями. В первом известном упоминании этой головоломки, в средневековом манускрипте Propositiones ad Acuendos Juvenes [en] («Задачи для развития молодого ума» [6] ), имуществом крестьянина являются волк, коза и капуста. Существуют «косметические» вариации головоломки, в которых фигурируют волк, овца и капуста [12] [7] , p. 26 , лиса, курица и зерно [13] , лиса, гусь и бобы [14] , пантера, свинья и овсянка [15] . Логика головоломки не меняется: есть три предмета A, B, C, таких, что нельзя оставить без присмотра A с B или B с C.
В Европе широкую популярность задача получила после издания сборника занимательных задач, приписываемого Алкуину (лат. Propositiones ad Acuendos Juvenes , VIII век). Задача была любимой головоломкой Льюиса Кэрролла [18] и многократно перепечатывалась в сборниках занимательной математики [6] [7] , p. 26. .
Упоминания головоломки присутствуют в игре Nintendo DS Professor Layton and the Curious Village и в мультсериале «Симпсоны» (13 эпизод 20 сезона «Gone Maggie Gone»), где Гомер должен пересечь реку с Мэгги, собакой и банкой крысиного яда.
Упоминание присутствует в сериале «Фарго» 1 сезон 9 серия.
В некоторых областях Африки были обнаружены вариации головоломки, в которых лодка может вместить в себя два объекта, помимо человека. Когда головоломка подобным образом ослаблена, можно ввести дополнительное ограничение, заключающееся в том, что никакие два объекта не могут быть оставлены на берегу вместе [7] , p. 27. .
“Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или волк, или коза, или капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?”
Словесный способ алгоритма решения задачи 1:
вернуться к волку и капусте
перевезти волка к козе
перевезти козу к капусте
перевезти капусту к волку
Словесный способ не имеет широкого распространения в информатике:
такие описания строго не формализуемы;
страдают многословностью записей;
допускают неоднозначность толкования отдельных предписаний.
Словесно-формульный способ записи алгоритмов использует ограниченный набор слов и математические формулы. Алгоритм разбивается на шаги, т.е. структурируется. Его часто называют структурированным или пошаговым.
Рассмотрим этот способ записи алгоритма на примере нахождения действительных корней полного квадратного уравнения:
Задача 2. Решить квадратное уравнение: a·x 2 +b·x + c = 0.
Исходными данными для алгоритма являются коэффициенты a, b, с. Причем a≠0 и b≠0. Результат: два или ни одного действительных корней.
Словесно-формульный способ записи задачи 2:
1) Задать (численные значения коэффициентов) a, b, c.
2) Вычислить (дискриминант): .
3) Если D≥0, то вычислить (действительные корни по формулам)
Иначе «Записать ответ: нет действительных корней».
4) Закончить решение.
Такой способ записи алгоритма очень часто используется в математике для описания небольших алгоритмов и совмещает использование определенного набора слов.
Одним из его недостатков является то, что для сложных задач трудно увидеть структуру алгоритма (нет наглядности). Этот недостаток преодолен в графическом (блок-схемном) способе описания алгоритма. Рассмотрим его.
На языке блок-схем каждый шаг алгоритма описывается с помощью соответствующей фигуры, а последовательность выполнения шагов определяется линиями-связями.
Блок схемы читаются сверху вниз и слева направо. Блок-схемы полезны тем, что обеспечивают легкую «читаемость» алгоритма. Они, как и любые схемы, наглядны.
Однако это не всегда так: стоит попытаться нарисовать блок-схему для более-менее сложного алгоритма, как она разрастается до невероятных размеров и теряет все свое наглядное преимущество. Поэтому блок-схемы хороши в структурном программировании для описания коротких алгоритмов. Язык блок-схем прост (хотя существуют его расширенные варианты):
Блок вычислений (вычислительный блок)
Вычислительные действия или последовательность действий
Логический блок (блок условия)
Выбор направления выполнения алгоритма в зависимости от некоторого условия
Блок ввода-вывода данных
Общее обозначения ввода (вывода) данных (вне зависимости от физического носителя)
Начало или конец алгоритма, вход или выход в подпрограмме
Процесс пользователя (подпрограмма)
Вычисление по стандартной программе или подпрограмме
Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма
Переход к следующему блоку
Вывод: Алгоритмизация — один из основных этапов решения задач с помощью компьютера. Понятие алгоритма является достаточно «молодым» и дополняется по мере использования его в сфере информационных технологий и программирования, не смотря на то, что в математике оно было известно еще до нашей эры. При описании свойств алгоритма разные авторы используют множество подходов и классификаций. Мы попытались обобщить их и выделить наиболее значимые: детерминированность, дискретность, конечность, массовость и результативность. Среди множества способов описания алгоритмов самым наглядным является графический метод, который реализуется с помощью блок-схемы алгоритма.
Волк, коза и капуста. На берегу реки стоит крестьянин с лодкой, а рядом с ним находятся волк, коза и капуста.
Крестьянин должен переправиться сам и перевезти волка, козу и капусту на другой берег. Однако в лодку кроме крестьянина помещается либо только волк , либо только коза, либо только капуста.
Оставлять же волка с козой или козу с капустой без присмотра нельзя — волк может съесть козу, а коза — капусту.
Как должен вести себя крестьянин?
Решение задачи Волк, коза и капуста
В данной задаче крестьянин может следовать одному из двух алгоритмов:
Алгоритм 1
1) сначала переправляются крестьянин и коза
2) крестьянин оставляет козу и возвращается обратно
3) крестьянин переправляет волка
4) крестьянин возвращается с козой
5) крестьянин переправляет капусту
6) крестьянин возвращается один
7) крестьянин забирает козу и отправляется на другой берег
Алгоритм 2
1) сначала переправляются крестьянин и коза
2) крестьянин оставляет козу и возвращается обратно
3) крестьянин переправляет капусту
4) крестьянин возвращается с козой
5) крестьянин переправляет волка
6) крестьянин возвращается один
7) крестьянин забирает козу и отправляется на другой берег