剑指offer之斐波那契数列

1 问题

写一个函数，输入n,求斐波那契数列的第n项。斐波那契数列定义如下。

  

   

    

     

    
    

     

      f(n) = 0; (n = 0)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      f(n) = 1; (n = 1)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      f(n) = f(n - 1) + f(n - 2); (n >= 2);
     
    
  
 

2 分析

1) 直接用递归

2) 我们用两个变量保持每次需要计算下一个值得前面2个数，从最前面开始迭代。

3 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      long long fibonacciOne(unsigned int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (n <= 0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     
 if (n == 1)
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

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

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      long long fibonacciTwo(unsigned int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (n <= 0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     
 if (n == 1)
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     
 long long first = 0;
     
    
   

    

     

    
    

     
 long long second = 1;
     
    
   

    

     

    
    

     
 long long sum = 0;
     
    
   

    

     

    
    

     
 for (int  i = 2; i <= n ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sum = first + second;
     
    
   

    

     

    
    

     

       first = second;
     
    
   

    

     

    
    

     

       second = sum;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return sum;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void) 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 long long resultOne = fibonacciOne(8);
     
    
   

    

     

    
    

     
 long long resultTwo = fibonacciTwo(8);
     
    
   

    

     

    
    

     
 printf("resultOne is %lld\n", resultOne);
     
    
   

    

     

    
    

     
 printf("resultTwo is %lld\n", resultTwo);
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      resultOne is 21
     
    
   

    

     

    
    

     

      resultTwo is 21
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
  
 

5 总结

方法二时间复杂度降低了很多，直接变成了O(n),比递归优化了很多，当我么求后面的结果需要前面的2个值的时候，后面的解需要依靠前面的解时候，我们可以用2个变量保持之前的值，然后每次算出一个新的值的时候进行迭代更新这2个值，因为这里刚需只需要2个值，所以用2个变量就行，如果是刚需很多值的话，我们可以用数组进行保持前面的值，后面的值就可以一一解答出来。

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/101481257