Блог

Главная - Вопросы по программированию - Головоломка с днем рождения бабушки в CLP (FD)

Головоломка с днем рождения бабушки в CLP (FD)

prolog #clpfd

#пролог #clpfd

Вопрос:

Может ли Prolog решить эту головоломку с помощью CLP (FD)? Я вижу некоторую проблему
с CLP (FD), поскольку могут потребоваться дробные пирожные:

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

Комментарии:

1. Дробные пирожные не могут быть нужны. Если в какой-то момент у вас были дробные пирожные, у вас все равно будут дробные пирожные после следующего моста. Вы никогда не вернетесь к целому числу тортов, поэтому у вас не могло быть ровно 2 торта в конце. Поэтому у вас всегда должно быть целое количество тортов. Обратите внимание, что вместо TrollShare #= Cakes / 2 вы можете написать TrollShare * 2 #= Cakes .

Ответ №1:

Математик, возможно, сначала вывел бы и решил какую-то замкнутую
формулу или, возможно, увидел бы ее в мгновение ока. Но давайте сделаем немного пролога. Поскольку
я не был уверен, работает ли CLP (FD), я использовал CLP (Q).

Следующий код выполнил задание:

 :- use_module(library(clpq)).

grandmother(X,N,Y) :- N>1, !, M is N//2, 
      grandmother(X,M,H),
      K is N-M,
      grandmother(H,K,Y).
grandmother(X,1,Y) :- {Y = X/2 1}.

И результат действительно был интегральным, и, как можно
убедитесь, что все промежуточные шаги также будут составными:

 ?- grandmother(X,7,2).
X = 2.

Но если бы бабушка была в другой стране, например:

 grandmother(X,1,Y) :- {Y = X/3 5/4}.

Тогда результат не будет целым:

 ?- grandmother(X,7,2).
X = 1101r4.
Метки: