Логическая задача.Миссионеры и Каннибалы

@anyapiy · Регистрация: 15.12.2014

Студворк — интернет-сервис помощи студентам

Добрый день. Помогите пожалуйста написать алгоритм данной задачи:
Три миссионера и три каннибала должны пересечь реку в лодке, в которой могут поместиться только двое. Миссионеры должны соблюдать осторожность, чтобы каннибалы не получили на каком-либо берегу численное преимущество. Как переплыть реку?
Возможная последовательность:
Название: 1.png
Просмотров: 116

Размер: 6.4 Кб

Название: 1.png
Просмотров: 116

Размер: 6.4 Кб

@_Ivana · 30.10.2016, 03:04

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

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
(defn step-var (v state)
    (match state '((ml cl) (mr cr) boat-left))
    (def s (cond boat-left 1 -1) dm (* s (car v)) dc (* s (cadr v)))
    (cons (cons (- ml dm) (- cl dc))
          (cons (+ mr dm) (+ cr dc)) (not boat-left)) )
 
(defn valid? (state)
    (match state '((ml cl) (mr cr) boat-left))
    (defn good (m c) not (all id (cons (< 0 m) (< 0 c) (< m c))))
    (all (lambda (x) x) (cons (<= 0 ml) (<= 0 cl) (<= 0 mr) (<= 0 cr)
            (good ml cl) (good mr cr) (< 0 (+ mr cr)) )))
 
(defn steps (s)
    (def ns (filter valid? (map (lambda (v) step-var v (car s)) vars)))
    (map (lambda (n) cons n s) ns))
 
(def start-state '(((3 3) (0 0) true)))
(def vars '((1 0) (0 1) (2 0) (0 2) (1 1)) )
 
(defn solved? (state) all (lambda (x) = 0 x) (caar state))
 
(defn show-res (l)
    (print \n "Вариант:" \n)
    (defn n-str (n s) cond (>= 0 n) "" (++ s (n-str (- n 1) s)))
    (defn m-c (m c) (++ (n-str m "М") (n-str c "К")))
 
    (defn go (l)
      (cond (null? l) ""
        (
        (match (car l) '((ml cl) (mr cr) boat-left))
        (print "Левый: " (m-c ml cl) ", правый: " (m-c mr cr) " - ")
        (cond (null? (cdr l)) (print "финиш" \n)
            (
            (match (cadr l) '((mln cln) _))
            (def dm (abs (- ml mln)) dc (abs (- cl cln)))
            (print (cond boat-left "туда: " "обратно: ") (m-c dm dc) \n)
            ))
        (go (cdr l))
        )))
    (go l))
 
(foldl (lambda (l a) show-res (reverse l)) "" (solve-wide start-state))

Кликните здесь для просмотра всего текста

=> Количество анализируемых вариантов: 1 3 2 6 8 22 32 84 128 326 514 1280
Вариант:
Левый: МММККК, правый: - туда: КК
Левый: МММК, правый: КК - обратно: К
Левый: МММКК, правый: К - туда: КК
Левый: МММ, правый: ККК - обратно: К
Левый: МММК, правый: КК - туда: ММ
Левый: МК, правый: ММКК - обратно: МК
Левый: ММКК, правый: МК - туда: ММ
Левый: КК, правый: МММК - обратно: К
Левый: ККК, правый: МММ - туда: КК
Левый: К, правый: МММКК - обратно: М
Левый: МК, правый: ММКК - туда: МК
Левый: , правый: МММККК - финиш

Вариант:
Левый: МММККК, правый: - туда: КК
Левый: МММК, правый: КК - обратно: К
Левый: МММКК, правый: К - туда: КК
Левый: МММ, правый: ККК - обратно: К
Левый: МММК, правый: КК - туда: ММ
Левый: МК, правый: ММКК - обратно: МК
Левый: ММКК, правый: МК - туда: ММ
Левый: КК, правый: МММК - обратно: К
Левый: ККК, правый: МММ - туда: КК
Левый: К, правый: МММКК - обратно: К
Левый: КК, правый: МММК - туда: КК
Левый: , правый: МММККК - финиш

Вариант:
Левый: МММККК, правый: - туда: МК
Левый: ММКК, правый: МК - обратно: М
Левый: МММКК, правый: К - туда: КК
Левый: МММ, правый: ККК - обратно: К
Левый: МММК, правый: КК - туда: ММ
Левый: МК, правый: ММКК - обратно: МК
Левый: ММКК, правый: МК - туда: ММ
Левый: КК, правый: МММК - обратно: К
Левый: ККК, правый: МММ - туда: КК
Левый: К, правый: МММКК - обратно: М
Левый: МК, правый: ММКК - туда: МК
Левый: , правый: МММККК - финиш

Вариант:
Левый: МММККК, правый: - туда: МК
Левый: ММКК, правый: МК - обратно: М
Левый: МММКК, правый: К - туда: КК
Левый: МММ, правый: ККК - обратно: К
Левый: МММК, правый: КК - туда: ММ
Левый: МК, правый: ММКК - обратно: МК
Левый: ММКК, правый: МК - туда: ММ
Левый: КК, правый: МММК - обратно: К
Левый: ККК, правый: МММ - туда: КК
Левый: К, правый: МММКК - обратно: К
Левый: КК, правый: МММК - туда: КК
Левый: , правый: МММККК - финиш

Добавлено через 46 минут
UPD: правильные отсечения существенно ускоряют работу алгоритма. Достаточно чуть-чуть доработать функцию генерации следующих шагов из текущего:

Lisp
1
2
3
(defn steps (l)
    (def nexts (filter valid? (map (lambda (v) step-var v (car l)) vars)))
    (map (lambda (n) cons n l) (filter (lambda (v) not (elem v l)) nexts)))

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

Количество анализируемых вариантов: 1 3 2 4 2 2 2 2 2 2 4 4

Для 5 миссионеров и 4 каннибалов также считается влет, но вариантов много - распечатка их всех не влезает в ограничения по количеству символов поста

Количество анализируемых вариантов: 1 4 3 7 9 11 14 16 16 11 8 12 17 24 41 63

Кликните здесь для просмотра всего текста

=> Количество анализируемых вариантов: 1 4 3 7 9 11 14 16 16 11 8 12 17 24 41 63
Вариант:
Левый: МММММКККК, правый: - туда: КК
Левый: МММММКК, правый: КК - обратно: К
Левый: МММММККК, правый: К - туда: ММ
Левый: МММККК, правый: ММК - обратно: М
Левый: ММММККК, правый: МК - туда: МК
Левый: МММКК, правый: ММКК - обратно: К
Левый: МММККК, правый: ММК - туда: МК
Левый: ММКК, правый: МММКК - обратно: М
Левый: МММКК, правый: ММКК - туда: МК
Левый: ММК, правый: МММККК - обратно: К
Левый: ММКК, правый: МММКК - туда: ММ
Левый: КК, правый: МММММКК - обратно: К
Левый: ККК, правый: МММММК - туда: КК
Левый: К, правый: МММММККК - обратно: М
Левый: МК, правый: ММММККК - туда: МК
Левый: , правый: МММММКККК - финиш

Вариант:
Левый: МММММКККК, правый: - туда: КК
Левый: МММММКК, правый: КК - обратно: К
Левый: МММММККК, правый: К - туда: ММ
Левый: МММККК, правый: ММК - обратно: М
Левый: ММММККК, правый: МК - туда: МК
Левый: МММКК, правый: ММКК - обратно: К
Левый: МММККК, правый: ММК - туда: МК
Левый: ММКК, правый: МММКК - обратно: М
Левый: МММКК, правый: ММКК - туда: МК
Левый: ММК, правый: МММККК - обратно: К
Левый: ММКК, правый: МММКК - туда: ММ
Левый: КК, правый: МММММКК - обратно: К
Левый: ККК, правый: МММММК - туда: КК
Левый: К, правый: МММММККК - обратно: К
Левый: КК, правый: МММММКК - туда: КК
Левый: , правый: МММММКККК - финиш

Вариант:
Левый: МММММКККК, правый: - туда: КК
Левый: МММММКК, правый: КК - обратно: К
Левый: МММММККК, правый: К - туда: ММ
Левый: МММККК, правый: ММК - обратно: М
Левый: ММММККК, правый: МК - туда: МК
Левый: МММКК, правый: ММКК - обратно: К
Левый: МММККК, правый: ММК - туда: МК
Левый: ММКК, правый: МММКК - обратно: М
Левый: МММКК, правый: ММКК - туда: МК
Левый: ММК, правый: МММККК - обратно: К
Левый: ММКК, правый: МММКК - туда: МК
Левый: МК, правый: ММММККК - обратно: М
Левый: ММК, правый: МММККК - туда: ММ
Левый: К, правый: МММММККК - обратно: М
Левый: МК, правый: ММММККК - туда: МК
Левый: , правый: МММММКККК - финиш

Вариант:
Левый: МММММКККК, правый: - туда: КК
Левый: МММММКК, правый: КК - обратно: К
Левый: МММММККК, правый: К - туда: ММ
Левый: МММККК, правый: ММК - обратно: М
Левый: ММММККК, правый: МК - туда: МК
Левый: МММКК, правый: ММКК - обратно: К
Левый: МММККК, правый: ММК - туда: МК
Левый: ММКК, правый: МММКК - обратно: М
Левый: МММКК, правый: ММКК - туда: МК
Левый: ММК, правый: МММККК - обратно: К
Левый: ММКК, правый: МММКК - туда: МК
Левый: МК, правый: ММММККК - обратно: М
Левый: ММК, правый: МММККК - туда: ММ
Левый: К, правый: МММММККК - обратно: К
Левый: КК, правый: МММММКК - туда: КК
Левый: , правый: МММММКККК - финиш

Вариант:
Левый: МММММКККК, правый: - туда: КК
Левый: МММММКК, правый: КК - обратно: К
Левый: МММММККК, правый: К - туда: ММ
Левый: МММККК, правый: ММК - обратно: М
Левый: ММММККК, правый: МК - туда: МК
Левый: МММКК, правый: ММКК - обратно: К
Левый: МММККК, правый: ММК - туда: МК
Левый: ММКК, правый: МММКК - обратно: М
Левый: МММКК, правый: ММКК - туда: МК
Левый: ММК, правый: МММККК - обратно: К
Левый: ММКК, правый: МММКК - туда: МК
Левый: МК, правый: ММММККК - обратно: М
Левый: ММК, правый: МММККК - туда: МК
Левый: М, правый: ММММКККК - обратно: К
Левый: МК, правый: ММММККК - туда: МК
Левый: , правый: МММММКККК - финиш

Вариант:
Левый: МММММКККК, правый: - туда: КК
Левый: МММММКК, правый: КК - обратно: К
Левый: МММММККК, правый: К - туда: КК
Левый: МММММК, правый: ККК - обратно: К
Левый: МММММКК, правый: КК - туда: ММ
Левый: МММКК, правый: ММКК - обратно: К
Левый: МММККК, правый: ММК - туда: МК
Левый: ММКК, правый: МММКК - обратно: М
Левый: МММКК, правый: ММКК - туда: МК
Левый: ММК, правый: МММККК - обратно: К
Левый: ММКК, правый: МММКК - туда: ММ
Левый: КК, правый: МММММКК - обратно: К
Левый: ККК, правый: МММММК - туда: КК
Левый: К, правый: МММММККК - обратно: М
Левый: МК, правый: ММММККК - туда: МК
Левый: , правый: МММММКККК - финиш

......

@anyapiy · 31.10.2016, 17:04 **[ТС]**

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

@_Ivana · 31.10.2016, 17:13

Сообщение от anyapiy

помочь сделать

могу,

Сообщение от anyapiy

сделать

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

@anyapiy · 31.10.2016, 19:43 **[ТС]**

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

@_Ivana · 31.10.2016, 19:48

Сообщение от anyapiy

для начала

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

Lisp
1
2
foo (lambda (x) (* 2 x)) '(1 2 3 4 5)
=> (2 4 6 8 10)

@anyapiy · 31.10.2016, 21:15 **[ТС]**

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

@_Ivana · 31.10.2016, 22:18

Сообщение от anyapiy

увы

,я только подтверждаю мои априорные предположения.

@TrueTerm · 02.11.2016, 21:05

anyapiy, вот другой вариант на Common Lisp. Использованы только стандартные средства, причем только "чисто функциональные", без переменных и добавлений "императивного стиля".

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(defun make-state (b m k) (list b m k)) 
(defun b-state (state)(nth 0 state))
(defun m-state (state)(nth 1 state))
(defun k-state (state)(nth 2 state))
 
(defun nextstate (state dm dk)
(safe (make-state  
       (- (b-state state))
       (+ (m-state state) (* (b-state state) dm))
       (+ (k-state state) (* (b-state state) dk))
       )
))      
 
(defun safe (state)
(cond 
    ((> (m-state state) 3) nil)
    ((< (m-state state) 0) nil)          
    ((> (k-state state) 3) nil)
    ((< (k-state state) 0) nil)
    ((and (> (m-state state) 0)(< (m-state state) (k-state state))) nil)
    ((and (> (- 3 (m-state state)) 0)(< (- 3 (m-state state)) (- 3 (k-state state)))) nil)
    (t state)
 ))
 
 
(defun path (state goal been-list)
(cond ((null state) nil)
((equal state goal) (cons state been-list))
((not (member-lis state been-list ))
(or (path (nextstate state 1 1) goal (cons state been-list))
(path (nextstate state 1 0) goal (cons state been-list))
(path (nextstate state 2 0) goal (cons state been-list))
(path (nextstate state 0 2) goal (cons state been-list))    
(path (nextstate state 0 1) goal (cons state been-list))
 )))) 
 
(defun member-lis (x lis)
(cond ((null lis) nil)
((equal x (car lis)) t)
(t (member-lis x (cdr lis))))) 
 
(defun way (state goal) (path goal state nil)) 
 
(print (way '(-1 3 3) '(1 0 0)) )

Проверено на онлайн интерпретаторе http://rextester.com/l/common_lisp_online_compiler. Выдает ответ:

Lisp
1
2
((-1 3 3) (1 2 2) (-1 3 2) (1 3 0) (-1 3 1) (1 1 1) (-1 2 2) (1 0 2) (-1 0 3)
 (1 0 1) (-1 1 1) (1 0 0))

Здесь состояние закодировано тремя числами: лодка на исходном берегу (-1) или лодка на целевом берегу (1), количество миссионеров, количество каннибалов.

transformator.t · 02.11.2016, 21:41

del

@anyapiy · 05.11.2016, 18:08 **[ТС]**

TrueTerm, Cпасибо большое!!!
поясните пожалуйста ещё,по какому принципу работает эта функция,а именно какую роль играют dm dk

Lisp
1
2
3
4
5
6
7
(defun nextstate (state dm dk)
(safe (make-state  
       (- (b-state state))
       (+ (m-state state) (* (b-state state) dm))
       (+ (k-state state) (* (b-state state) dk))
       )
))

@TrueTerm · 06.11.2016, 11:12

anyapiy, Функция nextstate (state dm dk) по текущему состоянию state вычисляет следующее возможное состояние (nil, если такое невозможно). Параметры dm, dk - сколько миссионеров и каннибалов уезжают на другой берег за этот ход. Функция производит новое состояние тремя присваиваниями:
b_new:=-b (лодка будет на другом берегу),
m_new:=m+b*dm (изменилось кол-во миссионеров),
k_new:=k+b*dk (изменилось кол-во каннибалов).
Затем проверяет новое состояние на корректность при помощи safe. Возвращается либо это состояние, если оно корректно, либо nil (если состояние недопустимо).

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

Логическая задача.Миссионеры и Каннибалы

Решение

Решение

@anyapiy 1 / 1 / 0 Регистрация: 15.12.2014 Сообщений: 13

	Логическая задача.Миссионеры и Каннибалы 29.10.2016, 13:57. Показов 4217. Ответов 11 Метки нет (Все метки) Добрый день. Помогите пожалуйста написать алгоритм данной задачи: Три миссионера и три каннибала должны пересечь реку в лодке, в которой могут поместиться только двое. Миссионеры должны соблюдать осторожность, чтобы каннибалы не получили на каком-либо берегу численное преимущество. Как переплыть реку? Возможная последовательность: 1

@anyapiy 1 / 1 / 0 Регистрация: 15.12.2014 Сообщений: 13
	31.10.2016, 17:04 [ТС]
	Если будет не трудно можете помочь сделать при помощи примитивных функций cons, cond, без применения функций lambda и других продвинутых функций, а то я только начинаю программировать на данном языке 0

@anyapiy 1 / 1 / 0 Регистрация: 15.12.2014 Сообщений: 13
	31.10.2016, 19:43 [ТС]
	ну что же, я хочу доказать, что я не халявщик,но расскажите пожалуйста поэтапно какие функции стоит написать и что они должны делать,для начала.спасибо 0

@anyapiy 1 / 1 / 0 Регистрация: 15.12.2014 Сообщений: 13
	31.10.2016, 21:15 [ТС]
	в моем проекте не должно быть использования функций типа lambda,а лишь функции примитивы.С lambda нам сказали не работать,ибо мы их не проходили.увы 0

transformator.t defun 603 / 617 / 44 Регистрация: 30.04.2011 Сообщений: 702
	02.11.2016, 21:41
	del 0

@TrueTerm 205 / 142 / 57 Регистрация: 25.12.2014 Сообщений: 447
	06.11.2016, 11:12
	anyapiy, Функция nextstate (state dm dk) по текущему состоянию state вычисляет следующее возможное состояние (nil, если такое невозможно). Параметры dm, dk - сколько миссионеров и каннибалов уезжают на другой берег за этот ход. Функция производит новое состояние тремя присваиваниями: b_new:=-b (лодка будет на другом берегу), m_new:=m+bdm (изменилось кол-во миссионеров), k_new:=k+bdk (изменилось кол-во каннибалов). Затем проверяет новое состояние на корректность при помощи safe. Возвращается либо это состояние, если оно корректно, либо nil (если состояние недопустимо). 1