剑指offer面试题[9]-裴波那契数列

╰半橙微兮° 2022-06-13 01:26 87阅读 0赞

## 题目描述 ##

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。

n<=39

分析:

虽然在学递归函数时，会用斐波那契数列作为例子，但这并不能说明递归的解法最合适这个题目，我自己也试过，在牛客网上用递归来做，运行结果会提示算法运行超过规定的时间，原因是算法复杂度过高。以求解f(9)为例，需要先求f(8)和f(7)，求解f(8)时，需要求解f(7)和f(6)，求解f(7)时，需要求解......可以用树形结构来表示这种依赖关系：

f(10)

/          \\

f(9)          f(8)

/     \\        /      \\

f(8)      f(7)  f(7)    f(6)

..................................................

我们不难发现其中很多结点都是重复的，而且重复的结点会随着n的增大而急剧增加，这意味着如果n的值很大，计算将会十分复杂。

递归的实现如下：(复杂度太高不合适)

class Solution \{   
        public:

int Fibonacci(int n) \{

if(n<=0)

return 0;

if(n=1)

return 1;

for(int i=2;i<=n;i++)                  //注意等于号

return Fibonacci(n-1)+Fibonacci(n-2);

\}  
\};

递归代码之所以很慢是因为重复的计算量太多，我们只是想办法避免重复计算就行了。比如我们可以把已经得到的数列中间保存起来，如果下次需要计算的时候我们先检查一下，如果前面已经计算过了就不用计算了。

其实更简单的办法就是从下往上计算，首先根绝f(0)和f(1)得到f(2),然后根据f(1)和f(2)得到f(3).....就是可以定义两个值表示当前计算值的前面两个值，front1和front2。初始值front1为f(0)=0,front2为f(1)=1,计算f(2)=front1+front2=1,此时需要更新front1与front2，为计算f(3)做准备。即f把ront2的值赋给front1，把f(2)的值赋给front2，即f(3)=front1+front2=f(1)+f(2)。依次内推。。。。。。

class Solution \{  
public:  
    int Fibonacci(int n) \{  
        int result\[2\]=\{0,1\};  
        if(n<2)  
            return result\[n\];  
        int frontData1=0;  
        int frontData2=1;  
        int Value=0;  
        for(int i=2;i<=n;i++)  
          \{  
              Value=frontData1+frontData2;  
              frontData1=frontData2;  
              frontData2=Value;  
          \}  
        return Value;  
    \}  
\};