Автор: Админка

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


Ответ на задачу про волка, козу и капусту.

Задача про волка, козу и капусту – одна из самых известных и популярных задач о переправе. В данной статье мы разберём решение данной задачи.

Формулировка.

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

Решение.

Стоит сразу заметить, что коза взаимодействует сразу с двумя объектами: и волком, и капустой. Поэтому первой с собой стоит взять именно её.

  • Берём козу и перевозим её на другой берег, высаживаем.
  • Возвращаемся обратно, берём волка и перевозим его на другой берег.
  • Высаживаем волка, забираем козу и везём её обратно.
  • Высаживаем козу, забираем капусту и везём её на другой берег.
  • Высаживаем капусту и возвращаемся обратно, берём козу и везём её на другой берег
  • Высаживаем козу – все в сборе.

У этой задачи есть и другой не очень принципиально отличающееся решение: капусту и волка можно поменять местами. Основная идея – не оставлять козу с волком или капустой.

Похожие статьи

Задача на переправу Волк, коза и капуста

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

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

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

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

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

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

Алгоритм 1

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

Алгоритм 2

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

Перевозим волка, козу и капусту через реку с эффектами на Haskell / Хабр

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

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

Начнем с самого простого — маршрута перемещений. Так как мы не знаем заранее, через какое гарантированное количество шагов мы получим решение, можно построить бесконечный маршрут, все равно мы будем вычислять его лениво:

data Direction = Back | Forward route :: [Direction] route = iterate alter Forward alter :: Direction -> Direction alter Back = Forward alter Forward = Back 

Так как мы собираемся построить обобщенное решение, то и абстрагируемся от персонажей тоже. Мы построим нетранзитивное симметричное отношение порядка между элементами множества персонажей (поделитесь в комментариях, если для этого есть свое устоявшееся название):
data Character = Wolf | Goat | Cabbage deriving Eq class Survivable a where survive :: a -> a -> Ordering instance Survivable Character where survive Wolf Goat = GT survive Goat Wolf = LT survive Goat Cabbage = GT survive Cabbage Goat = LT survive _ _ = EQ 

Зачем вообще использовать эффекты? Эффекты помогают бороться со сложностью, которая присуща любой предметной области. Значит, для того, чтобы определить какие эффекты использовать для решения головоломки, стоит подумать над тем, с какими сложностями мы можем столкнуться, когда попробуем описать решение задачи с помощью кода:
  • Чтобы найти решение, при котором все персонажи будут перевезены на противоположный берег, надо перебрать много вариантов перестановок. Для этого мы будем использовать эффект множественности, которого можно добиться с помощью обычного списка.
  • Еще нам нужно запоминать местоположение персонажа, чтобы проверять условия совместимости с другими персонажами (волк ест козу, коза ест капусту) и кого можно посадить на лодку. Мы можем хранить состав двух берегов type River a = ([a],[a]) c помощью эффекта состояния State (River a).
  • Лодка может взять кого-нибудь на борт, а может и не брать — тут нам пригодится эффект частичности с Maybe.

В коде я буду использовать свою экспериментальную библиотеку joint (на Хабре есть две статьи, объясняющие ее суть — первая и вторая), но при желании решение можно перенести на transformers или mtl.

Итак, у нас есть три разрозненных эффекта: состояние, множественность, частичность. Теперь надо решить, как мы собираемся их скомпоновать между собой:

  • В аппликативной/монадной цепочке вычислений для Maybe, если мы где-то получили Nothing, то и результат всего вычислений будет Nothing. Мы оставим его отдельно, так как не хотим, чтобы при отправлении пустой лодки (без персонажа, крестьянина мы не учитываем) мы потеряли весь прогресс в нахождении решения.
  • Каждый последующий выбор хода (эффект множественности) должен опираться на состав текущего берега (эффект состояния), так как мы не можем взять персонажа в лодку, если она находится на другом берегу. Следовательно, нам нужно эти эффекты сцепить в трансформер: State (River a) :> [].

Один ход в головоломке можно описать как последовательность действий:
  1. Получить состав персонажей на текущем берегу
  2. Выбрать следующего персонажа для транспортировки
  3. Переместить персонажа на противоположный берег
