斐波那契数列类似题目递归以及记忆化优化

清疚 2022-10-21 01:22 47阅读 0赞

当然，斐波那契数列可以使用递推，这谁都会。

a[1]=1;
    a[2]=1;
    for (int i = 3; i <= m; i++)
    	a[i] = a[i - 1] + a[i - 2];

框架是这样的，这个算法不考虑数字的存储范围。时间复杂度是O(n)的。

但是，如果让你用递归……当然只是为了训练递归算法。用递归的时间复杂度并不快。

int fb(int n)
    { 
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 1;
    	return fb(n - 1) + fb(n - 2);
    }

框架是这样的，别看代码短，实际耗时长，如果我们加上计时，我们会发现 n = 46 n=46 n=46的时候算法时间复杂度竟然达到了惊人的 4812 m s 4812ms 4812ms！  
![在这里插入图片描述][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 1]

我们发现在这棵递归树上有很多重复搜索的点，而这只是n=5，可想而知n=46，于是我们可以用一个数组来记录每一次的结果，在重复调用的时候可以直接返回，这样几乎可以达到线性的速度。如下代码

#include <iostream>
    #include <windows.h>
    #include <cstring>
    using namespace std;
    DWORD starttime, endtime;
    int a[100];
    int fun(int n)
    { 
        if (n == 1)
            return 1;
        if (n == 2)
            return 1;
        if (a[n] > -1)
            return a[n];
        else 
            return a[n] = fun(n - 2) + fun(n - 1);
    }
    int main()
    { 
        int n;
        memset(a, -1, sizeof(a));
        a[0] = 1;
        a[1] = 1;
        cin >> n;
        starttime = GetTickCount();
        cout << fun(n) << endl;
        cout << GetTickCount() - starttime << " ms" << endl;
        return 0;
    }

测速：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]  
这是我对于NOIP-J2014阅读程序第二题的思考以及改进，那一道题并不是斐波那契数列，但我觉得斐波那契数列更通常，而改进的算法是记忆化搜索的雏形。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/335dd53fd2e34878897d21404ae3f3b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/623b536a6f1a44c9948e21421f4656bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/c1fb53d46ed74e999b9f6a3e397af5ed.png