Javascript 中的斐波那契数列

斐波那契数列是指前两个数列之后的每个数列都是前两个数列之和的数列。该数列以 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 个斐波那契数时，我们只需要较低的斐波那契数一次，但我们计算它们的次数要多得多。如果我们只是将计算值存储在某处，我们可以减少这种冗余计算。这是动态规划的关键。

计算一次，以后再使用。

让我们看一下 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

您甚至可以对其进行测试以获得巨大的值。

相关文章

• Javascript 中的斐波那契数列
• JavaScript 中的动态编程