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

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


Волк, коза и капуста. Загадка на логику.

Эта известная головоломка есть в народном творчестве таких стран, как Италия, Румыния, Эфиопия и Зимбабве. Существует не одна ее вариация: с лисой, курицей и хлебом или с пантерой, свиньей и кашей! А Ты знаешь, как решать задачу о переправе?

14 93 т.

Итак, представь, что Ты — фермер, у которого есть маленькая лодка. С одного берега реки на другой Тебе необходимо перевезти волка, козу и капусту. Всех вместе взять нельзя — нужно переправлять каждого «пассажира» по отдельности. Но имей в виду, что когда Ты повезешь на другой берег капусту, в это время волк съест козу. А если решишь везти волка — коза скушает капусту.

Что же делать? Хорошенько поразмысли. Рейсов можно делать сколько угодно — главное, чтобы все оставалось целым и невредимым.

Ну как, удалось решить эту нелегкую задачку? Все еще нет? Ну ладно, дам одну подсказку: переправлять «пассажира» можно не только туда, но и назад!

Что же — думаю, теперь Тебе удалось перевезти всех целыми и невредимыми! Посмотри на решение задачи и проверь, все ли сходится.

  1. Сначала нужно перевезти козу, оставив волка с капустой.
  2. Теперь возвращаемся и забираем волка. Но оставлять волка с козой на новом берегу нельзя.
  3. Поэтому берем козу с собой в лодку, а волк сидит на берегу одинокий и голодный.
  4. Козу оставляем на берегу, а капусту переправляем к волку.
  5. Возвращаемся назад и забираем козу.

Кстати, это не единственный вариант решения задачи. Вот еще один:

  1. Везем козу туда.
  2. Возвращаемся обратно.
  3. Везем капусту туда.
  4. Забираем козу назад.
  5. Везем волка туда.
  6. Возвращаемся за козой.
  7. Перевозим козу туда.

Готово!

А теперь признавайся, удалось ли Тебе самостоятельно дойти до правильного решения, и если да — то каким способом? ;)

Еще больше отборных загадок найдешь тут:

Заметили орфографическую ошибку? Выделите её мышкой и нажмите Ctrl+Enter

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

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

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

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

Решение.

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

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

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

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

Загадка про волка, козу и капусту

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

Ответ

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

Перевозим волка, козу и капусту через реку с эффектами на 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 

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

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

15 интересных логических задачек для детей и взрослых

15 интересных логических задачек для детей и взрослых

Логические игры и головоломки — это отличное развлечение как для детей, так и для взрослых. Они вырабатывают привычку думать, рассуждать, делать выводы и всегда стараться найти решение проблемы.

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

Помните старинную задачу про волка, козу и капусту? Кто не решал ее в детстве! Предложите задачу своему ребенку! Мужику нужно перевезти через реку волка, козу и капусту. Но в лодке может поместиться только он сам, а с ним или только волк, или только коза, или только капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как мужику перевезти свой груз?

Решение:

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

Детективная задачка

На лугу лежат пять кусочков угля, одна морковь и шарф. Никто не клал их туда. Почему они там лежат?

Решение:

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

Летная задачка

Мужчина выпрыгивает без парашюта из самолета. Высадка небезопасная, но мужчина остается целым и невредимым. Почему?

Решение:

Самолет находится ещё на взлётно-посадочной полосе.

Задачка про ноги

Ваня идет к лесному озеру. Ему навстречу движется класс из 25 учеников и двух преподавателей. Родители 10 детей также принимают участие в прогулке. Пять матерей еще везут своих детей на колясках. Преподаватель ведет с собой собаку. Сколько ног идут по дороге к лесному озеру?

Решение:

По дороге к лесному озеру идут только две ноги — Ванины. Все, кого он встретил, возвращаются с озера.

Сколько ворон?

Вишня у Маши плодоносит в большом количестве. К сожалению, на дерево садятся вороны и безжалостно клюют плоды. Вечером Маша считает ворон. Их 38! Это настолько выводит ее из себя, что она ловит одну ворону сачком. Сколько ворон осталось на дереве?

