Вовк коза капуста відповідь

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

Задача про вовка, козу і капусту — логічна гра, яка ілюструє класичну проблему в області штучного інтелекту з пошуку рішення, яке задоволення системі обмежень.

З одного берега на іншій фермер має перевезти човном вовка, козу і капусту. Човен витримує лише човняра і одного «пасажира». Одночасно не можна залишати разом на березі вовка і козу, козу і капусту. Можна робити скільки завгодно рейсів.

Зміст

Історія і варіації [ ред. | ред. код ]

Загадка є однією з низки головоломок про переправу, де об'єктом є набір елементів, а перехід через річку залежить від різних обмежень.

У самих ранніх відомих варіантах цієї проблеми, у середньовічному рукописі Propositiones ad Acuendos Juvenes [en] , існують три об'єкти: вовк, коза і капуста. Також існують інші варіації головоломки, такі як лисиця, гусак і мішок зерна; вовк, вівця і капуста; лис, курка і хліб; лисиця, гусак і кукурудза; [1] fox, goose and corn [2] пантера, свиня, і каша. Логіка головоломки, в якій є три об'єкти, A, B, C і, такі, що ні А і В, ні B і C не можна залишити разом, залишається тією ж.

Головоломка була знайдена в фольклорі таких країн, як у Камерун, Кабо-Верде, Данія, Ефіопія, Гана, Італія, Румунія, Шотландія, Судан, Уганда, Замбія і Зімбабве. Головоломка отримала порядковий номер H506.3 у класифікації Томсона в категорії народної літературі, і АТО1579 в системі Аарне-Томпсона-Утера [3] .

Загадка була фаворитом Льюїса Керролла, і була перевидана в різних колекціях рекреаційної математик [4] .

В деяких частинах Африки були виявлені варіації на загадку, в яких судно може перевозити два об'єкти, а не тільки один. Коли головоломка ослаблена таким чином, то можна ввести додаткові обмеження, що немає двох елементів, у тому числі і С, котрих можна залишити разом.

Японська версія [ ред. | ред. код ]

Потрібно перевезти сім'ю з шести чоловік і поліцейського з бандитом на інший берег річки на плоту. Проте одночасно на пліт поміщаються тільки дві людини (Уточнення: один з яких повинен бути дорослим), мама, залишившись без тата, б'є хлопчиків, тато — дівчаток. А бандит (уточнення: за відсутності поліцейського) б'є всіх.

Розв'язок [ ред. | ред. код ]

Спочатку фермер перевозить козу (вовк капусти не з'їсть), а потім повертається і забирає вовка. Щоб вовк не з'їв кози, фермер забирає її і повертається за капустою. Залишивши козу, він перевозить капусту, а потім повертається по козу.

перевезти козу туди;
повернутися назад;
перевезти капусту туди;
перевезти козу назад;
перевезти вовка туди;
повернутися назад;
перевезти козу туди;

Кроки 3) та 5) можна поміняти місцями.

Розв'язок у Lisp (пошук вшир) [ ред. | ред. код ]

(defun
is_in
(k
lst)
(cond
(
(NULL
lst)
NIL)
(
(eql
k
(car
lst))
T)
(
1
(is_in
k
(cdr
lst))
)
)
)
(defun
remove
(k
lst)
(cond
((NULL
lst)
NIL)
((eql
k
(car
lst))
(remove
k
(cdr
lst))
)
(
1
(cons
(car
lst)
(remove
k
(cdr
lst)))
)
)
)
(defun
is_ok
(lst)
(cond
(
(NULL
lst)
T
)
(
(is_in
'man
lst)
T
)
(
(and
(is_in
'goat
lst)
(is_in
'cabbage
lst))
NIL)
(
(and
(is_in
'wolf
lst)
(is_in
'goat
lst))
NIL)
(
1
T)
)
)
(defun
move
(k)
(cond
(
(eql
k
'man)
(cond
((is_in
'man
left)
(setq
left
(remove
'man
left))
(setq
right
(cons
'man
right))?
T)
((is_in
'man
right)
(setq
right
(remove
'man
right))
(setq
left
(cons
'man
left))
T)
)
)
(
(and
(is_in
k
left)
(is_in
'man
left))
(setq
left
(remove
'man
(remove
k
left)))
(setq
right
(cons
'man
(cons
k
right)))
T
)
(
(and
(is_in
k
right)
(is_in
'man
right))
(setq
right
(remove
'man
(remove
k
right)))
(setq
left
(cons
'man
(cons
k
left)))
T
)
(
1
NIL)
)
)
(defun
perevoz()
(setq
p
(car
way))
(setq
way
(cdr
way))
(setq
left
(car
(cdr
p)))
(setq
right
(car
(cddr
p)))
(setq
k
(car
p))
(cond
((eql
(length
right)
4)
(print
p)
(return)))
(cond
(
(and
(is_ok
left)
(is_ok
right))
(cond
((and
(neql
(car(last
k))
'goat)
(move
'goat))
(setq
way
(append
way
(list
(list
(append
k
(list
'goat))
left
right))))
(move
'goat)))
(cond
((and
(neql
(car(last
k))
'wolf)
(move
'wolf))
(setq
way
(append
way
(list
(list
(append
k
(list
'wolf))
left
right))))
(move
'wolf)))
(cond
((and
(neql
(car(last
k))
'cabbage)
(move
'cabbage))
(setq
way
(append
way
(list
(list
(append
k
(list
'cabbage))
left
right))))(move
'cabbage)))
(cond
((and
(neql
(car(last
k))
'man)
(move
'man))
(setq
way
(append
way
(list
(list
(append
k
(list
'man))
left
right))))(move
'man)))
)
)
(perevoz)
)
(defun
solve
()
(setq
way
nil)
(setq
left
'(goat
cabbage
wolf
man))
(setq
right
NIL)
(move
'goat)
(setq
way
(append
way
(list
(list
(list
'goat)
left
right))))
(setq
left
'(goat
cabbage
wolf
man))
(setq
right
NIL)
(move
'wolf)
(setq
way
(append
way
(list
(list
(list
'wolf)
left
right))))
(setq
left
'(goat
cabbage
wolf
man))
(setq
right
NIL)
(move
'cabbage)
(setq
way
(append
way
(list
(list
(list
'cabbage)
left
right))))
(setq
right
NIL)
(setq
left
NIL)
(perevoz)
)

Див. також [ ред. | ред. код ]

Посилання [ ред. | ред. код ]

↑The Classic River Crossing Puzzle. Архів оригіналу за 17 червня 2008 . Процитовано 10 березня 2012 .
↑ Mary Jane Sterling, Math Word Problems for Dummies, P.313
↑«Carrying a Wolf, a Goat, and a Cabbage across the Stream. Metamorphoses of ATU 1579»[Архівовано 24 вересня 2015 у Wayback Machine.], Piret Voolaid, Folklore: Electronic Journal of Folklore35 (2007), pp. 111—130. Tartu: Eesti Kirjandusmuuseum.
↑ p. 17, Rediscovered Lewis Carroll Puzzles, Lewis Carroll, compiled by Edward Wakeling, Courier Dover Publications, 1996, ISBN 0486288617