生活随笔
收集整理的這篇文章主要介紹了
斐波那契数列 递推 递归 备忘录 动态规划
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
當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;?? }??
總結：從代碼中可以看出來，遍歷方法實際上是一種自底向上的方法，而備忘錄方法是一種自頂向下的方法，也許正由于這個原因造成了備忘錄方法無法進行空間優化。(待證)
總結
以上是生活随笔為你收集整理的斐波那契数列 递推 递归 备忘录 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