Решение:

Осталась только одна ворона, пойманная Машей. Остальные вороны испугались и улетели.

Задачка на внимательность

Молодая девушка заказывает в кафе яблочный сок, рулет и шоколадное мороженое. Официант, который принимает заказ, приносит ей вскоре все желаемое. После того как девушка оплатила заказ, официант спросил: «Трудно работать в полиции?» Как он догадался, что девушка — полицейский?

Решение:

Девушка была в полицейской форме.

День рождения князя

Когда князь празднует день рождения, его подданные должны принести ему достойный подарок: самую сочную ветчину, самый пряный сыр, самую упитанную курицу, искусно выделанные шкурки, плетеные корзинки, глиняные кувшины и резные изделия. Крестьянин сделал князю необычный подарок: бутылку с яблочным соком. Отличие этого подарка — яблоко находится в бутылке. Князь поражен: каким образом тот смог засунуть яблоко в бутылку? «Как ты сделал это? При помощи колдовства?» — спрашивает князь. Крестьянин отвечает: «Догадайтесь сами, но я вовсе не чародей!» Как яблоко попадает в бутылку?

Решение:

Крестьянин надевает бутылку на яблоневую ветку вскоре после цветения. Таким образом, плод развивается в бутылке.

Еще один вид логических игр придется всем по вкусу — это игры с палочками. Для игры понадобится набор счетных палочек или любые палочки одинаковой длины и толщины (например, спички, с которых предварительно счистили серу), подойдут и полоски картона. Если вы играете вместе с детьми, то можно давать устные задания. Если ребенок играет один, подготовьте карточки с рисунком и условием игровой задачи.

Задание № 1

Переложи одну палочку так, чтобы дом смотрел в другую сторону.

Задание № 2

Переложи 3 палочки так, чтобы корова оглянулась и подняла хвост.

Еще несколько заданий с палочками из пособия С. И. Волковой «Математика и конструирование» (1−4 классы):

А в завершении мы хотим предложить вам самостоятельно изготовить знаменитую китайскую головоломку «Танграм». И в этом нам опять поможет пособие С. И. Волковой «Математика и конструирование».

Из деталей этой головоломки можно складывать разные фигуры. Сложите для начала 1 и 2 фигуры. Рисунок вам поможет. Теперь попробуйте сложить фигуры 3, 4, 5, 6. И с этим справились? Поздравляем!

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

Фото: NadyaEugene/masterone/Shutterstock.com, архив пресс-службы,

Задача «Волк, коза и капуста»

Удивительные находки и неразгаданные загадки

И.Г. СУХИН, Институт теории образования и педагогики РАО

 

Во многих математических монографиях есть страницы, посвященные истории возникновения знаменитых задач, доступных учащимся старших классов (например, Чистяков В.Д. Старинные задачи по элементарной математике — Минск, 1978). Однако практически нет работ, из которых учитель начальной школы мог бы получить исчерпывающую информацию о не менее известных старинных головоломках, представляющих интерес для учеников I–IV классов. Нам хотелось бы поделиться с читателями журнала результатами своих поисков и начать разговор о поразительной судьбе некоторых из таких задач.

В “Книге 1” труда Е.И. Игнатьева “В царстве смекалки, или Арифметика для всех: Опыт математической хрестоматии: Книга для семьи и школы” (СПб.: Тип. А.С. Суворина, 1911. — С. 75–76) приведена одна из самых замечательных логических задач в истории человечества: “Задача 52-я. Волк, коза и капуста”:

“Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?”

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

“Решение: Ясно, что приходится начать с козы. Крестьянин, перевезши козу, возвращается и берет волка, которого перевозит на другой берег, где его и оставляет, но зато берет и везет обратно на первый берег козу. Здесь он оставляет ее и перевозит к волку капусту. Вслед затем, возвратившись, он перевозит козу, и переправа оканчивается благополучно”.

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

