Prolog — задача 78 кто украл соль

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 месяца назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6774
      @admin
      StudLance.ru

      Задача:

      Кто украл соль?
      — Вот тебе твой сахар,—сказал Король.—Можешь испечь мне кренделей.
      — Как, без соли?—спросила Королева.
      Так и есть! Соль тоже украли! Следствием установлено, что кражу могли совершить Гусеница, Ящерка Билль или Чеширский Кот.

      (Кто-то из них пробрался на кухню и съел всю соль: пустая коробка из-под соли осталась на месте.)
      Все трое предстали перед судом и сделали следующие заявления:
      Гусеница. Соль съел Ящерка Билль.
      Ящерка Билль. Сущая правда!
      Чеширский Кот. Я никогда не ел соль.
      В ходе судебного заседания выяснилось, что по крайней мере один из обвиняемых лгал и по крайней мере один говорил правду.

      Кто украл соль?

      Приведенные тут варианты решения очень легко читаются — я думаю, к ним не нужны дополнительные пояснения. Если что-то не понятно — спрашивайте. Наиболее сложные предикаты — входит_в, без_повторов и убрать_повторы подробно разобраны тут. Там же, объясняется как понять findall. Также, понять решение может помочь статья «Решение логических задач на Prolog«.

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

      Решение 1

      DOMAINS 
      	персонаж = гусеница; ящерица; кот
      	гипотеза = съел_соль(персонаж)
      	
      	персонажи = персонаж*
      PREDICATES      
             nondeterm возможный_вор(персонаж)
             nondeterm генерация_гипотезы(гипотеза)
             
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал(персонаж, гипотеза)
             nondeterm сказал_правду(персонаж, гипотеза)
             nondeterm солгал(персонаж, гипотеза)
             
             nondeterm по_крайней_мере_один(персонажи)
      CLAUSES 
      	возможный_вор(гусеница).
      	возможный_вор(ящерица).
      	возможный_вор(кот).
      	
      	генерация_гипотезы(съел_соль(Вор)):-
      		возможный_вор(Вор).
      		
      	сказал(гусеница, съел_соль(ящерица)). %гусеница сказала что соль съела ящерица
      	сказал(ящерица, СъелСоль):- %ящерица сказала, что гусеница сказала правду
      		сказал(гусеница, СъелСоль).
      	сказал(кот, съел_соль(Вор)):-
      		возможный_вор(Вор),
      		NOT(Вор = кот). % кот никогда не ел соль
      	
      	сказал_правду(Кто, Гипотеза):-
      		сказал(Кто, Что),
      		Что = Гипотеза.
      		
      	солгал(Кто, Гипотеза):-
      		возможный_вор(Кто),
      		NOT(сказал_правду(Кто, Гипотеза)).
      	
      	по_крайней_мере_один(Список):-
      		NOT(Список = []). % список не пустой (есть по крайней мере один элемент)
      		
      	проверка_гипотезы(Гипотеза):-
      		findall(Кто, солгал(Кто, Гипотеза), Солгали),
      		findall(Кто, сказал_правду(Кто, Гипотеза), СказалиПравду),
      		по_крайней_мере_один(Солгали),
      		по_крайней_мере_один(СказалиПравду).
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 2

      DOMAINS 
      	имя = гусеница; ящерица; кот
      	роль = вор; не_вор
      	истинность = правда;ложь
      	
      	структура_гипотезы = персонаж(имя, роль, истинность)
      	
      	гипотеза = структура_гипотезы*
      	
      	имена = имя*
      PREDICATES      
             nondeterm возможное_имя(имя)
             nondeterm возможная_роль(роль)
             nondeterm возможная_истинность(истинность)
             
             nondeterm входит_в(структура_гипотезы, гипотеза)
             
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             nondeterm проверка_высказывания(имя, гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             
             nondeterm количество(имена, integer)
      CLAUSES 
      	возможное_имя(гусеница).
      	возможное_имя(ящерица).
      	возможное_имя(кот).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
      	возможная_истинность(правда).
      	возможная_истинность(ложь).
      	
      	генерация_гипотезы([
      		персонаж(гусеница, РольГусеницы, ПравдивостьГусеницы),
      		персонаж(ящерица, РольЯщерицы, ПравдивостьЯщерицы),
      		персонаж(кот, РольКота, ПравдивостьКота)
      	]):-
      		возможная_роль(РольГусеницы), 
      		возможная_роль(РольЯщерицы), 
      		возможная_роль(РольКота), 
      		
      		возможная_истинность(ПравдивостьГусеницы), 
      		возможная_истинность(ПравдивостьЯщерицы), 
      		возможная_истинность(ПравдивостьКота).
      		
      	сказал(гусеница, Гипотеза):-
      		%гусеница сказала что соль съела ящерица
      		входит_в(персонаж(ящерица, вор, _Правдивость), Гипотеза).
      	сказал(ящерица, Гипотеза):- 
      		%ящерица сказала, что гусеница сказала правду
      		входит_в(персонаж(гусеница, вор, _Правдивость), Гипотеза).
      	сказал(кот, Гипотеза):-
      		% кот никогда не ел соль
      		входит_в(персонаж(кот, не_вор, _Правдивость), Гипотеза).
      		
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      		входит_в(Элемент, Хвост_списка).
      		
      	проверка_гипотезы(Гипотеза):-
      		findall(Лжец, входит_в(персонаж(Лжец, РольЛжеца, ложь), Гипотеза), Солгали),
      		findall(Честный, входит_в(персонаж(Честный, РольЧестного, правда), Гипотеза), СказалиПравду),
      		
      		количество(Солгали, КоличествоЛжецов),
      		количество(СказалиПравду, КоличествоЧестных),
      		КоличествоЛжецов >= 1, КоличествоЧестных >= 1,
      		
      		проверка_высказывания(гусеница, Гипотеза),
      		проверка_высказывания(ящерица, Гипотеза),
      		проверка_высказывания(кот, Гипотеза).
      		
      	количество([], 0).
      	количество([_Первый|Остальные], Количество):-
      		количество(Остальные, КоличествоОстальных),
      		Количество = КоличествоОстальных+1.
      		
      	проверка_высказывания(Имя, Гипотеза):-
      		входит_в(персонаж(Имя, _Роль, правда), Гипотеза),
      		сказал(Имя, Гипотеза).
      	проверка_высказывания(Имя, Гипотеза):-
      		входит_в(персонаж(Имя, _Роль, ложь), Гипотеза),
      		NOT(сказал(Имя, Гипотеза)).
      		
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 3

      DOMAINS 
      	имя = гусеница; ящерица; кот
      	роль = вор; не_вор
      	истинность = правда;ложь
      	
      	структура_гипотезы = персонаж(имя, роль, истинность)
      	
      	гипотеза = структура_гипотезы*
      	
      	имена = имя*
      PREDICATES      
             nondeterm возможное_имя(имя)
             nondeterm возможная_роль(роль)
             nondeterm возможная_истинность(истинность)
             
             nondeterm входит_в(структура_гипотезы, гипотеза)
             
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             nondeterm проверка_высказывания(имя, гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             
             nondeterm количество(имена, integer)
             
             nondeterm поиск_решения(имя)
      CLAUSES 
      	возможное_имя(гусеница).
      	возможное_имя(ящерица).
      	возможное_имя(кот).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
      	возможная_истинность(правда).
      	возможная_истинность(ложь).
      	
      	генерация_гипотезы([
      		персонаж(гусеница, РольГусеницы, ПравдивостьГусеницы),
      		персонаж(ящерица, РольЯщерицы, ПравдивостьЯщерицы),
      		персонаж(кот, РольКота, ПравдивостьКота)
      	]):-
      		возможная_роль(РольГусеницы), 
      		возможная_роль(РольЯщерицы), 
      		возможная_роль(РольКота), 
      		
      		возможная_истинность(ПравдивостьГусеницы), 
      		возможная_истинность(ПравдивостьЯщерицы), 
      		возможная_истинность(ПравдивостьКота).
      		
      	сказал(гусеница, Гипотеза):-
      		%гусеница сказала что соль съела ящерица
      		входит_в(персонаж(ящерица, вор, _Правдивость), Гипотеза).
      	сказал(ящерица, Гипотеза):- 
      		%ящерица сказала, что гусеница сказала правду
      		%входит_в(персонаж(гусеница, вор, _Правдивость), Гипотеза).
      		сказал(гусеница, Гипотеза).
      	сказал(кот, Гипотеза):-
      		% кот никогда не ел соль
      		входит_в(персонаж(кот, не_вор, _Правдивость), Гипотеза).
      		
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      		входит_в(Элемент, Хвост_списка).
      		
      	проверка_гипотезы(Гипотеза):-
      		findall(Лжец, входит_в(персонаж(Лжец, РольЛжеца, ложь), Гипотеза), Солгали),
      		findall(Честный, входит_в(персонаж(Честный, РольЧестного, правда), Гипотеза), СказалиПравду),
      		
      		количество(Солгали, КоличествоЛжецов),
      		количество(СказалиПравду, КоличествоЧестных),
      		КоличествоЛжецов >= 1, КоличествоЧестных >= 1,
      		
      		проверка_высказывания(гусеница, Гипотеза),
      		проверка_высказывания(ящерица, Гипотеза),
      		проверка_высказывания(кот, Гипотеза).
      		
      	количество([], 0).
      	количество([_Первый|Остальные], Количество):-
      		количество(Остальные, КоличествоОстальных),
      		Количество = КоличествоОстальных+1.
      		
      	проверка_высказывания(Имя, Гипотеза):-
      		входит_в(персонаж(Имя, _Роль, правда), Гипотеза),
      		сказал(Имя, Гипотеза).
      	проверка_высказывания(Имя, Гипотеза):-
      		входит_в(персонаж(Имя, _Роль, ложь), Гипотеза),
      		NOT(сказал(Имя, Гипотеза)).
      		
      	поиск_решения(Вор):-
      		генерация_гипотезы(Гипотеза),
              	проверка_гипотезы(Гипотеза),
              	findall(Имя, входит_в(персонаж(Имя, вор, _Правдивость), Гипотеза), Воры),
              	Воры = [Вор].
      GOAL    
              поиск_решения(ИмяВора).
      

      Решение 4

      DOMAINS 
      	имя = гусеница; ящерица; кот
      	роль = вор; не_вор
      	истинность = правда;ложь
      	
      	структура_гипотезы = персонаж(имя, роль, истинность)
      	
      	гипотеза = структура_гипотезы*
      	
      	имена = имя*
      PREDICATES      
             nondeterm возможное_имя(имя)
             nondeterm возможная_роль(роль)
             nondeterm возможная_истинность(истинность)
             
             nondeterm входит_в(структура_гипотезы, гипотеза)
             nondeterm входит_в(имя, имена)
             
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             nondeterm проверка_высказывания(имя, гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             
             nondeterm количество(имена, integer)
             
             nondeterm поиск_решения(имя)
             
             nondeterm без_повторов(имена, имена, имена)
             nondeterm поиск_решений_без_повторов(имена)
      CLAUSES 
      	возможное_имя(гусеница).
      	возможное_имя(ящерица).
      	возможное_имя(кот).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
      	возможная_истинность(правда).
      	возможная_истинность(ложь).
      	
      	генерация_гипотезы([
      		персонаж(гусеница, РольГусеницы, ПравдивостьГусеницы),
      		персонаж(ящерица, РольЯщерицы, ПравдивостьЯщерицы),
      		персонаж(кот, РольКота, ПравдивостьКота)
      	]):-
      		возможная_роль(РольГусеницы), 
      		возможная_роль(РольЯщерицы), 
      		возможная_роль(РольКота), 
      		
      		возможная_истинность(ПравдивостьГусеницы), 
      		возможная_истинность(ПравдивостьЯщерицы), 
      		возможная_истинность(ПравдивостьКота).
      		
      	сказал(гусеница, Гипотеза):-
      		%гусеница сказала что соль съела ящерица
      		входит_в(персонаж(ящерица, вор, _Правдивость), Гипотеза).
      	сказал(ящерица, Гипотеза):- 
      		%ящерица сказала, что гусеница сказала правду
      		%входит_в(персонаж(гусеница, вор, _Правдивость), Гипотеза).
      		сказал(гусеница, Гипотеза).
      	сказал(кот, Гипотеза):-
      		% кот никогда не ел соль
      		входит_в(персонаж(кот, не_вор, _Правдивость), Гипотеза).
      		
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      		входит_в(Элемент, Хвост_списка).
      		
      	проверка_гипотезы(Гипотеза):-
      		findall(Лжец, входит_в(персонаж(Лжец, РольЛжеца, ложь), Гипотеза), Солгали),
      		findall(Честный, входит_в(персонаж(Честный, РольЧестного, правда), Гипотеза), СказалиПравду),
      		findall(Вор, входит_в(персонаж(Вор, вор, ВорСказал), Гипотеза), Воры),
      		
      		количество(Воры, 1), % вор только один
      		количество(Солгали, КоличествоЛжецов),
      		количество(СказалиПравду, КоличествоЧестных),
      		КоличествоЛжецов >= 1, КоличествоЧестных >= 1,
      		
      		проверка_высказывания(гусеница, Гипотеза),
      		проверка_высказывания(ящерица, Гипотеза),
      		проверка_высказывания(кот, Гипотеза).
      		
      	количество([], 0).
      	количество([_Первый|Остальные], Количество):-
      		количество(Остальные, КоличествоОстальных),
      		Количество = КоличествоОстальных+1.
      		
      	проверка_высказывания(Имя, Гипотеза):-
      		входит_в(персонаж(Имя, _Роль, правда), Гипотеза),
      		сказал(Имя, Гипотеза).
      	проверка_высказывания(Имя, Гипотеза):-
      		входит_в(персонаж(Имя, _Роль, ложь), Гипотеза),
      		NOT(сказал(Имя, Гипотеза)).
      		
      	поиск_решения(Вор):-
      		генерация_гипотезы(Гипотеза),
              	проверка_гипотезы(Гипотеза),
              	findall(Имя, входит_в(персонаж(Имя, вор, _Правдивость), Гипотеза), Воры),
              	Воры = [Вор].
              	
        	без_повторов([], Буфер, БезПовторов):-
          		БезПовторов = Буфер.
        	без_повторов([ПервыйЭлемент|ОстальныеЭлементы], Буфер, БезПовторов):-
          		входит_в(ПервыйЭлемент, Буфер), 
          		без_повторов(ОстальныеЭлементы, Буфер, БезПовторов).
        	без_повторов([ПервыйЭлемент|ОстальныеЭлементы], Буфер, БезПовторов):-
          		NOT(входит_в(ПервыйЭлемент, Буфер)),
          		без_повторов(ОстальныеЭлементы, [ПервыйЭлемент|Буфер], БезПовторов).
          		
          	поиск_решений_без_повторов(Решения):-
          		findall(Решение, поиск_решения(Решение), ВсеРешения),
          		без_повторов(ВсеРешения, [], Решения).
          
      GOAL    
              поиск_решений_без_повторов(ИмяВора).
      

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×