step direction = bank >>= next >>= transport

Давайте пройдемся по каждому шагу подробнее.

В зависимости от направления перемещения лодки, применяем линзу для источника отправления к состоянию всей реки и получаем состав текущего берега:

bank :: (Functor t, Stateful (River a) t) => t [a] bank = view (source direction) <$> current 

Выбор следующего персонажа происходит так: получая набор персонажей с берега (предыдущее выражение bank), мы формируем пространство выбора, добавляя к этому самому пространству пустую лодку:

\xs -> Nothing : (Just <$> xs) 

Для каждого кандидата (пустая лодка (Nothing) — тоже кандидат) проверяем чтобы на оставшемся берегу не оставалось персонажей, которые были бы не прочь полакомиться друг другом:

valid :: Maybe a -> Bool valid Nothing = and $ coexist <$> xs <*> xs valid (Just x) = and $ coexist <$> delete x xs <*> delete x xs coexist :: Survivable a => a -> a -> Bool coexist x y = survive x y == EQ 

И когда мы отфильтровали пространство выбора персонажей, поднимаем эффект множественности и возвращаем каждый элемент из этого пространства выбора:

next :: (Survivable a, Iterable t) => [a] -> t (Maybe a) next xs = lift . filter valid $ Nothing : (Just <$> xs) 

Остался последний шаг — фактическая транспортировка c помощью линз: удаляем персонажа с берега отправки и добавляем к берегу назначения:

leave, land :: River a -> River a leave = source direction %~ delete x land = target direction %~ (x :) 

Если в лодке был персонаж — изменяем состояние реки, иначе ход был холостым:

transport :: (Eq a, Applicative t, Stateful (River a) t) => Maybe a -> t (Maybe a) transport (Just x) = modify @(River a) (leave . land) $> Just x where transport Nothing = pure Nothing 

Было бы неплохо посмотреть на работу программы в действии. Для нахождения решения нам нужно как минимум совершить семь шагов по маршруту:

start :: River Character start = ([Goat, Wolf, Cabbage], []) solutions = run (traverse step $ take 7 route) start 

И у нас есть два решения:

Полные исходники можно посмотреть здесь.

Сделаем игру Волк-Коза-Капуста

Нашел замечательную статью “Самостоятельное изучение схемотехники. Синтез автоматов на триггерах. Часть 1” на Хабре. В статье рассматривался интересный пример создания игры «Волк-Коза-Капуста».
Попробую объяснить суть дела.

Задача: На одном берегу реки находятся крестьянин, волк, коза и капуста. У крестьянина есть лодка, но видимо не очень хорошая  Он может взять с собой в плавание только один «предмет», в смысле только козу или только капусту или только волка. Проблема в том, что кое-кого нельзя оставлять наедине с желанной пищей. Например, нельзя уплыть оставив волка и козу на одном берегу – волк съест козу. Или нельзя уплыть с волком, оставив козу и капусту – ведь коза съест капусту. Но крестьянину нужно непременно попасть на другой берег. Вот такой он упертый. И хочет он довезти всех в сохранности.


Вообще-то это довольно известная детская головоломка.


Автор той статьи предлагает использовать «граф автомата Мура» для описания этой системы из волка-козы-капусты и крестьянина. Ну что же – в этом наверное есть какая-то здравая мысль.

Для хранения состояния системы используется четырех-битное слово. По одному биту на каждого: на козу (бит 3), на волка (бит 2), капусту (бит1) и крестьянина (бит 0). Если бит равен единице, то сущность на первом берегу, а если нулю, то на втором.

Кроме этого, в той статье автор определяет четыре «события» по которым система переходит из одного состояния в  другое:
1)    событие А1 – крестьянин везет козу
2)    событие А2 – крестьянин везет волка
3)    событие А3 – крестьянин везет капусту
4)    событие А4 – крестьянин перебирается сам на другой берег

После всех этих определений автором статьи был автором нарисован следующих граф:

