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

Логическая задача про капусту волка и козу


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

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

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

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

Решение.

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

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

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

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

Список задач MonadPlus и логики · в коде

Сегодня мы собираемся научиться решать классические и нестареющие логические задачи без каких-либо структур данных, кроме монадических свойств List в качестве MonadPlus!

Мы собираемся решить эту устаревшую логическую головоломку, которая, как утверждает Википедия, восходит к 9 веку:

У фермера есть волк, коза и капуста, которые он хочет переправить через реку. К сожалению, его лодка может нести с собой только одну вещь.Он не может оставить волка наедине с козой, иначе волк съест козу. Он не может оставить козу одну с капустой, иначе коза ее съест. Как он может правильно перевезти свои вещи на другую сторону по одному, без каких-либо бедствий?

Мы предполагаем, что у вас есть базовое знакомство с концепциями функционального программирования и базовое понимание монад (если вы этого не знаете, ознакомьтесь с большим кратким руководством adit). Если вы не знакомы с MonadPlus / Alternative (и как они работают как монады), ознакомьтесь с Частью 1 и Частью 2, которые должны предоставить всю справочную информацию и большую часть синтаксиса.Большая часть синтаксиса Haskell объясняется либо здесь, когда мы дошли до него, либо в предыдущих частях. Тем не менее, если у вас есть какие-либо вопросы, не стесняйтесь оставлять комментарии, быстро прочитать Learn You A Haskell или зайти в дружелюбный #haskell от freenode!

Обзор MonadPlus

Полезность монады зависит от того, как вы определяете характерное поведение «связывание» или «сцепление». В этой статье MonadPlus относится к шаблону проектирования (и классу типов Haskell), в котором вы моделируете эту «цепочку» как процесс «успех / неудача».

Существует общий язык, с которым можно говорить об этом процессе: mzero означает «сбой здесь», а return x означает «успех со значением x здесь». Таким образом, цепочка реализована таким образом, что цепочка чего-либо до отказа будет распространять этот сбой вперед. То есть mzero >> return x = mzero .

Наш подход

Итак, вооружившись тем, что мы узнали из части 2, давайте сформулируем общий план поиска всех решений за n ходов.

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

С монадой List мы говорим: «Вот описание - (одиночного) путешествия. Какие путешествия по этому описанию успешны? »

Так чем же могло быть это путешествие для нас? Что ж, мы думаем о путешествии в этой ситуации как о накоплении движений к плану.Мы начинаем с пустого плана («Ничего не делать»). Следующим шагом мы добавляем в наш план один ход (например, «Просто пошевелите лисой»). Затем на следующем шаге мы добавляем еще один ход («Сначала переместите лису, затем переместите фермера»).

  1. Начать с пустого плана; tabula rasa.
  2. Добавьте к нему законный и безопасный ход.
  3. Повторить шаг 2 n раз
  4. Неудача, если вы не решение; если да, то получится.

Просто, правда? Мы только что проложили путь единого плана , от его рождения до возможной смерти или вознесения.

Это самая важная особенность этого подхода: он позволяет описать одно путешествие в общих чертах, и List «автоматически» обнаружит все успешные поездки, соответствующие вашему шаблону. Вам никогда не придется беспокоиться об ансамбле или вручную выполнять явное ветвление или фильтрацию. Когнитивно, все, что вам нужно сделать, это написать одну историю . Всего один . В этом сила абстракции List Monad.

Наши типы

Первое, что мы делаем при написании любой программы на Haskell: определяем наши типы!

  данные Персонаж = Фермер | Волк | Коза | Капуста - 1 шт. извлечение (Show, Eq, Enum) newtype Move = Move Персонаж - 2 получение (уравнение) экземпляр Показать Переместить где - 3 show (MoveThe Farmer) = "F" show (MoveThe Wolf) = "W" show (MoveThe Goat) = "G" show (MoveThe Cabbage) = "C" type Plan = [Move] - 4 данные Позиция = Запад | Восток - 5 получение (Показать, уравнение)  
  1. Сначала мы определяем пронумерованный тип Character всех персонажей, с которыми мы будем работать: фермер, волк, коза и капуста.
  2. Затем мы определяем простой контейнер Move , который просто содержит символ. Движение Фермер будет представлять движение только фермера, движение Волк будет представлять движение фермера и волка и т. Д.
  3. Для упрощения отладки мы собираемся определить наш собственный экземпляр Show для ходов, чтобы мы могли использовать для них print .
  4. Синоним простого типа; Plan - это просто список Move s.Обратите внимание, что мы не используем этот список как MonadPlus - это просто глупый список ходов в нашем плане.
  5. A Позиция типа : либо на западном, либо на восточном берегу реки. Все начинают на западном берегу, и мы хотим, чтобы все они оказались на восточном берегу.

