【10】斐波那契数列的循环和递归实现

浅浅的花香味﹌ 2022-05-27 09:24 192阅读 0赞

## 面试题10：斐波那契数列 ##

### 【0】目录： ###

**【1】题目**  
**【2】分析**  
**【3】测试代码**  
**【4】测试结果**  
**【5】算法优劣分析**

### **【1】题目：** ###

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。

斐波那契数列： 1，1，2，3，5，8，13，21，34，55，89 ……  
![这里写图片描述][70]

### **【2】分析：** ###

在斐波那契数列中，不难得出规律，当n > 2时，某个数等于前两位数之和，如： 2 = 1+ 1；3 = 1+ 2； 5 = 2 +3……  
那么我们可以分为三个部分来求解，如下所示：  
![这里写图片描述][70 1]

### **【3】测试代码：** ###

#include<iostream>
    using namespace std;
     //========================循环实现===============================
    long long Fibonacci01(unsigned int n )
    {
        int result[2]={
       0,1}; 
         if (n < 2)
            {
                return result[n];
             }
        long long fib1 = 0;
        long long fib2 = 1;
        long long fibn = 0;
        for(int i = 2; i<= n ;++i )
        {
            fibn = fib1+fib2;
            fib1 = fib2;
            fib2 =fibn;
        }
        return fibn;
    }
    
    //===========================递归实现================================
    long long Fibonacci02(unsigned int n)
    {
        if(n <= 0)
        {
            return 0;
        }
        if(n == 1)
        {
            return 1;
        }
        if(n >= 2)
            return Fibonacci02( n - 1)+Fibonacci02( n - 2) ;
    }
    
    //====================测试代码========================
    void test()
    {
        long long ret1 = 0,ret2 = 0 ;
        int  n = 0;
        printf("请输入待求斐波那契数的数:\n");
        scanf( "%d", &n );
        ret1 = Fibonacci01(  n );
        ret2 = Fibonacci02(  n ); 
    
    
        printf("循环实现第%d个斐波那契数ret1为： %lld\n",n, ret1);
        printf("递归实现第%d个斐波那契数ret2为： %lld\n",n, ret2);
    
    }
    
    int main()
    {
        test();
        return 0;
    }

### **【4】测试结果如下：** ###

![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
![这里写图片描述][70 4]  
![这里写图片描述][70 5]  
![这里写图片描述][70 6]  
![这里写图片描述][70 7]  
![这里写图片描述][70 8]  
![这里写图片描述][70 9]  
![这里写图片描述][70 10]  
![这里写图片描述][70 11]  
![这里写图片描述][70 12]

![这里写图片描述][70 13]

### **【5】算法优劣分析：** ###

上面我们采用了循环和递归分别求第n个斐波那契数，那么这两种方式各有优缺点：  
**递归算法：**  
递归的本质是将一个难以解决的大问题分解成若干个小的模块，每个小模块再来求解；递归的底层是用栈来实现的；递归用来解决这个问题，显然是合适的；**优点：**代码量少，逻辑清晰、算法一目了然；**缺点：**在求斐波那契数列的时候，会大量的重复调用现象，如下图所示，（ f ( 6 ) 计算了4次） 这些重复的操作会占用大量的时间，因此，当所求的斐波那契数过大时，效率不高，当输入40时，明显要等几秒，结果才会出来，当数字过大时，将无法计算；另外，在函数调用的时候，会开辟空间，而每个进程的栈容量都是有限的，这就容易造成栈溢出；显然，使用递归算法，那么，算法的时间复杂度O 是以n的指数的方式递增的；  
![这里写图片描述][70 14]  
**循环算法：**  
只要递归能实现的地方，基本都可以通过循环实现，循环看似比较繁琐，但实际上，是最实用的一种方案,我们可以将已经得到的中间项保存起来，下次计算的时候，先查找一下，如果之前计算过了，就不再重复计算了，显然这种方法的时间复杂度为O（n）

[70]: /images/20220527/47c8099627a347cdb5a17217b9e1dff8.png
[70 1]: /images/20220527/c3c65315f6f343c2a3215609069136f6.png
[70 2]: /images/20220527/d5acd65dfca3441ba7875fd5a7991b77.png
[70 3]: /images/20220527/ae32f3050a014a6db0ec2570bb41b00c.png
[70 4]: /images/20220527/0ac3e8d4993646b88049ff858990ed75.png
[70 5]: /images/20220527/f6edc2ee9ca44b4d836737c82929c1f2.png
[70 6]: /images/20220527/dcccfa79e3594d19a6c9ccc4ad095cad.png
[70 7]: /images/20220527/17fc3d2783da4e3a975875dbdaec643f.png
[70 8]: /images/20220527/fa0d7f07605e4d7d835e61fb5e5d0e53.png
[70 9]: /images/20220527/08ea3072b885474cbcea93883fe18137.png
[70 10]: /images/20220527/890dad49351348d587b9d7c7a400c73e.png
[70 11]: /images/20220527/a9b8dc4d5d6b44b8af7b33c7d3b02ea4.png
[70 12]: /images/20220527/915e5688bb1c435181fc6b2e4cf1019f.png
[70 13]: /images/20220527/63228cf126d24d1494c57b340ea87ff2.png
[70 14]: /images/20220527/8d57c8d5551744faa69fbc573e08cc8c.png