麻烦斐波那契数生成

下面是我的第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

我试图找到bug，但失败了。如何解决这个问题？

来源

2013-03-08 Md. Arafat Al Mahmud

对于初学者来说，

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-08 18:28:20

首先，你f/2是不 OK：

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

因为第一个参数必须是完全实例化的数字，与>和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-09 14:57:52

麻烦斐波那契数生成

回答

相关问题