Добро пожаловать в Haskell!

Привет! Эти отступления «Добро пожаловать в Haskell» предназначены для людей, незнакомых с Haskell, в основном для синтаксиса Haskell. Если вы уже чувствуете себя комфортно, можете пропустить их.

Здесь много синтаксиса и концепций Haskell; в основном все, что мы делаем, - это объявляем новые типы.

  1. Мы заявляем, что Character является «либо» Farmer , Wolf , Goat или Cabbage . Это все равно, что сказать, что Bool либо False , либо True : на самом деле, вы можете определить свой собственный Bool примерно так: (или даже свой собственный Int )

      data Bool = False | Правда данные Int = -536870912... | -1 | 0 | 1 | 2 | ... 536870911  

    Синтаксис вывода сообщает компилятору автоматически выводить функции для печати типа (Показать), проверки на равенство (Eq) и их перечисления (Enum)

  2. Мы объявляем новый тип Move , который представляет собой просто оболочку вокруг символа . Мы можем создать новый Move , используя MoveThe :

      ghci>: t MoveThe MoveThe :: Character -> Переместить ghci>: t MoveThe Wolf MoveThe Wolf :: Move  

    ( ghci> представляет команду в интерактивной подсказке ghci, а : t запрашивает тип всего, что идет после нее)

  3. Здесь мы определяем пользовательские функции для печати Move

  4. Вот синоним типа Plan .Каждый раз, когда мы используем Plan в качестве типа, мы действительно имеем в виду [Move] , и компилятор рассматривает эти две вещи как одно и то же.

  5. Позиция : то же самое, что и Персонаж .

Реализация

Последний шаг

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

Последний этап нашего путешествия - после того, как мы сделали все n ходов, мы заканчиваем путешествие, если это не решение.

.

Решение проблемы с волком, козой и капустой (форум 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 г .: Сообщение отредактировал: Кэмпбелл Ричи]

.

пролог - Переполнение стека в решателе для головоломки Wolf Goat Cabbage

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

Решение проблемы волчьей козьей капусты с помощью F # - статьи TechNet - США (английский)

Я изучаю язык F #. В рамках этого путешествия я решил написать решение проблемы волка, козы и капусты на F #.

Было немного сложно начать работу, потому что я просто не мог мыслить в терминах функционального программирования и F #. Эти две статьи помогли мне начать работу

http://www.paulbutcher.com/2007/09/escape-from-zurg/
http://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf

Мне тоже было трудно читать эти две статьи, потому что они написаны на Ruby и Haskell, но я получил общее представление о том, как построить решение таких проблем.

Моим первым шагом было составить список элементов, которые необходимо переместить с левого берега реки на правый, а также констант

1. let Items = [ «Волк» ; «Коза» ; «Капуста» ]

2.

3. let DeadlyCombinations = [ установить [ «Волк» ; «Коза» ]; комплект [ «Коза» ; «Капуста» ];]


Здесь Items - это просто список с 3 строками. DeadlyCombinations - это также список, состоящий из двух наборов. Эти наборы определяют предметы / животных, которых нельзя оставлять одних ни на одном берегу.

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

1. let isMoveDeadly list1 =

2. пусть listSet = комплект список1

3. List.exists (fun n -> n = listSet) DeadlyCombinations


Затем мне нужна логика для перемещения Предмета из левого берега в правый.для этого я написал метод MoveRight (означает перемещение объекта с левого берега на правый берег).

01. let rec MoveRight items =

02. сопоставить предметы с

03. | [] -> []

04. | голова :: хвост ->

05. если (isMoveDeadly tail), затем

06. MoveRight tail @ [голова]

07. еще

