1

我是 Prolog 的新手，我想编写一个函数，它返回所有不同的方式来换一美元（100 美分）。我们有 2 美分硬币、11 美分硬币、38 美分硬币，有趣的是，还有 -8 美分硬币（价值 -8 美分的硬币）。此外，我们总共只有 10 枚“-8”美分硬币。（其他种类的硬币没有上限）

这是我的尝试：

change100([P2, P11, P38, Pn8]):- 
    Pn8 =< 10,
    Pn8 >= 0,
    P2 >= 0, P11 >= 0, P38 >= 0,
    D is 2 * P2 + 11 * P11 + 38 * P38 - 8 * Pn8,
    D = 100.

但它不起作用。当我运行它并查询时

?- change100(A).

我收到消息

ERROR:

=< /2: Arguments are not sufficiently instantiated.

为什么是这样？我该如何解决？

原始问题陈述：

硬币有 4 种：2 美分、11 美分、38 美分，有趣的是，-8 美分（价值-8 美分的硬币）。更有趣的是，总共只制作了 10 -8 美分的作品，因此您无需担心超过 10 -8 美分的情况。

一美元（100 美分）有多少种不同的方法？

例如，为 100 美分找零的一种方法是使用 4 个 2 美分、8 个 11 美分、2 个 38 美分和 9 个 -8 美分。

有可能有 0 个硬币，例如 50 个 2 美分硬币是为一美元找零的一种方法。

编写一个名为 change100(Coins) 的 Prolog 函数，其开头如下：

  change100([P2, P11, P38, Pn8]) :-
       % ...

P2 是 2 美分硬币的数量，P11 是 11 美分硬币的数量，依此类推。请记住，如问题描述中所述，Pn8 最多为 10。

4

1 回答 1

1

要在数值不等式中使用，Prolog 中的变量必须被实例化。

您的代码尝试在算术上比较未实例化的变量，这不是 Prolog 可以做的。

但是你可以使用所谓的“约束逻辑编程”——Prolog 扩展来解决这个问题。

这是 SWI-Prolog 中的代码（几乎与您的原始代码相同）：

:- use_module(library(clpfd)).
change100([P2, P11, P38, Pn8]):- 
    Pn8 #=< 10,
    Pn8 #>= 0,
    P2 #>= 0, P11 #>= 0, P38 #>= 0,
    D #= 2 * P2 + 11 * P11 + 38 * P38 - 8 * Pn8,
    D #= 100,
    label([P2, P11, P38, Pn8]).

更新。

可以验证您使用该程序获得了 195 种不同的解决方案。

您提到应该有 108 种不同的解决方案。在不正确假设硬币数量乘以硬币价值应小于或等于 100（即不超过 100/2=50 个价值 2 的硬币）的情况下，可以获得该解决方案的数量。如果我们只有正硬币，这个假设是正确的，但是对于这个问题，这个假设会导致例如“90 * 2 + 0 * 11 + 0 * 38 - 10 * 8”的遗漏。

要模拟这种不正确的逻辑并获得 108 个解决方案，您可以2 * P2 #=< 100, 11 * P11 #=<100, 38 * P38 #=< 100,在程序中添加一行。但请争辩说，确实有 195 种解决方案。

于 2014-03-19T03:16:36.247 回答