Вначале крестьянин опять-таки перевозит козу. Но вторым он не обязательно должен забирать волка! Можно взять капусту, отвезти ее на другой берег, оставить там и вернуть на первый берег козу. Затем перевезти на другой берег волка, вернуться за козой и снова отвести ее на другой берег. В этом случае количество рейсов (7) точно такое же, как и в опубликованном выше варианте.

Существование двух решений не отмечено ни в многократных переизданиях книги Е.И. Игнатьева, ни в других самых авторитетных источниках. В их числе: Э. Люкас “Математические развлечения: Приложение арифметики, геометрии и алгебры к различного рода запутанным вопросам, забавам и играм” (СПб.: Изд. Павленкова, 1883. — С. 7), Н.Н. Аменицкий, И.П. Сахаров “Забавная арифметика: Хрестоматия для развития сообразительности и самодеятельности детей в семье и в школе” (М.: Изд. товарищества И.Д. Сытина, 1909. — С. 23–24), В. Аренс “Математические игры и развлечения” (СПб.: Физика, 1911. — С. 20), Б.А. Кордемский “Математическая смекалка” (М.: Государственное издательство технико-теоретической литературы, 1955. — С. 14; М.: Наука, 1991. — С. 15) и многочисленные сборники последних лет.

Это тем более удивительно, что наличие двух решений было указано, к примеру, еще в начале 20-х годов ХХ века в книге В. Литцмана “Веселое и занимательное в фигурах и числах: Математические развлечения” (М. — Пт.: Изд. Л.Д. Френкель, 1923. — С. 128–129), причем довольно подробное. Видимо, многие издатели сочли необязательным приводить оба варианта, ведь они схожи и являются по сути “зеркальными”. Но в книге для детей, особенно младшего возраста, это необходимо, иначе существенно снижается педагогическая ценность задачи!

Любопытно, что Б.А. Кордемский в решении отмечает только второй вариант и по какой-то причине не упоминает первый. Загадка? Загадка.

Очень интересен вопрос о времени возникновения данной головоломки и ее первоисточнике. Б.А. Кордемский в книге “Математическая смекалка” говорит вскользь: “Это... старинная задача; встречается в сочинениях VIII века”.

Вначале может показаться, что мы имеем дело с опечаткой, ведь первая или одна из первых отечественных публикаций задачи “Волк, коза и капуста” датирована концом ХVIII века. В фондах Российской Исторической библиотеки сохранилась книга “Гадательная арифметика для забавы и удовольствия” (СПб., 1789). На титульном листе значится: “На ижд. изд. И. Краснопольского”, что означает “на иждивении издателя И. Краснопольского”. В раритете на 62 страницах сорок одна занимательная задача. На с. 42–43 читаем: “Некоторый мужик везши с собою волка, козу и капусту приехал к реке, у берегу коей нашел столь малую лодку, что она кроме его и одного чего-нибудь из везомых им, поднимать не могла. И так спрашивается, каким образом переправить оных через реку так, чтобы волк не съел козы, а коза капусты?” Далее приводится один вариант решения (первый).

Интересно, что в пособии болгарских авторов “Математический фольклор” (М.: Знание, 1987. — С. 180) задача о волке, козе и капусте помещена в раздел “Из математического фольклора других стран” с пометкой в скобках “Россия”.

Вернемся к истории задачи и вопросу: прав ли Б.А. Кордемский, датировав задачу восьмым веком.

По мнению ряда историков, задача имеет западные корни. В. Аренс указывает, что авторство хрестоматийной задачи приписывается Алкуину (Аренс В. Математические игры и развлечения. — СПб.: Физика, 1911. — С. 20).

В. Литцман, предлагая читателям познакомиться с задачей о переправе в книге “Веселое и занимательное о числах и фигурах” (М.: Государственное издательство физико-математической литературы, 1963. — С. 189), вскользь пишет: “У Алкуина мы находим следующий рассказ”.

