Пролог: сдача монет

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

изменить (M, P, N, D) с формулой, что M> = 0 и M = P + 5 * N + 10 * D вот мой подход

change(M,P,N,D) :-
     M is P+5*N+10*D,
     P is M - (5*N+10*10).

пара тест-кейсов

  change(100,10,8,5).
  True
  change(X,10,8,5).
  X = 100.

Однако, если я попытаюсь

 change(100,P,8,5).

это дает мне «Аргументы недостаточно конкретизированы» вместо P = 10. Что это вызывает?

редактировать: исправьте мой код, используя предикат между между (0, M, P), между (0, M, N), между (0, M, D), M равно P + 5 * N + 10 * D.


prolog coin-change
person boxy    schedule 01.04.2015    source источник
comment
возможный дубликат Пролог разбивает деньги на меньшие суммы   -  person    schedule 01.04.2015
comment
Причина, по которой вы получаете ошибку, заключается в том, что is/2 оценивает арифметическое выражение: это не чисто логический предикат. Кажется, вы уже знаете по крайней мере один способ решить эту проблему; см. дубликат вопроса и ответ на лучший способ.   -  person    schedule 01.04.2015

Ответы (1)


arrow_upward
5
arrow_downward

Используйте clpfd!

:- use_module(library(clpfd)).

Все, что нам нужно, чтобы выразить change/4, — это одно уравнение:

change(Money,Pennies,Nickels,Dimes) :-
   Money #= Pennies + Nickels*5 + Dimes*10.

Давайте запустим наземный запрос, заданный OP!

?- change(100,10,8,5).
true.

Далее четыре запроса с ровно одной переменной:

?- change(Money,10,8,5).
Money = 100.

?- change(100,Pennies,8,5).
Pennies = 10.

?- change(100,10,Nickels,5).
Nickels = 8.

?- change(100,10,8,Dimes).
Dimes = 5.

Поскольку мы используем clpfd, мы также можем задавать дополнительные вопросы. общие запросы, такие как этот с тремя переменными:

?- change(100,Pennies,Nickels,Dimes).
100 #= Pennies + 5*Nickels + 10*Dimes.

Обратите внимание, что это (пока) не перечисляет все возможные комбинации... для этого требуется два шага:

  1. Укажите, что «все счетчики неотрицательны», используя ins/2:

    ?- [Pennies,Nickels,Dimes] ins 0..sup,
   change(100,Pennies,Nickels,Dimes).
100 #= Pennies + 5*Nickels + 10*Dimes,
Pennies in 0..100,
Nickels in 0..20,
Dimes   in 0..10.

  2. Используйте предикат перечисления labeling/2:

    ?- Zs = [Pennies,Nickels,Dimes],
   Zs ins 0..sup,
   change(100,Pennies,Nickels,Dimes),
   labeling([],Zs).
  Pennies = 0  , Nickels = 0, Dimes = 10
; Pennies = 0  , Nickels = 2, Dimes = 9
; Pennies = 0  , Nickels = 4, Dimes = 8
% the next 115 answers were omitted for the sake of brevity
; Pennies = 90 , Nickels = 2, Dimes = 0
; Pennies = 95 , Nickels = 1, Dimes = 0
; Pennies = 100, Nickels = 0, Dimes = 0
; false.
person repeat    schedule 04.08.2015