1

以下是我的第 N 个斐波那契数查找谓词，可以：

f(0,0).
f(1,1).
f(N,R):-P is N-1,Q is N-2,f(P,T1),f(Q,T2),R is T1+T2.

我正在尝试使用以下谓词生成斐波那契数：

fgen(0,0).
fgen(1,1).
fgen(A,B):-fgen(X,Y),A is X+1,f(A,T),B is T.

当我查询时fgen(X,Y).

表明：

?- fgen(X,Y).

X = 0
Y = 0 ;

X = 1
Y = 1 ;

X = 1
Y = 1 ;
ERROR: Out of local stack

我使用了 trace 命令，结果如下：

?- trace,fgen(X,Y).
   Call: (9) fgen(_G281, _G282) ? creep
   Exit: (9) fgen(0, 0) ? creep

X = 0
Y = 0 ;
   Redo: (9) fgen(_G281, _G282) ? creep
   Exit: (9) fgen(1, 1) ? creep

X = 1
Y = 1 ;
   Redo: (9) fgen(_G281, _G282) ? creep
   Call: (10) fgen(_L178, _L189) ? creep
   Exit: (10) fgen(0, 0) ? creep
^  Call: (10) _G281 is 0+1 ? creep
^  Exit: (10) 1 is 0+1 ? creep
   Call: (10) f(1, _L179) ? creep
   Exit: (10) f(1, 1) ? creep
^  Call: (10) _G282 is 1 ? creep
^  Exit: (10) 1 is 1 ? creep
   Exit: (9) fgen(1, 1) ? creep

X = 1
Y = 1 ;
   Redo: (10) f(1, _L179) ? creep
^  Call: (11) _L207 is 1-1 ? creep
^  Exit: (11) 0 is 1-1 ? creep
^  Call: (11) _L208 is 1-2 ? creep
^  Exit: (11) -1 is 1-2 ? creep
   Call: (11) f(0, _L209) ? creep
   Exit: (11) f(0, 0) ? abort
% Execution Aborted

我试图找到错误，但失败了。如何解决问题？

4

2 回答 2

0

对于初学者，

fgen(A,B) :- fgen(X, Y), A is X+1, f(A, T), B is T.

是相同的

fgen(A,B) :- fgen(X, _), A is X+1, f(A, B).

所以你有两个问题。一个是您正在生成然后丢弃 Y，单例警告应该提醒您注意这一点。应始终通过用 _ 替换变量来响应单例警告；如果看起来这会使您的代码变成废话，那么您的代码就是废话。:)

另一个问题是这B is T是不必要的（is/2在这里使用而不是=/2什么都没有，因为右侧没有算术）。

所以让我们试试这个：

fgen(A, B) :- fgen(X, A), B is X + A.

这几乎可以工作：

?- fgen(X, Y).
X = Y, Y = 0 ;
X = Y, Y = 1 ;
X = Y, Y = 0 ;
X = 1,
Y = 2 ;
X = Y, Y = 0 ;
X = 2,
Y = 3 ;
X = Y, Y = 0 ;
X = 3,
Y = 5 ;
X = Y, Y = 0 ;
X = 5,
Y = 8 ;
X = Y, Y = 0 ;
X = 8,
Y = 13 ;
X = Y, Y = 0 ;
X = 13,
Y = 21 .

所有那些无意义的零都应该告诉你，你根本不需要你的第一个基本情况。毕竟，添加零不会改变任何事情。如果您删除该基本情况，您将获得所需的行为：

?- fgen(X, Y).
X = Y, Y = 1 ;
X = 1,
Y = 2 ;
X = 2,
Y = 3 ;
X = 3,
Y = 5 ;
X = 5,
Y = 8 ;
X = 8,
Y = 13 ;
X = 13,
Y = 21
于 2013-03-08T18:28:20.130 回答
0

首先，你f/2的不行：

6 ?- f(10,X).

X = 55 ;
ERROR: (user://2:68):
        Out of local stack

您的条款应互斥：

f(0,0).
f(1,1).
f(N,R):-N>1,
        P is N-1,Q is N-2,f(P,T1),f(Q,T2),R is T1+T2.

如果没有N>1测试，在重新开始时，最深的目标f(0,T2)将与第三条规则重新匹配，单向进入负数，永远不会返回。现在，使用互斥子句，这种不匹配被阻止并且谓词变得确定：

8 ?- f(10,X).

X = 55 ;

No

也许您尝试生成所有可能的值，但出现错误：

9 ?- f(A,B).

A = 0,    B = 0 ;    
A = 1,    B = 1 ;
ERROR: (user://5:147):
        Arguments are not sufficiently instantiated
^  Exception: (8) _G230>1 ? abort
% Execution Aborted

因为第一个参数必须是完全实例化的数字，才能与>and一起使用is。

因此，您的第二个谓词fgen(A,B). 有点不清楚，但从f(A,T)它打算A成为索引的调用来看，以及B它对应的斐波那契数，一个一个地生成答案序列(0,0) , (1,1) , (2,1), (3,2) , (4,3), (5,5) , (6,8) , ...。为了枚举索引，我们可以定义

% natural(0).
% natural(A):- natural(B), A is B+1.

natural(N):- znat(0,N).
znat(N,N).
znat(A,N):- B is A+1, znat(B,N).

然后简单地

fgen(A,B):- natural(A), f(A,B).

现在，

12 ?- fgen(A,B).

A = 0,    B = 0 ;    
A = 1,    B = 1 ;    
A = 2,    B = 1 ;    
A = 3,    B = 2 ;    
A = 4,    B = 3 ;    
A = 5,    B = 5 ;    
A = 6,    B = 8

第一个（注释掉的）版本natural/1创建了一个线性长度的执行堆栈。第二个版本在恒定堆栈空间中运行。

当然，你f/2是双重递归的，所以它会比以往任何时候都更早地耗尽堆栈natural。

于 2013-03-09T14:57:52.350 回答