麻煩斐波那契數生成

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

麻煩斐波那契數生成

回答

相關問題