08. Console.WriteLine ( "Идет для перемещения » + головка)

09. хвост


здесь MoveRight - это имя функции. rec означает, что эта функция будет вызываться рекурсивно, и она принимает животных в качестве параметра.здесь вы можете видеть, что F # автоматически определяет тип животных, для которых я использую логику сопоставления. Тип, который для животных предполагается List.

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

Мы намерены двигать головой, только если хвост не смертельный. в противном случае нам нужно выбрать другой элемент из списка.

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

Если хвост не смертельный, то мы эффективно переместили головной элемент с левого берега на правый.

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

Иногда нам может потребоваться переместить предмет с правого берега реки на левый, потому что комбинация на правом берегу реки может оказаться смертельной

01. пусть MoveLeft животные =

02. let RightList = ListDiff animals Животные

03. let ShouldTakeAnimal = isMoveDeadly RightList

04. если (ShouldTakeAnimal), затем

05. let x = List.head RightList

06. Консоль.WriteLine ( "Переход к переместить " + x + " назад " )

07. [x]

08. еще

09. Console.WriteLine ( "Фермер идет только назад " )

10. []


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

Для этого мы пишем нашу функцию MoveLeft (переход от правого берега реки к левому)

Так как мы не создаем второй список для элементов на правом берегу реки, нам нужно взять разницу между основным списком элементов на top с текущим списком элементов на левом берегу, чтобы получить список элементов на правом берегу.Это делается с помощью следующих функция, которая используется в функции MoveLeft выше

1. let ListDiff list1 list2 = List.filter (fun n -> List.forall (fun x -> x <> n) список1) список2


Первый оператор if определяет, может ли фермер уйти один или он должен переместить предмет с правого берега на левый. это делается путем определения того, смертельна ли комбинация на правом берегу реки. если да, то фермер не может путешествовать один, и он должен взять с собой предмет.Если комбинация не смертельна, то фермер может путешествовать один.

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

01. let rec Решить направление животные =

02. сопоставьте животных с

03. | [] -> Console.WriteLine ( "Решено" )

04. | _ ->

05. направление совпадения с

06. | Влево -> Решить вправо (Перемещение животных вправо)

07. | Вправо -> Решить влево (животные @ (MoveLeft animals))


Здесь Solve - это рекурсивная функция, которая принимает два параметра: один - направление, а другой - список животных на левом берегу.Начнем с передачи всего списка элементов в качестве параметра.

Нам нужно создать размеченное направление с довольно простым

1. тип Направление =

2. | Левый

3. | Правый


Логика функции решения следующая.
если список животных слева пуст, загадка решена. если нет, то проверьте, где находится фермер, если фермер слева, затем переместите животное с левого берега на правый, вызвав MoveRight, и если фермер находится на правом берегу, затем вызовите функцию MoveLeft.(функция moveleft либо переместит фермера обратно на левый берег в одиночку ... или с животным, если комбинация окажется смертельной).

Наконец, мы вызываем нашу главную функцию в основном методе

1. []

2. let main args =

3. Решить Left Animals

4. 0


Результат программы:

Этот пример был хорош, потому что заставил меня подумать о
. 1.сопоставление с образцом
2. рекурсивное сокращение входного набора с помощью head :: tail
3. Разбиение ограничений задачи на мелкие функции.

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

Если вы хотите улучшить мой код для решения этой проблемы, не стесняйтесь редактировать эту страницу и улучшать код. вот весь листинг кода

открытая система

(*

Направление типа определяет, в каком направлении человек это настоящее время.

Слева означает, что Человек это присутствует на левой стороне берега.

Право означает человека это присутствует на правой стороне банка.

*)

тип Направление =

| Левый

| Правый

(*

Главный список животных

*)

let Животные = [ «Волк» ; «Коза» ; «Капуста» ]

let DeadlyCombinations = [ установить [ «Волк» ; «Коза» ]; комплект [ «Коза» ; «Капуста» ];]

пусть isMoveDeadly list1 =

пусть listSet = комплект список1

Список.существует (весело n -> n = listSet) DeadlyCombinations

let rec MoveRight animals =

соответствие животных с

| [] -> []

| голова :: хвост ->

если (isMoveDeadly tail), затем

MoveRight хвост @ [голова]

еще

Консоль.WriteLine ( «Собираюсь переехать» + головка)

хвост

let ListDiff list1 list2 = List.filter (fun n -> List.forall (fun x -> x <> n) list1) list2

пусть MoveLeft животные =

let RightList = ListDiff animals Животные

let ShouldTakeAnimal = isMoveDeadly RightList

если (ShouldTakeAnimal), затем

пусть x = List.голова RightList

Console.WriteLine ( «Собираюсь переехать» + x + "задний" )

[x]

еще

Console.WriteLine ( «Фермер возвращается один» )

[]

let rec Решить направление животные =

сопоставьте животных с

| [] -> Консоль.WriteLine ( «Решено» )

| _ ->

направление совпадения с

| Влево -> Решить вправо (Перемещение животных вправо)

| Вправо -> Решить влево (животные @ (MoveLeft animals))

[<точка входа>]

let main args =

Решить левых животных

0


.

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


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



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