Java程序斐波那契数列

Question

我正在编写一个“简单”程序来确定斐波那契数列中的第 N 个数。例如:序列中的第 7 个数字是:13。我已经完成了程序的编写，它可以工作，但是从第 40 个数字开始它开始延迟，并且花费的时间越来越长。我的程序必须排到系列中的第 100 位。

我该如何解决这个问题才不会花这么长时间？这是非常基础的程序，所以我不知道所有花哨的语法代码。我的公式是:

if n =1 || n = 0
   return n;

else 
    return F(n-1) + F(n-2);

在第 40 个任期过去之前，这一直很有效。我还必须添加什么其他声明才能使其更快地获得更高的数字？？

Answer 1

问题在于，因为您使用的是简单递归，所以您多次重新计算 F(n)，所以您的执行时间是指数级的。

有两种简单的方法可以解决这个问题:

1) F(n) 第一次求值时缓存它们的值。在评估 F(n) 之前先检查缓存，看看您是否已经为这个 n 计算过它。

2) 使用迭代方法:计算 F(1)、F(2)、F(3) 等...直到达到所需的数字。