Что же в наши дни известно об этой незаурядной личности? Алкуин (735–804) был ученым монахом и математиком из Ирландии, автором ряда учебников по математике. Король Карл Великий благоволил к ученым и всячески поощрял развитие наук. За королевским круглым столом нередко проводились состязания в решении хитроумных головоломок, в которых Алкуин имел возможность проявить свои незаурядные способности.

Алкуин основал Палатинскую школу в Туре (созданную для детей Карла V), принимал участие в основании университета в Париже. Добавим, что Алкуин был другом и учителем Карла Великого, его ученым советником.

Из других головоломок Алкуина наибольшую известность получили задачи 1) о гончей и зайце, 2) о покупке свиней, 3) о трех наследниках и 21 бочке, 4) о ста мерах пшеницы, 5) о быке. Но только головоломка о волке, козе и капусте до сих пор поражает воображение и детей, и взрослых. Эту и некоторые другие задачи Алкуин поместил в свой трактат “Задачи для оттачивания ума юношей”, написанный, как было принято в то время, латиницей.

Перед публикацией данной статьи очень хотелось подержать в руках текст первоисточника. А вдруг там приведены оба решения? И вот копия латинского манускрипта передо мной. Под №ХVIII легендарная задача. Сразу бросается в глаза, что решение одно — то самое, которое приводится в большинстве пособий. Но сама головоломка имеет иное название: “Задача о человеке, козе и волке”! А ее условие (если переводить близко к оригиналу) таково:

“Один человек должен был перевезти через реку волка, козу и кочан капусты. И не удалось ему найти другого судна, кроме как такого, которое могло выдержать только двоих из них. Задача, таким образом, заключалась в том, как всех перевезти на другой берег целыми и невредимыми. Скажите, кто способен: каким путем они могут перебраться на другой берег невредимыми” (перевод с латинского выполнен Е.И. Сухиной).

Так что же, все загадки разгаданы? Нет, последнее десятилетие преподносит новые сюрпризы. Вот уже в нескольких изданиях при объяснении решения данной головоломки авторы делают одну и ту же забавную ошибку. Раскроем на с. 244 пособие Е.А. Латия “365 развивающих игр и затей для маленьких детей” (М.: Эксмо-Пресс, 2001), где предлагаемое решение столь фантастично, что его следует воспроизвести дословно: “Разгадка: сперва везут волка и капусту, оставляют капусту на противоположном берегу; везут волка обратно и оставляют на берегу; забирают козу, переправляют на другой берег; там забирают капусту, везут обратно к волку и уже вместе их окончательно перевозят на другой берег”.

Если бы волка и капусту можно было везти в лодке одновременно, то переправа завершилась бы гораздо быстрее, чем указано Е.А. Латием (но по условию задачи их нельзя переправлять вместе!) В вышедшей ранее раскраске “Угадайка: Выпуск 4” (М.: Крона, 1996) волка заменили на крокодила, козу — на пирата Крюка, а капусту — на Питера Пэна, но решение аналогично предыдущему: “Сначала надо перевезти Питера и крокодила...” и т.д. Очевидно, что первоисточник ошибки один и тот же. Быть может вам удастся найти его?

А вдруг это Алкуин через века задумал подшутить над нами? Ничем другим я не могу объяснить то обстоятельство, что и сам первоначально при объяснении второго варианта решения указал не 7 рейсов, а 11, причем заметил свою оплошность в самый последний момент.

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

 

Где еще можно прочитать об Алкуине и его знаменитой задаче

Баврин И.И., Фрибус Е.А. Занимательные задачи по математике — М.: ВЛАДОС, 1999.

Баврин И.И., Фрибус Е.А. Старинные задачи — М.: Просвещение, 1994.

Белов В.Н. Головоломки из близкой дали // Компьютерра. — 2000. — № 1.

Депман И.Я. История арифметики — М.: Просвещение, 1965.

Леман И. Увлекательная математика — М.: Знание, 1985.

Попов Г.Н. Сборник исторических задач по элементарной математике — М. — Л.: Главная редакция научно-популярной и юношеской литературы, 1938.

 

