JavaScript中的斐波那契数列

  • Z时代
  • 2024-01-10
  • 分类：综合

斐波那契数是这样的数，使得该序列中前两个后的每个数字都是前两个的和。该系列从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

您甚至可以测试它的巨大值。

以上是 JavaScript中的斐波那契数列 的全部内容， 来源链接： utcz.com/z/334734.html

回到顶部