Вообще прочитав статью и внимательно изучив этот граф мне немедленно захотелось попробовать реализовать эту игру «в железе». Тем более, что делать мне по большому счету почти ничего не надо – ведь у меня есть плата Марсоход и она очень подходит для этой игры.

Порылся в интернете и нашел несколько картинок коз, капуст, волков и крестьян. Выбрав более подходящие собрал их на одной картинке и напечатал на принтере вот так:

Потом наклеил эту картинку на картонку вырезал по контуру и двумя коротенькими шурупами привинтил плату Марсоход к картонке. Получилось вот так:

Идея в следующем. На плате Марсоход есть 8 светодиодов. Мысленно делим их на две группы. Первые четыре светодиода отображают присутствие сущностей на левом берегу, а правые четыре светодиода отображают присутствие сущностей на правом берегу. Понятно, что правые светодиоды это просто инверсия левых. Так нагляднее будет игра.

Опять же удобство – на плате Марсоход как раз четыре кнопочки – к ним привязываем «события» - перемещения сущностей. Под кнопочкой нарисована картинка обозначающая кого «перевозит» эта кнопка. Ну вот и все! Собственно аппаратура готова! Паять ничего не нужно. У нас есть ПЛИС на плате Марсоход. Осталось все это запрограммировать. Поскольку граф уже был любезно составлен автором той замечательной статьи, то казалось, что запрограмировать будет легко. Вроде бы думать уже не надо.

Вот тут и началось самое интересное. На самом деле есть большая разнича между теоретическими изысканиями и практическая реализацией. Попробую объяснить мои проблемы и проблемки с существующим графом:

  • В существующем графе исходное состояние это 0000, что в принятой терминологии обозначает, что все сущности изначально находятся на том правом берегу. Как-то это странно.
  • Любое событие А1-А4 перевозит всех сразу на левый берег с правого из состояния 0000 в состояние 1111. Тоже странно.
  • Нет явного состояния «выиграл» или «проиграл». На графе проигрыш переводит всех сущностей сразу на правый берег в состояние 0000, что как бы обозначает «выиграл». Ну и как это?
  • В статье говорится о четырех проигрышных ситуациях 0011\1100, 1010\0101, на само же деле их шесть. Есть еще две проигрышные ситуации 1110\0001 – это когда крестьянин оставляет все свое хозяйство и плывет сам. Коза съедает капусту, а потом волк козу.

Несмотря на то, что первую версию игры по существующему графу я сделал довольно быстро, как оказалось, пользоваться этим практически нельзя. Игра получилась совсем непонятная.

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

Теперь про мой "новый" граф автомата Мура. Исходное состояние игры 0000 и это обозначает, что все сущности на первом левом берегу. Единица в бите состояния обозначает, что соответствующая сущность находится на правом берегу. Имеем одно выигрышное состояние 1111 и шесть проигрышных. И сущностей и события именуем в одинаковой последовательности, а не так как было раньше. Тоесть в слове состояния Коза – бит ноль. Событие по перевозке Козы – тоже бит ноль в слове событий (то есть кнопочка ноль).
Вообще, в нашем проекте, который я пишу на языке Verilog примем следующие обозначения битов в слове состояния и в слове событий:

parameter GOAT = 0;
parameter CABBAGE = 1;
parameter WOLF = 2;
parameter MEN = 3;

Вот так выглядит мой граф:

Теперь уже по новому графу пишем на языке Verilog описание логики работы нашего автомата. Полный текст получившейся «программы» можно взять здесь.

Несмотря на то, что проект заработал правильно (с моей точки зрения), все равно осталось какое-то чувство неудовлетворенности. Я еще когда писал весь этот код на Verilog видел, что получается как-то «тяжеловесно».

На самом деле вся логика может быть гораздо проще. Попробую объяснить свою мысль. В данном конкретном примере не нужно ломать голову всеми этими «автоматами». Составление такого графа подразумевает четкое представление какие вообще состояния есть и их трансформации. А собственно говоря зачем все это?

