斐波那契数列 递推 递归 备忘录 动态规划

当n=0时，f(n) = 0     

当n=1时，f(n) = 1

当n>1时，f(n) = f(n-1) + f(n-2)

递归算法：

[cpp] view plaincopy

int fun(int n)  

{  

    if(n <= 0)  

        return 0;  

    if(n == 1)  

        return 1;  

  

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

}  

备忘录方法：

[cpp] view plaincopy

#include <iostream>  

using namespace std;  

  

const int N = 100;  

int f[N];  

  

int fun(int n)  

{  

    if(f[n]>=0)  

        return f[n];  

  

    if(n == 0)  

    {  

        f[0] = 0;  

        cout<<"0"<<endl;  

        return f[0];  

    }  

  

    if(n == 1)  

    {  

        f[1] = 1;  

        cout<<"1"<<endl;  

        return f[1];  

    }  

  

    cout<<n<<endl;  

    f[n] = fun(n-1) + fun(n-2);  

    return f[n];  

}  

  

int main()  

{  

    for (int i=0; i<N; i++)  

        f[i] = -1;  

  

    cout<<fun(4);  

    return 0;  

}  

由于计算的时候只需要前两个数即可，所以代码还可以继续优化。但是对于上述的备忘录方法貌似不能继续进行空间优化了(不知道对否，如果理解的不对请不吝赐教~)。

但是对于下面的方法（就称为遍历方法吧）,还是可以继续优化的。  自底向上的动态规划

[cpp] view plaincopy

#include <iostream>  

using namespace std;  

  

const int N = 100;  

int f[N];  

  

int main()  

{  

      

    int n;  

    cin>>n;  

  

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

    {  

        if(i==0)  

            f[i] = 0;  

        else if(i==1)  

            f[i] = 1;  

        else  

            f[i] = f[i-1] + f[i-2];  

    }  

  

    cout<<f[n];  

  

    return 0;  

}  

斐波那契数（动态规划）通过把所计算的值存储在递归过程的外部数组中，明确地避免重复计算。这一程序计算的时间与N成正比。int F(int i){if(knownF[i] != unknown)return knownF[i];if(i == 0) t = 0;if(i == 1) t = 1;if(i > 1) t = F(i - 1) + F(i - 2);return knownF[i] = t;}
自顶向下的动态规划

由于计算的时候只用了前两个数，所以没有必要使用数组。

[cpp] view plaincopy

#include <iostream>  

using namespace std;  

  

int main()  

{  

    int n;  

    cin>>n;  

  

    int temp1, temp2, temp;  

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

    {  

        if(i==0)  

            temp1 = 0;  

        else if(i==1)  

            temp2 = 1;  

        else  

        {  

            temp = temp1 + temp2;  

            temp1 = temp2;  

            temp2 = temp;  

              

        }  

    }  

  

    cout<<temp;  

  

    return 0;  

}  

总结：从代码中可以看出来，遍历方法实际上是一种自底向上的方法，而备忘录方法是一种自顶向下的方法，也许正由于这个原因造成了备忘录方法无法进行空间优化。(待证)

总结

以上是生活随笔为你收集整理的斐波那契数列 递推 递归 备忘录 动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。