Problem
設有一頭小母牛，從出生第四年起每年生一頭小母牛，按此規律，第N年時有幾頭母牛？

Input
本題有多組數據。每組數據只有一個整數N，獨占一行。(1≤N≤50)

Output
對每組數據，輸出一個整數（獨占一行）表示第N年時母牛的數量

Sample Input
1
4
5
20

Sample Output
1
2
3
872

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
最容易寫出來的。

解決方法很簡單：母牛數等于自己加上它生的小牛數，再加上它的小牛們自己生的小牛，如此遞歸。


/*
此解答未被Accept
原因：運算時間超時（1200ms，而時間限制在1000ms）
*/
#include<stdio.h>

int F(int n)
{
?int res = n<4?0:n-3;//該母牛所生的小牛數

?if(n>=4)
?{
??for(int i=1; i<=n-3; i++)//該母牛的每一個孩子再生小牛。
??{
???res += F(i);
??}
?}

?return res;
}

int main()
{
?int n;

?while( scanf("%d",&n) != EOF)
?{
??printf("%d\n",F(n)+1);
?}

?return 0;
?
}

上面解答的弱點是，重復計算（比如F(1)被。每一個小牛掉用了，被每一個小牛的每一個孩子調用了，如此重復下去），導致時間開銷很大。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－
改進的：

為了避免重復運算，我們將用一個數組保存已經被計算過的值，由于函數F的任何計算的結果都不會是
－1，那么我們設置數組的初始值為－1，但檢查到其值不為－1時，那么它已經被計算過了，我們就沒有必要再計算了。

/*
此解答已通過TongJi編譯，并接收
?User??????? Result?? Memory Time? Language Date?
?zhouyinhui? Accepted 56 k?? 2ms?? C++????? 2006-05-06 16:32:02
*/
?
#include<stdio.h>
#include<malloc.h>

int* arr;//用于保存運算結果，避免遞歸調用中的重復運算

int F(int n)
{
?int res = n<4?0:n-3;

?if(n>=4)
?{
??
??for(int i=1; i<=n-3; i++)
??{
???if( *(arr+i) == -1 )//如果未運算該F(i)
???{
????*(arr+i) = F(i);//則運算并保存結果
???}
???res += *(arr+i);??

??}
??
?}

?return res;
}

int main()
{
?int n;

?while( scanf("%d",&n) != EOF)
?{
??int *array = (int *)malloc(n*4);
??for(int i=0; i<n; i++)
??{
???*(array+i) = -1;
??}

??arr = array;

??printf("%d\n",F(n)+1);
?}

?return 0;
?
}





?

轉載于:https://www.cnblogs.com/zhouyinhui/archive/2006/05/06/392719.html

總結

以上是生活随笔為你收集整理的小问题，对递归重复调用的改进，一起来分享的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。