Понятно, что любое событие по перевозке, во-первых, обязательно приводит к перемещению крестьянина на противоположный берег. Тоесть, каждое событие всегда «инвертирует» бит состояния крестьянина. Во-вторых, сущности Коза, Капуста и Волк могут перемещаться только если перед событием они с крестьянином находятся на одном берегу.  Перемещение всех сущностей – это инвертирование их бита состояния. Распознавание «аварийных ситуаций», тоесть проигрышей, это отдельная песня. Проигрыши распознаются отдельной

Pers.narod.ru. Алгоритмы. Волк, коза и капуста

Pers.narod.ru. Алгоритмы. Волк, коза и капуста

Этот сайт больше не обновляется. Подключите Javascript, чтобы увидеть новый адрес страницы или перейдите к статье

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

Задача очень проста, если учесть, что перевозить объекты можно не только "туда", но и "обратно". Второе соображение - существует единственное "безопасное" сочетание двух объектов из трех - волк и капуста.

Поэтому решение таково:


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

Шаги 3) и 5) можно поменять местами.


1. Есть исполнитель «Перевозчик», который перевозит через реку волка, козу и капусту. Напишите алгоритм с обязательным

1. Задача про волка, козу и капусту имеет решение, когда коза перевозится дважды. Первую подпрограмму создаем для перевозки козы, назовем ее ПП1.
ПП1
ВЗЯТЬ КОЗУ
ПЕРЕПЛЫТЬ
ВЫСАДИТЬ

Вторая подпрограмма ПП2 - из двух команд: ПЕРЕПЛЫТЬ и ВЫСАДИТЬ.

Алгоритм выглядит так:

НАЧ
   Делай ПП1
ПЕРЕПЛЫТЬ
ВЗЯТЬ ВОЛКА
   Делай ПП2
ВЗЯТЬ КОЗУ
   Делай ПП2
ВЗЯТЬ КАПУСТУ
   Делай ПП2
   Делай ПП1
КОН

2. Анализ команд показывает, что повторяются 2 блока команд: 2 шага и 3 поворота, затем 2 шага и 3 прыжка. Значит, будет две подпрограммы, назовем их соответственно Повороты и Прыжки.

Алгоритм будет выглядеть так:
НАЧ
   Делай Повороты
   Делай Прыжки
   Делай Повороты
   Делай Прыжки
   Делай Повороты
   Делай Прыжки
   Делай Повороты
   Делай Прыжки
КОН

Алгоритм

- Фермер, волк, коза и капуста Поиск в ширину и в глубину в Java

Переполнение стека
  1. Около
  2. Продукты
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
.

Решение проблемы с волком, козой и капустой (форум Programming Diversions на Coderanch)

Нет, Джим Инст, вам не нужно думать о том, что происходит, когда фермер переходит реку, или о том, что делает лодка; вы просто предполагаете, что лодка находится там, где находится фермер. На самом деле я получил 16 возможных состояний, пронумерованных от 0 до f, где самый старший бит (3-й бит = 8) представляет фермера, 2-й бит = 4 - это волк, 1-й бит = 2 - это гусь, а 0- -й бит (младший бит = 1) представляет собой зерно капусты или что-то еще.

Итак, f означает, что все четверо находятся на этой стороне реки, 0 означает, что все четыре пересеклись, 1 означает, что капуста одна на этой стороне реки, 2 означает, что гусь один на этой стороне реки и т. Д. можно считать, что это означает, что дополнение числа находится на другой стороне реки, поэтому 0 означает f на другой стороне. Тогда у вас будет инвариант thisSide + thatSide == 0xf.
По эту сторону реки есть три запрещенных штата: 3, 6, 7, где гусь ест капусту, лес - козу, или и то, и другое.Это означает, что на другой стороне есть три запрещенных состояния, 8 9 и c. Мы знаем, что 8 + 7 или 9 + 6 или c + 3 в сумме дают 0xf. Остается в общей сложности 10 разрешенных состояний. За каждым разрешенным состоянием могут следовать 1, 2 или 3 разрешенных состояния-преемника.

