JavaScript中的斐波那契数列
斐波那契数是这样的数，使得该序列中前两个后的每个数字都是前两个的和。该系列从1、1开始。示例-
1, 1, 2, 3, 5, 8, 13, 21, 34, ….
我们可以编写一个程序来生成nth，如下所示：
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。由于所有这些调用将花费大量时间，因此您将陷入困境。
当我们需要第五个斐波那契数时，我们只需要较低的斐波那契数，但是我们计算它们的次数要多得多。如果仅将计算值存储在某个地方，则可以减少这种冗余计算。这是动态编程的关键。
计算一次，以后再使用。
让我们看一下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
您甚至可以测试它的巨大值。