-1

なぜフィボナッチの再帰的手順がこれほど長く機能するのですか？

これはOCamlにあります：

let rec fib n = if n<2 then n else fib (n-1) + fib (n-2);;

これはMathematicaにあります：

Fib[n_] := If[n < 2, n, Fib[n - 1] + Fib[n - 2]]

これはJavaです：

public static BigInteger fib(long n) {
    if( n < 2 ) {
        return BigInteger.valueOf(n);
    }
    else {
        return fib(n-1).add(fib(n-2));
    }
}

それは長い間機能するからです。なぜなら、それは時間内にノードをn=100持つツリーをトレースするからだと思います。2^100

ただし、生成する数値は100しかないため、100のメモリレジスタと100の計算タクトを消費する可能性があります。

したがって、実行を最適化することができます。

このタスクは何についてであり、どのように解決されますか？ソリューションはMathematicaに実装されていないので、おそらく存在しません。この問題に関する研究はどうですか？

4

3 に答える 3

7

これは、メモ化の価値を示すために使用される典型的な例です。だから、それはそれをより速くするための1つのアプローチです。

（フィボナッチ数をすばやく計算したい場合は、もちろん、関数を書き直して非常に速く答えを得るのは非常に簡単です。0から始めてnまで進み、毎回前の2つのフィボナッチ数を渡します。）

于 2013-01-22T07:22:34.050 に答える
1

@JeffreyScofieldの回答のように、メモ化が進むべき道だと思います。定義 ：

Fib2[n_] := Fib2[n] = If[n < 2, n, Fib2[n - 1] + Fib2[n - 2]]

小切手 ：

Fib[30] // AbsoluteTiming
(* {9.202920, 832040} *)

Fib2[30] // AbsoluteTiming
(* {0., 832040} *)

Fib2[100] // AbsoluteTiming
(* {0.001000, 354224848179261915075} *)
于 2013-01-22T08:48:44.667 に答える
-2

n = 100の場合でも、再帰的なフィボナッチ数列の場合、操作にそれほど時間はかからないはずです。再帰的であろうと反復的であろうと、一定時間で実行される以前の数値を合計するだけなので、O（N）時間で実行する必要があります。計算にはおよそどのくらい時間がかかりますか？

于 2013-01-22T07:23:11.943 に答える