9

このロジック プログラミングは、私の命令型プログラミング スキルに本当に拍車をかけています。これは宿題なので、私に答えを落とさないでください。これは私が持っているものです:

fibo(N,1) :-
   N < 2,
   !. 
fibo(N,R) :-
   N1 is N-1,
   N2 is N-2,
   fibo(N1,R1),
   fibo(N2,R2),
   R is R1+R2.

次のような別の関数を作成するとします。fib(N,Value,LastValue). Nは n 番目の数値、value は戻り値です。累積を使用してこれを書き換える方法がわかりません。また、逆方向にカウントするため、何かを計算する前に最後の値を「知る」方法がわかりません。:s 任意の入力を歓迎します。

4

5 に答える 5

5

ここに解決策を投稿することもできますが、これは宿題であるため、非生産的です。代わりに、ここにリードがあります：

あなたがリストしたフィボナッチのバージョンの問題は、それが非効率的であることです。を呼び出すたびにfibo/2別の2 つの呼び出しが発生しますが、これらの呼び出しの一部は同じフィボナッチ数の値を計算します。たとえば、擬似コードでは次のようになります。

(a) fibo(4) -> fibo(3), fibo(2)
(b) fibo(3) -> fibo(2), fibo(1)
(c) fibo(2) -> fibo(1), fibo(0) % called from (a)
(d) fibo(2) -> fibo(1), fibo(0) % called from (b), redundant

この欠点を克服するために、最後の値だけでなく最後の 2 つの値を返すという観点からフィボナッチを言い換えて、各呼び出しがfib/31 回の再帰呼び出しのみを引き起こすようにするように求められました (したがって、フィボナッチ数列を線形時間で計算します)。基本ケースを次のように変更する必要があります。

fib(1,1,0).
fib(2,1,1).

再帰的なケースはあなたに任せます。

せっかちな人向け

ここにも再帰的なケースがあります:

fib(N, Val, Last) :-
  N > 2,
  N1 is N - 1,
  fib(N1, Last, Last1), % single call with two output arguments, 
                        % instead of two calls with one output argument
  Val is Last + Last1.
于 2010-11-23T20:16:03.257 に答える
2

関連する議論を参照してください。

SICStus Prolog によるフィボナッチ数列の一般化

そこから有限領域制約を使用して、非常に優れたソリューションを検討してください。

于 2010-11-23T10:19:58.147 に答える
1

おそらく、末尾再帰を使用するのが良いオプションです

編集: fib(6) を fib(5)+fib(4) に分割する代わりに、 fib(6) = fib(6,0,0) のようなものを試すことができます 最初のパラメーターは、0に達したときのステップ数です2 番目のパラメーターは最後に計算した値、3 番目のパラメーターは現在の 2 番目と 3 番目のパラメーターの合計に等しい計算する値です (0 + 0 が 1 になる最初のステップを除く)。 )

したがって、計算するには、各呼び出しで2番目のパラメーターを設定し、3番目に累積するので、 fib(6,0,0) => fib(5,0,1) => fib(4,1,1) => fib(3 ,1,2) => fib(2,2,3) => fib(1,3,5) => fib(0,5,8) の場合、8 を返します

その方法では、スタックオーバーフローを回避して、実際にアドレスリターンをスタックに保存する必要はありません

于 2010-11-23T17:23:29.760 に答える
0

フィボナッチ数列を計算する別の方法があることに注意してください: 基本ケースから開始して上に移動します。

今、 を計算するには、とfib(n)を足します。代わりに、それをひっくり返して、フィボナッチ数列の定義に基づいて計算し、そこから構築します。fib(n-1)fib(n-2)fib(0)fib(1)

于 2010-11-23T00:30:29.557 に答える
-1

あなたはほとんどすでにそれを持っています。書き直してください：

fibo(N, Value) :-
N1 is N-1, N2 is N-2,
 fibo(N1, LastValue),fibo(N2, SecondToLastValue),
 Value is LastValue + SecondToLastValue.

の面では

fibo2(N, Value, LastValue):- ...

累積を使用してこれを書き換える方法がわかりません

これは必要ありません (そうすることが可能ですが)。

于 2010-11-23T00:49:19.090 に答える