Правила таковы, что фермер должен переходить дорогу каждый раз в одиночку или в сопровождении одного предмета. Это эквивалентно побитовой операции XOR 8 9 a или c; если у вас есть переменные thisSide и thatSide, то одна и та же операция должна быть применена к обеим сторонам, чтобы сохранить инвариант класса.Также вы удаляете из результатов любое из шести запрещенных состояний.
Вы можете вернуть состояния обратно на английский с помощью поразрядного И: private final int FARMER = 8, WOLF = 4, GOOSE = 2, CABBAGE = 1; . . . . если (состояние и ФЕРМЕР> 0) outputString + = "фермер"; если (состояние & WOLF> 0) outputString + = "волк"; и т. д.

Затем вы получаете дерево, начинающееся с f, и затем вы выполняете поиск дерева, пока не найдете в нем 0. Для достижения 0 требуется ровно 7 операций, первая из которых - состояние ^ = FARMER + GOOSE;

*********************************************** ***************************
В LISP он читает что-то вроде этого, если ваш алгоритм поиска по ширине и оператор -> уже поставлено: (defparameter * farmer * '((fwgcR wcRfg) (fwgRc wRfgc gRfwc) (fwcRg wcRfg wRfgc cRfwg) (fgcRw gRfwc cRfwg) (fgRwc gRfwc Rfwgc) (wcRfg fwcRg fwgcR) (gRfwc fgRwc fwgRc fwcRg) (cRfwg fwcRg fgcRw) (wRfgc fwgRc fwcRg) (Rfwgc fgRwc))) (defun farmer-lmg (состояние) (-> * фермер * штат)) (width-search 'fwgcR' Rfwgc # 'farmer-lmg) Аббревиатуры (очевидно) означают фермерскую волчью гусиную капусту и РЕКУ; те, кто до R, находятся на этой стороне, а те, что после R, находятся на этой стороне.Бит defun создает генератор легального хода (LMG).
*********************************************** **************************
С предоставленными нами утилитами LISP он работает, но, кажется, всегда дает мне один и тот же ответ . Я думаю, есть 4 возможных решения, но первая операция всегда заключается в том, что фермер переносит гуся, а четвертая операция всегда возвращает гуся.

[править] Незначительные орфографические исправления и значение lmg [/ править]
[30 ноября 2007 г .: Сообщение отредактировал: Кэмпбелл Ричи]

.Оптимизация

- Транспортировка лисы, козы и капусты - Stack Overflow

Переполнение стека
  1. Около
  2. Продукты
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
  5. Реклама Обратитесь к разработчикам и технологам со всего мира
  6. О компании
.

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

Загадка:
Шел человек с козой, волком и капустой на рынок, и ему нужно было перейти реку. Его лодка могла нести только две вещи (включая его самого). Его проблема заключалась в том, что если он сначала съел капусту, то волк съел бы козу. Но если он взял волка и оставил козу и капусту, то коза съела бы их. Как он переправил всех троих через реку, не оставив никого из них?

Ответ:
Сначала он взял козу, потому что знал, что волк не будет есть капусту.Затем он схватил волка, но на обратном пути он взял с собой козу. Он спустил козу, взял кочаны и оставил их волку, а затем вернулся и велел козе принести его.
Показать ответ Скрыть ответ ПОДЕЛИТЬСЯ Человек, коза, волк и капуста Загадка мем с загадкой и ссылкой на страницу ответа. .

Волк, коза и капуста

Это не только новая игра. Это тоже загадка. Надо сказать, что это очень известная головоломка.
Волк, козел и кочан на берегу реки. Недалеко от них есть лодка. Им нужно переплыть реку и добраться до другого берега реки. Но только один из них может пользоваться лодкой одновременно. Цель головоломки - перенести волка, козу и кочан на другой берег реки, и все они должны быть в безопасности.Это довольно сложно, потому что, если вы оставите волка и козу на одном берегу реки, волк съест козу. Если оставить козу и кочан вместе, коза съест капусту. Это очень интересная логическая головоломка.
Уважаемые родители, не торопитесь и не пытайтесь помочь своим детям! Неплохо, если они не могут сразу ответить на этот вопрос. Головоломка для них не очень сложная. Единственное, что им нужно, - это немного подумать.

.

Смотрите также


Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.



Понравился рецепт? Подпишись на RSS! Подписаться!