Prolog :: f(x)递归

Question

我是Prolog的初学者,有两个要求:

1. f(1) = 1

2. 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(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正确指出的那样,使用这些术语本身是不够的,因为这些术语与它们的算术评估不同.具体而言,-(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太难理解了.将在实例化错误下提交的许多相关问题  作为证据,并参见clpfd以获取声明性解决方案.