Алиса в стране чудес — Prolog. В некоторой далекой стране

      Комментарии к записи Алиса в стране чудес — Prolog. В некоторой далекой стране отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Алиса в стране чудес — Prolog. В некоторой далекой стране

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 2 мес. назад.

  • Автор
    Сообщения
  • #2056

    questioner
    Участник

    Нужно решение задачи на Visual Ptolog 5.2 или Turbo Prolog.

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

    Преподаватель запретил использовать в программе отсечения.

  • #2058

    Рыцарь всегда говорит правду, а шпион — всегда врет, т.е. в любом случае они не могут дать сразу два утверждения.
    Утверждения мы поместим в базу данных. Так, например, информация о том, что второй человек является шпионом может быть записана так: [_A, shpion, _C]. Первый и последний элемент списка не связан, т.е. он может иметь любое значение — возникает проблема сравнения таких записей. Поэтому в базе данных я бы хранил сразу наборы высказываний (это не единственное решение, но мне оно кажется самым простым).

    Объявим типы данных — юнит (может являться рыцарем, лжецом или шпионом), одно высказывание (список юнитов), набор высказываний:

    domains
    	unit=ricar;shpion;lzhec
    	units=unit*
    	says = units*

    В разделе predicates опишем прототипы используемых функций:

    predicates
    	nondeterm solve(units)
    	nondeterm try(unit) 
    	
    	say(integer, says)
    	
    	nondeterm can_be_ricar_or_lzhec(integer)
    	
    	nondeterm length(says, integer)
    	nondeterm pos(unit, units, integer)
    	
    	nondeterm process(integer, units)
    	nondeterm processSays(units, says)

    Функция solve используется для подбора решения (перебора всех видов персонажей):

    try(ricar).
    try(lzhec).
    try(shpion).

    Правило length является стандартным, однако оно немного изменено в связи с тем, что запрещено использовать оператор отсечения в Prolog:

    length(List, Length):-
      List = [], Length = 0;
      List = [_Head|Tail], length(Tail, TailLength), Length = TailLength + 1.

    Функция pos возвращает позицию элемента с заданным значением в списке. Если элемента нет, то правило завершится неудачей — мы используем это чтобы гарантировать, что решение содержит обязательно одного лжеца, одного шпиона и одного рыцаря.

    pos(Element, [Element|_Tail], 0).
    pos(Element, [Head|Tail], Index):-
      NOT(Element=Head),
      pos(Element, Tail, TailPos), 
      Index = TailPos + 1.

    Если первый элемент списка содержит искомое значение — функция возвращает ноль, т.к. мы решили с нуля начинать индексацию элементов. Вернув ноль стоило бы поставить оператор отсечения, однако т.к. его использование запрещено — остальные ветви алгоритма должны выполнять дополнительную проверку чтобы убедиться, что первый элемент не является искомым. Рекурсивным вызовом обрабатываются элементы списка, за исключением первого, поэтому к полученному результату добавляется единица.

    Предикат nondeterm can_be_ricar_or_lzhec проверяет возможность размещения рыцаря или лжеца на заданной позиции. Они оба могли дать только одно утверждение — поэтому достаточно получить список их высказываний и сравнить его длину с единицей:

    can_be_ricar_or_lzhec(Index):-
      say(Index, Says), length(Says, 1).

    В базе данных хранится информация о высказываниях юнита с заданным номером:

    say(0, [[_A, shpion, _C]]).
    say(1, [[_A, _B, shpion]]).
    say(2, [[shpion, _B, _C], [_A, shpion, _C]]).

    Функция solve выполняет поиск решения логической задачи, для этого запрашивает генерацию всех возможных сочетаний из трех юнитов. Юниты помещаются в список. Вызовом функций pos находятся позиции каждого типа юнита, а также гарантируется наличие каждого типа юнита в списке (иначе позицию определить невозможно). Проверяется возможность размещения рыцаря и лжеца на текущих позициях, а затем, для этих позиций вызывается функция process.

    solve(Solution):-
      try(A), try(B), try(C), 
      Solution = [A, B, C],
      pos(lzhec, Solution, LzhecPos), pos(ricar, Solution, RicarPos), pos(shpion, Solution, _ShpionPos),
    		
      can_be_ricar_or_lzhec(LzhecPos), can_be_ricar_or_lzhec(RicarPos),
    		
      process(RicarPos, Solution), NOT(process(LzhecPos, Solution)).

    Функция process принимает текущее решение и проверяет его на соответствие высказываниям юнита с заданным номером. В связи с этим для лжеца результат ее работы должен быть инвертирован оператором NOT. Функция извлекает из базы все высказывания персонажа и пытается применить их всех к решению (используя вспомогательную функцию processSays):

    process(Index, Solution):-
      say(Index, Says), processSays(Solution, Says).
    		
    processSays(_Solution, []).
    processSays(Solution, [HeadSay|TailSays]):-
      Solution = HeadSay, processSays(Solution, TailSays).

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

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