Помещик нанял двух крестьян и обещал дать каждому по 5 мер

      Комментарии к записи Помещик нанял двух крестьян и обещал дать каждому по 5 мер отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Помещик нанял двух крестьян и обещал дать каждому по 5 мер

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

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

    questioner
    Участник

    Задачу нужно решить двуме методами — поиском в глубину и в ширину:

    Помещик нанял двух крестьян и обещал по окончании раоты дать каждому по 5 мер овса. Когда работа была окончена, помещик велел отдать в распоряжение рабо­тавших крестьян 3 мешка: один мешок с 10 мерами овса, а два других, вместимостью 7 мер и 3 меры, пустые. Дру­гих мешков или других емкостей у крестьян не было, од­нако они разделили овес так, что каждый унес домой 5 мер овса. Как крестьяне произвели этот дележ?

    Помогите решить эту логическую задачу на SWI Prolog.

  • #1857

    В статье о решении логических задач описана пример про фермера, по образцу очень легко решить вашу задачу обходом в глубину.
    Схематично задача решалась так:

    1. описали способ хранения состояния задачи;
    2. фиксировали начальное и конечное состояние;
    3. определили функцию проверки корректности промежуточного состояния;
    4. определили функцию генерации новых состояний.
    5. задача решена.

    Я бы на вашем месте хранил состояние в списке, элемент которого — пара из вместимости мешка и массы груза в нем.
    Начальное и конечное состояния:

    state([(10, 10), (7, 0), (3, 0)]). % начальное
    state([(10, 5), (7, 5), (3, 0)]). % конечное

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

    check([]):-!.
    check([state(HV, HM)|T]):-
      HV >= HM, check(T).

    Правило генерации новых состояний пишется по шаблону. Для него нужно пересыпать содержимое мешков.

    % intersperse(((10, 10), (5, 3)), ((X, XV), (Y, YV))).
    % X = 10, XV = 8, Y = 5, YV = 5.
    intersperse(((From, From_m), (To, To_m)), ((From, RFrom_m), (To, RTo_m))):-
      DeltaTo is To - To_m, CanIntersperse is min(DeltaTo, From_m),
      RFrom_m is From_m - CanIntersperse, RTo_m is To_m + CanIntersperse.

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

    % intersperseList((10, 10), [(7,0), (3,0), (4,0)], R).
    % R = [ (10, 3), (7, 7), (3, 0), (4, 0)] ;
    % R = [ (10, 7), (7, 0), (3, 3), (4, 0)] ;
    % R = [ (10, 6), (3, 0), (7, 0), (4, 4)] ;
    % R = [ (4, 0), (3, 0), (7, 0)].
    intersperseList(From, ToList, Result):-
      intersperseList(From, [], ToList, Result).
     
    %intersperseList(From, Buf, ToList, Result).
    intersperseList(_From, Result, [], Result):-!.
    intersperseList(From, Buf, [H|T], Result):-
      intersperse((From, H), (NewFrom, NewH)),
      append([NewFrom|Buf], [NewH|T], Result).
    intersperseList(From, Buf, [H|T], Result):-
      intersperseList(From, [H|Buf], T, Result).

    Выбираете каждый мешок из списка, а для остальной части вызываете intersperseList. Каждый из списков, полученных в результате — это новое состояние.

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

    is_equal_state(A, B):-
      subtract(A, B, []).

    Что-то еще не получается?

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