Javascriptのフィボナッチ数列

フィボナッチ数は、最初の2つ以降のシリーズのすべての数が、前の2つの数の合計になるような数です。シリーズは1、1で始まります。例-

1, 1, 2, 3, 5, 8, 13, 21, 34, ….

次のようにn番目を生成するプログラムを書くことができます-

functionfibNaive(n) {
   if (n<= 1) return n;
   returnfibNaive(n - 1) + fibNaive(n - 2);
}

-

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

これにより、出力が得られます-

13
21
34
3

これらの関数呼び出しが実際にどのように行われているかを見てみましょう-

/**
* f(5)
* / \
* f(4) f(3)
* / \ / \
* f(3) f(2) f(2) f(1)
* / \ ..........
* f(2) f(1)..........
*/

f（5）を呼び出すと、f（2）がほぼ4回呼び出され、同じコードが4回以上実行されます。これは、重複するサブ問題の場合です。その関数を500秒間実行してみてください。これらの呼び出しはすべて時間がかかるため、行き詰まります。

5番目のフィボナッチ数が必要な場合は、低いフィボナッチ数を1回だけ必要としますが、それよりもはるかに多くの回数を計算します。代わりに計算値をどこかに保存するだけで、この冗長な計算を減らすことができます。これが動的計画法の核心です。

一度計算して後で再利用します。

記憶されているfib関数の実装を見てみましょう。

letfibStore = {};
functionfibDP(n) {
   if (n<= 1) return n;
if (fibStore[n]) {
   returnfibStore[n];
}
   fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
   returnfibStore[n];
}

現在、ストアfibStoreを使用して、すでに計算した値を追跡しています。これにより、過度の冗長な計算が減り、関数の効率が維持されます。

-

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

これにより、出力が得られます-

13
21
34
3

巨大な値についてこれをテストすることもできます。