Prolog：硬币变化

Question

我是prolog的新手，正在尝试解决这个经典的硬币找零问题。

change(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).

它给了我 "Arguments are not sufficiently instantiated" 而不是 P = 10。这是什么原因造成的？

编辑：使用 between predicate 修复我的代码 between(0,M,P),between(0,M,N),between(0,M,D),M为P+5*N+10*D.

Answer 1

使用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.

请注意，这并没有（还）列举所有可能的组合...这样做需要两个步骤：

使用ins/2声明"all counts are non-negative":

?- [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.

使用枚举谓词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.

Prolog：硬币变化

Prolog : coin change

prolog

coin-change