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

Узнай цену своей работы

Формулировка задачи:

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

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

textual
Листинг программы
(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)) )

Объяснение кода листинга программы

В представленном коде реализована простая модель для игры в «Миссионеры и Каннибалы» (Missionaries and Cannibals). В этой игре миссионеры (Missionaries) и каннибалы (Cannibals) находятся на двух островах, и их численность меняется в зависимости от того, кого они едят. Миссионеры могут перейти на другой остров, если на нем есть свободные места, и каннибалы не против этого. Код состоит из нескольких функций:

  1. make-state создает состояние, представленное в виде списка, содержащего численность миссионеров, каннибалов и общее количество людей на острове.
  2. b-state, m-state и k-state возвращают соответствующие значения из состояния.
  3. nextstate генерирует следующее состояние, учитывая текущее состояние и добавление или вычитание миссионеров и каннибалов.
  4. safe проверяет, является ли текущее состояние допустимым (то есть не содержит отрицательного количества людей или не содержит больше трех миссионеров или каннибалов).
  5. path генерирует путь из начального состояния к целевому состоянию, используя алгоритм поиска в глубину.
  6. member-lis проверяет, содержится ли элемент в списке.
  7. way вызывает функцию path, чтобы сгенерировать путь от целевого состояния к начальному состоянию.
  8. print используется для вывода пути. Пример вызова функции way в конце кода демонстрирует, как можно использовать функцию для генерации пути от состояния '(-1 3 3)' к состоянию '(1 0 0)'.

Оцени полезность:

13   голосов , оценка 4.538 из 5