Prolog::f(x) 递归

Question

我是 Prolog 的初学者，有两个要求：

f(1) = 1
f(x) = 5x + x^2 + f(x - 1)

规则：

f(1,1). f(X,Y) :- Y is 5 * X + X * X + f(X-1,Y).

查询：

f(4,X).

输出：

ERROR: is/2: Arguments are not sufficiently instantiated

如何增加 f(X-1) 的值？

Answer 1

问题是您试图将 f(X-1,Y) 当作一个数字来求值，但当然它是一个可能为真或为假的谓词。经过一些修补，我找到了这个解决方案：

f(1,1).
f(X,Y) :- X > 0, Z is X-1, f(Z,N), Y is 5*X + X*X + N.

诀窍是让它首先找到到达 f(1,N) 的路径，而不评估任何东西；然后通过满足 Y is 5*X + X*X + N 让结果冒出来。在 Prolog 中，顺序对其搜索很重要。它需要满足 f(Z,N) 才能使语句 Y is 5*X + X*X + N.

的值为 N

另外，注意条件 X > 0 以避免无限递归。

Answer 2

这可以通过使用辅助变量.

轻松解决

例如，考虑：

f(1, 1).
f(X, Y) :-
        Y #= 5*X + X^2 + T1,
        T2 #= X - 1,
        f(T2, T1).

这是您给出的规则的直接翻译，使用辅助变量 T1 和 T2 代表部分表达式 f(X-1) 和 X-1。正如@BallpointBen 正确指出的那样，仅使用术语本身是不够的，因为这些术语不同于它们的算术 evaluation。特别是，-(2,1) 不是整数 1，但 2 - 1 #= 1 成立！

根据您的 Prolog 系统，您目前可能还需要导入一个库来使用谓词 (#=)/2，它表示等式个 整数表达式.

您的示例查询现在已经产生了一个解决方案：

?- f(4, X).
X = 75 .

请注意，在这种情况下，谓词不会普遍终止：

?- f(4, X), false.
nontermination

我们可以很容易地通过附加约束来做到这一点：

f(1, 1).
f(X, Y) :-
        X #> 1,
        Y #= 5*X + X^2 + T1,
        T2 #= X - 1,
        f(T2, T1).

现在我们有：

?- f(4, X).
X = 75 ;
false.

请注意，我们可以将其用作真正的关系，同样在 最一般的情况下 :

?- f(X, Y).
X = Y, Y = 1 ;
X = 2,
Y = 15 ;
X = 3,
Y = 39 ;
X = 4,
Y = 75 ;
etc.

基于低级算法的版本通常只涵盖此类查询实例的非常有限的子集。因此，我建议您使用 (#=)/2 而不是 (is)/2 的 。尤其对于初学者来说，使用 (is)/2 太难理解了。将 instantiation-error as evidence, and see clpfd 下的许多相关问题作为声明性解决方案。

Prolog::f(x) 递归

Prolog:: f(x) recursion

recursion

prolog

arithmetic-expressions

instantiation-error