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).

したがって、2つの問題があります。1つは、Yを生成してから破棄していることです。これは、シングルトン警告で警告されているはずです。シングルトン警告には、変数を_に置き換えることで常に対応する必要があります。これがあなたのコードをナンセンスに変えるように見えるなら、あなたのコードはナンセンスです。:)

もう1つの問題は、それ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)が 3 番目のルールと再照合され、元に戻らずに一方向に負の数になります。相互に排他的な句を使用すると、この不一致がブロックされ、述語が決定論的になります。

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。

したがって、2 番目の述語fgen(A,B). 少し不明確ですが、インデックスになるf(A,T)ことを意図している呼び出しとそれに対応するフィボナッチ数から判断すると、一連の回答が 1 つずつ生成されます。インデックスを列挙するために、定義できますAB(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、線形の長さの実行スタックを作成します。2 番目のバージョンは、一定のスタック スペースで実行されます。

もちろん、あなたf/2は二重再帰的であるため、これまでよりもはるかに早くスタックを使い果たしますnatural。

于 2013-03-09T14:57:52.350 に答える