斐波那契数列实现方法递归解决、递归优化算法

以你之姓@ 2022-12-27 01:13 139阅读 0赞

首先基础的递归算法

#include <stdio.h>
    #include <string.h>
    #include <windows.h>
    #include <iostream>
    DWORD time_start, time_end;
    int book[1001];
    int fac(int i)
    { 
        if ((i == 1) || (i == 2))
            return 1;
        if (i > 2) { 
            return fac(i-1) + fac(i-2);
        }
        return 0;
    }
    
    int main()
    { 
        int i = 0;
        int n;
        std::cin >> n;
        memset(book, 0, sizeof(book));
        time_start = GetTickCount();
        for (i = 1; i < n; i++)
        { 
            printf("%d ",fac(i));
        }
        printf("\n");
        time_end = GetTickCount();
        std::cout << "TIME = " << (time_end - time_start) << "ms" << std::endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
这是运行的记录，时间已经达到了7秒左右  
![在这里插入图片描述][20201206164852625.png_pic_center]  
最后两个数已经很慢了

这个递归是**爆炸增量函数**，属于**指数级**函数，膨胀迅速。

我们看看n=46的时候  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
只是n+1，就加了5秒，因为最后一个数要执行前面的数的所有步骤，所以这个方法只是在n=3~50的范围。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]  
上图是我用matplotlib做的函数曲线图，蓝色线就是爆炸增量函数，增长最快了。

因为每新增一个数，就会成倍的执行前面的所有步骤。所以我们要剪掉重复步骤，记录每一次结果。如下：

#include <stdio.h>
    #include <string.h>
    #include <windows.h>
    #include <iostream>
    using namespace std;
    DWORD time_start, time_end;
    int fb[1000];
    int fac(int i)
    { 
        if (fb[i]>0)
            return fb[i];
        if ((i == 1) || (i == 2)) { 
            fb[i]=1;
            return 1;
        }
        if (i > 2) { 
            int a= fac(i-1) + fac(i-2);
            fb[i]= a;
            return a;
        }
    }
    
    int main()
    { 
        int i = 0;
        int n;
        std::cin >> n;
        time_start = GetTickCount();
        for (i = 1; i < n; i++)
        { 
            printf("%d ",fac(i));
        }
        printf("\n");
        time_end = GetTickCount();
        std::cout << "TIME = " << (time_end - time_start) << "ms" << std::endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]  
比循环的速度还要快，循环是线性的复杂度，不需要回调。  
![在这里插入图片描述][20201206170210682.png_pic_center]  
上图是循环实现

#include <iostream>
    #include <windows.h>
    using namespace std;
    DWORD time_start, time_end;
    int main()
    { 
        int a[1001], n;
    	time_start = GetTickCount();
        cin >> n;
        a[0] = 1;
        a[1] = 1;
        for (int i = 2; i < n; i++)
        { 
            a[i] = a[i - 1] + a[i - 2];
            cout << a[i] << " ";
        } cout << endl;
        time_end = GetTickCount();
    	cout << "Time = " << (time_end - time_start) << "ms\n ";
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/82e26090b9ba4b48951de97626c499d7.png
[20201206164852625.png_pic_center]: /images/20221120/c98816ec24b2428e8729b43124968b0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201206165054494.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201206165319738.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201206165746760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70#pic_center
[20201206170210682.png_pic_center]: https://img-blog.csdnimg.cn/20201206170210682.png#pic_center