私は SWI Prolog を使用して Prolog を学習していますが、フィボナッチ数計算プログラムの次の 2 つのソリューションについて疑問があります。
最初のものはこれです：
fib(1,1).
fib(2,1).
fib(N,F) :- N > 2,
N1 is N-1,
fib(N1,F1),
N2 is N-2,
fib(N2,F2),
F is F1+F2.
それがどのように機能するかは非常に明確で、非常に簡単です。
次に、コードを読むと前のバージョンと同じように機能するように見えるこの2番目のバージョンがありますが、その後、Nのフィボナッチ数を計算し、asserta/2述語によってPrologデータベースに保存して、後で再利用します。
たとえば、10 のフィボナッチ数と 11 のフィボナッチ数を計算すると、12 のフィボナッチ数を計算するときに、前の 2 つの計算の結果を使用することになります。
だから私のコードは次のとおりです。
:-dynamic fibDyn/2.
fibDyn(1,1).
fibDyn(2,1).
fibDyn(N,F) :- N > 2,
N1 is N-1,
fibDyn(N1,F1),
N2 is N-2,
fibDyn(N2,F2),
F is F1+F2,
asserta(fibDyn(N,F)).
ロジックは前のものと同じであるように私には思えます：
N>2 の場合、F は N のフィボナッチ数であり、再帰を使用して N のフィボナッチ数を計算します (前の例のように)。
すでに計算してデータベースに入れている数のフィボナッチ数の数を計算するように依頼すると、プログラムはより高速になると思いますが、それは動作するように思えます。奇妙な方法: 速すぎて、非常に大きな整数のフィボナッチ数を直接計算できます (他のバージョンでは、このような大きな数ではうまくいきません)。
もう 1 つの奇妙な点は、クエリのトレースを実行すると、次のような結果が得られることです。
[trace] ?- fibDyn(200,Fib).
Call: (6) fibDyn(200, _G1158) ? creep
Exit: (6) fibDyn(200, 280571172992510140037611932413038677189525) ? creep
Fib = 280571172992510140037611932413038677189525 .
ご覧のとおり、フィボナッチ述語のコードを実行するのではなく、直接結果を取得しているようです (どこから?!?!)
このクエリを (最初のバージョンを使用して) 実行すると、プログラムがそれを計算することがわかります。
[trace] ?- fib(3,Fib).
Call: (6) fib(3, _G1158) ? creep
^ Call: (7) 3>2 ? creep
^ Exit: (7) 3>2 ? creep
^ Call: (7) _G1233 is 3+ -1 ? creep
^ Exit: (7) 2 is 3+ -1 ? creep
Call: (7) fib(2, _G1231) ? creep
Exit: (7) fib(2, 1) ? creep
^ Call: (7) _G1236 is 3+ -2 ? creep
^ Exit: (7) 1 is 3+ -2 ? creep
Call: (7) fib(1, _G1234) ? creep
Exit: (7) fib(1, 1) ? creep
^ Call: (7) _G1158 is 1+1 ? creep
^ Exit: (7) 2 is 1+1 ? creep
Exit: (6) fib(3, 2) ? creep
Fib = 2 .
なんで？2 番目のバージョン ( asserta述語を使用するバージョン) は、2 つの数値のフィボナッチ数を計算し、これらの値を使用して次の解を生成することを期待します。
たとえば、次のような状況が考えられます:フィボナッチ数をまだ計算したことがなく、N=4 のフィボナッチ数を計算するように要求して、それを計算します (2 番目に投稿されたスタックトレースのように)。
そこで、N=5 のフィボナッチ数を計算するように依頼すると、彼は保存された N=4 のフィボナッチ数を使用します。そこで、N=6 のフィボナッチ数を計算するように依頼すると、保存された 4 と 5 のフィボナッチ数を最終的に使用できます。
私は何が欠けていますか？理解するのを手伝ってもらえますか?