НАЧАЛЬНАЯ ШКОЛА №7-2002, c. 69-70.

 

 

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

.

Головоломка: Волк, коза и капуста

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

  1. Преобразование проблемы в структуры данных и функции
  2. Выберите стратегию поиска решения

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

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

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

Это мой первый набросок, поэтому он обязательно неэлегантен. Позже я хотел бы найти решение с использованием Prolog, но моего Prolog Foo еще нет. Я также хотел бы сделать это более гибким, включив больше участников, «матрицу съедобности» и возможность создания нескольких островов вместо двух банков.

Я решил представить два берега и лодку в виде списков. Я решил представить волка, козу и капусту целыми числами от нуля до двух; это позволяет мне использовать вычитание, чтобы увидеть, ест ли один другой. Если абсолютная величина их разницы равна единице, то двух пассажиров нельзя оставлять на берегу одних вместе. Ограничение «только один пассажир» проверяется путем проверки длины списка. Это основная идея.

Эта первая функция смотрит на один банк и возвращает True , если из этого банка можно безопасно выйти, и False , если выход из этого банка приведет к тому, что что-то будет поглощено.

 импортировать случайный как rnd импорт scipy.stats из импорта pylab * def compare (x): '' ' Сравните каждый элемент `x` с каждый второй элемент `x`. Пункты закодированы как целые числа. Если один предмет можно съесть другой элемент, затем абсолютное значение их разница равна единице. Мы будем рассмотреть все `x`; если мы найдем один где угодно, тогда мы вернем False, в противном случае мы вернем True.'' ' # создать временный список tmp = список () # определить, сколько элементов в x N = len (x) # для каждого элемента в x .. для i в диапазоне (N): # сравнить с любым другим элементом в x для j в диапазоне (i + 1, N): # записываем абсолютное значение # разница двух предметов tmp.append (abs (x [i] - x [j])) # если в tmp стоит 1, это означает # что-то съели, возвращаем False если 1 в tmp: return False # else return True еще: вернуть True 

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

 def check (x, y, z): '' ' Первое условие подсчитывает, сколько вещи в лодке. Следующее делает проверяет, осталось ли что-нибудь на банки могут есть что угодно. '' ' # Если в # лодка, затем верните False если len (y)> 1: return False # Если что-нибудь на любом берегу можно съесть # что-нибудь еще в этом банке, тогда # return False если len (y) == 1: если сравнить (x): если сравнить (z): вернуть True return False # Если у лодки правильный номер # жильцов и банки в безопасности # затем верните True вернуть True 

Я не знал, как назвать эту функцию.(Я не знал, что вызывать любую из этих функций.) Эта функция принимает текущее состояние и возвращает множество возможных ходов, как законных, так и незаконных. (Плавные) ходы кодируются как строки. Исходный (левый) берег - X , лодка - Y , а другой (правый) берег - Z . Мне это нравится, потому что это напоминает мне о математических задачах, и потому что аналогия слева и справа применима к буквам, когда вы думаете об алфавите.

Строка «X1R» означает «переместить элемент списка с одним индексом x на вправо на », якобы в лодку.Строка «Z0L» означает «переместить элемент с нулевым индексом из списка z на левый , в ожидающую лодку. Строка «YL», и «YR», означает «переместить лодку влево» и «переместить лодку вправо» соответственно. Это было совершенно произвольно, но я подумал, что это обеспечивает хороший баланс между краткостью и удобочитаемостью при отладке.

 def think (x, y, z): '' ' Это принимает текущее состояние и возвращает множество потенциально легальных и незаконных действий.'' ' # создаем пустой список ходов перемещается = список () # если лодка пуста .. если len (y) == 0: # если что-то есть на левом берегу если len (x)> 0: # предлагаем добавить каждый элемент на # левый берег к лодке для i в диапазоне (len (x)): move.append ('X' + str (i) + 'R') # если что-то есть на правом берегу если len (z)> 0: # предлагаем добавить каждый элемент на # правый берег к лодке для i в диапазоне (len (z)): движется.добавить ('Z' + str (i) + 'L') # если лодка полна .. еще: # предлагаю сдать вещи # на лодке на любом берегу move.append ('YL') move.append ('YR') # возвращаем возможные ходы ответные ходы 

