序言 : coin change

Question

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

用公式 M>=0 和 M = P+5*N+10*D 改变(M,P,N,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。这是什么原因造成的？

编辑:通过使用 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.

---

As we are using clpfd, we can also ask more general queries, like this one with three variables:

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