Алгоритм волк коза и капуста

Волк, коза́ и капу́ста [1] [2] [3] [4] — классическая головоломка на пересечение реки [en] . Головоломка возникла не позже IX века [5] [3] [6] и под разными названиями вошла в фольклор ряда этнических групп [7] [8] .

Содержание

Сюжет [ править | править код ]

Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.

Как крестьянину перевезти на другой берег всё своё имущество в целости и сохранности? [1] [3]

Решение [ править | править код ]

Первым шагом решения должна быть перевозка козы, так как любой другой вариант приведёт к потере части имущества. Вернувшись, крестьянин перевозит капусту (или волка) на другой берег, а козу увозит обратно. Оставляя козу на первом берегу, крестьянин перевозит волка (или капусту) на другой берег, после чего возвращается, чтобы забрать козу [9] [10] .

  1. Перевезти козу
  2. Вернуться
  3. Перевезти волка (или капусту)
  4. Вернуться с козой
  5. Перевезти капусту (или волка)
  6. Вернуться
  7. Перевезти козу

Упоминания и вариации [ править | править код ]

Головоломка принадлежит к числу задач о переправе [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:

вернуться к волку и капусте

перевезти волка к козе

перевезти козу к капусте

перевезти капусту к волку

Словесный способ не имеет широкого распространения в информатике:

такие описания строго не формализуемы;

страдают многословностью записей;

допускают неоднозначность толкования отдельных предписаний.

Словесно-формульный способ записи алгоритмов использует ограниченный набор слов и математические формулы. Алгоритм разбивается на шаги, т.е. структурируется. Его часто называют структурированным или пошаговым.

Рассмотрим этот способ записи алгоритма на примере нахождения действительных корней полного квадратного уравнения:

Читайте также:  Стабилизатор напряжения 7805 схема включения

Задача 2. Решить квадратное уравнение: a·x 2 +b·x + c = 0.

Исходными данными для алгоритма являются коэффициенты a, b, с. Причем a≠0 и b≠0. Результат: два или ни одного действительных корней.

Словесно-формульный способ записи задачи 2:

1) Задать (численные значения коэффициентов) a, b, c.

2) Вычислить (дискриминант): .

3) Если D≥0, то вычислить (действительные корни по формулам)

Иначе «Записать ответ: нет действительных корней».

4) Закончить решение.

Такой способ записи алгоритма очень часто используется в математике для описания небольших алгоритмов и совмещает использование определенного набора слов.

Одним из его недостатков является то, что для сложных задач трудно увидеть структуру алгоритма (нет наглядности). Этот недостаток преодолен в графическом (блок-схемном) способе описания алгоритма. Рассмотрим его.

На языке блок-схем каждый шаг алгоритма описывается с помощью соответствующей фигуры, а последовательность выполнения шагов определяется линиями-связями.

Блок схемы читаются сверху вниз и слева направо. Блок-схемы полезны тем, что обеспечивают легкую «читаемость» алгоритма. Они, как и любые схемы, наглядны.

Однако это не всегда так: стоит попытаться нарисовать блок-схему для более-менее сложного алгоритма, как она разрастается до невероятных размеров и теряет все свое наглядное преимущество. Поэтому блок-схемы хороши в структурном программировании для описания коротких алгоритмов. Язык блок-схем прост (хотя существуют его расширенные варианты):

Блок вычислений (вычислительный блок)

Вычислительные действия или последовательность действий

Логический блок (блок условия)

Выбор направления выполнения алгоритма в зависимости от некоторого условия

Блок ввода-вывода данных

Общее обозначения ввода (вывода) данных (вне зависимости от физического носителя)

Начало или конец алгоритма, вход или выход в подпрограмме

Процесс пользователя (подпрограмма)

Вычисление по стандартной программе или подпрограмме

Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма

Переход к следующему блоку

Читайте также:  Игры на двоих ios на двух устройствах

Вывод: Алгоритмизация — один из основных этапов решения задач с помощью компьютера. Понятие алгоритма является достаточно «молодым» и дополняется по мере использования его в сфере информационных технологий и программирования, не смотря на то, что в математике оно было известно еще до нашей эры. При описании свойств алгоритма разные авторы используют множество подходов и классификаций. Мы попытались обобщить их и выделить наиболее значимые: детерминированность, дискретность, конечность, массовость и результативность. Среди множества способов описания алгоритмов самым наглядным является графический метод, который реализуется с помощью блок-схемы алгоритма.

Волк, коза и капуста. На берегу реки стоит крестьянин с лодкой, а рядом с ним находятся волк, коза и капуста.

Крестьянин должен переправиться сам и перевезти волка, козу и капусту на другой берег. Однако в лодку кроме крестьянина помещается либо только волк , либо только коза, либо только капуста.

Оставлять же волка с козой или козу с капустой без присмотра нельзя — волк может съесть козу, а коза — капусту.

Как должен вести себя крестьянин?

Решение задачи Волк, коза и капуста

В данной задаче крестьянин может следовать одному из двух алгоритмов:

Алгоритм 1

1) сначала переправляются крестьянин и коза
2) крестьянин оставляет козу и возвращается обратно
3) крестьянин переправляет волка
4) крестьянин возвращается с козой
5) крестьянин переправляет капусту
6) крестьянин возвращается один
7) крестьянин забирает козу и отправляется на другой берег

Алгоритм 2

1) сначала переправляются крестьянин и коза
2) крестьянин оставляет козу и возвращается обратно
3) крестьянин переправляет капусту
4) крестьянин возвращается с козой
5) крестьянин переправляет волка
6) крестьянин возвращается один
7) крестьянин забирает козу и отправляется на другой берег