Этот монстр принимает текущее состояние берегов и лодки в дополнение к потенциальному ходу, а затем возвращает либо новое состояние, если это допустимый ход, либо Ложь . Мы будем использовать этого парня в понимании списка с условным условием if в конце.(Условное условное в отличие от трехстороннего условного условное условие .)

 def оценивать (x, y, z, mv): '' ' Это принимает текущее состояние оригинала банк `x`, лодка` y`, другой берег `z` и некоторый ход `mv` закодирован как строка. Он возвращается новое состояние берегов и лодки, если move является допустимым, иначе возвращается False. '' ' # превращаем строку в список строк mv = [i for i in mv] # делаем копии банков x и z, # и лодку посередине, y tx, ty, tz = x [:], y [:], z [:] # сделать первый ход start = mv.поп (0) # если первый ход с лодки .. если start == 'Y': # взять предмет из лодки, y, # и положим на левый берег, x. если mv [0] == 'L': tx.append (ty.pop ()) # взять предмет из лодки, y, # и положите на правый берег, z. если mv [0] == 'R': tz.append (ty.pop ()) # если первый ход с левого берега .. elif start == 'X': # возьмите этот предмет с левого берега, x, # и положите на лодку, y.ty.append (tx.pop (int (mv.pop (0)))) # если первый ход с правого берега .. elif start == 'Z': # возьмите этот предмет с правого берега, z, # и положите на лодку, y. ty.append (tz.pop (int (mv.pop (0)))) # проверяем состояние # лодка и берега - допустимое состояние # и вернем новые состояния если проверить (tx, ty, tz): возврат tx, ty, tz # в противном случае вернуть False еще: return False 

Поворот сюжета: мы решили задачу, но мы могли бы сделать это за пивом или другим вкусным напитком для взрослых.Что действительно интересно сейчас, так это производительность компьютера с точки зрения шагов, предпринятых для решения проблемы в большом количестве испытаний. Напомним, что мы делаем легальные ходы наугад, не требуя затрат, чтобы помочь нам выбрать оптимальный ход. Получается, что для решения задачи компьютеру обычно требуется от 25 до 50 шагов, а минимальное количество шагов - одиннадцать.

 def test (): # начальное состояние с волком (2), # коза (1) и капуста (0) x = список ([0,1,2]) y = список () z = список () # счетчик я = 0 # запускаем цикл в то время как True: # увеличить счетчик я + = 1 # если у вас все пассажиры # на другой берег, затем остановите цикл если len (z) == 3: сломать # генерируем кучу ходов движется = думать (x, y, z) # выбрать легальные ходы legal = [mv для mv в ходах, если оценивать (x, y, z, mv)] # произвольно оцениваем допустимый ход x, y, z = оценивать (x, y, z, rnd.выбор (законный)) # если мы пройдем 1000 шагов, то # остановим цикл и закончим если я == 1000: сломать # вернуть количество итераций вернуть я # создаем список для # количество итераций раз = список () # несколько раз .. для k в диапазоне (10000): # посмотрим, сколько итераций это # требуется для решения проблемы times.append (тест ()) 

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

 counts, bin, patch = hist (times, bin = 60, alpha = 0.5) title («Количество шагов, необходимых для решения головоломки») ylabel ("Количество решений") xlabel («Количество шагов для решения») savefig ("puzzle_histogram.png", fmt = "png", dpi = 200) 

.

Волк, коза и капуста - обучающие игры

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

.

Галерея избранного для Fat-Furry-Wolf - Fur Affinity [точка] net

~ Толстый-пушистый-волк

Участник с: 20 окт.2016 г. 08:14

  • Профиль
  • Галерея
  • Обрывки
  • Избранное
  • Журналы
.

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


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



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