記憶化搜索，即在搜索過程中記錄下搜索結(jié)果，在下次的搜索過程中如果算出過這個結(jié)果，就可以直接拿來用。

舉個栗子：

現(xiàn)有一個問題，要求寫出一個函數(shù)，功能是輸出第n個斐波那契數(shù)列。

斐波那契數(shù)列是這樣的：1,1,2,3,5,8......

直接的辦法是開一個數(shù)組，計算斐波那契數(shù)列到第n個，然后輸出array[n]就可以了

int?f(int?n){

int?fibo[MAXN]?=?{0,1};

for(int?i?=?2;?i?<=?n;?i++)

fibo[i]?=?fibo[i-2]?+?fibo[i-1];

return?fibo[n];

}

現(xiàn)在要求：必須使用遞歸！

問題還是很簡單。斐波那契數(shù)列的遞歸定義為：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2，n∈N*)，根據(jù)這一定義即可寫出程序：

int?f(int?n){

if(n?==?0?||?n?==?1)?return?1;????//遞歸終點

else?return?f(n-1)?+?f(n-2);

}

但是這里有個問題。比如n=5，遞歸式中需要計算f(4)和f(3)，而計算f(4)的時候又需要計算f(3)和f(2)，這就產(chǎn)生了計算重復(fù)，使得時間復(fù)雜度達(dá)到指數(shù)級別O(2n)

為了避免重復(fù)計算，我們需要新開一個數(shù)組來保存計算后的結(jié)果

int?dp[MAXN]?=?{0};

int?f(int?n){

if(n?==?0?||?n?==?1)?return?1;????//遞歸邊界

if(dp[n]?==?0)

dp[n]?=?f(n-1)?+?f(n-2);????//如果沒有計算過，計算它

//如果計算過，就不用算了

//最后都返回dp[n]

return?dp[n];

}

這樣可以大大的降低時間復(fù)雜度，降至O(n)

來寫個程序看看運行耗時吧！

#include?

#include?

#define?MAXN?100

int?dp[MAXN]?=?{0};

int?f1(int?n){

if(n?==?0?||?n?==?1)?return?1;????//遞歸邊界

if(dp[n]?==?0)

dp[n]?=?f1(n-1)?+?f1(n-2);????//如果沒有計算過，計算它

//如果計算過，就不用算了

//最后都返回dp[n]

return?dp[n];

}

int?f2(int?n){

if(n?==?0?||?n?==?1)?return?1;????//遞歸終點

else?return?f2(n-1)?+?f2(n-2);

}

int?main(){

int?n;

clock_t?start,?stop;

scanf("%d",?&n);

start?=?clock();

printf("%d\n",?f2(n));

stop?=?clock();

printf("f2耗時：%.0fms\n",?double((stop-start)?*?1000?/?CLOCKS_PER_SEC));

start?=?clock();

printf("%d\n",?f1(n));

stop?=?clock();

printf("f1耗時：%.0fms\n",?double((stop-start)?*?1000?/?CLOCKS_PER_SEC));

return?0;

}

運行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的记忆化搜索斐波那契c语言,记忆化搜索--优化斐波那契数列递归函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。