二级学院网站建设方案,专业网站设计招聘信息,河北网站推广优化,六安网站制作哪家好Problem设有一头小母牛#xff0c;从出生第四年起每年生一头小母牛#xff0c;按此规律#xff0c;第N年时有几头母牛#xff1f; Input本题有多组数据。每组数据只有一个整数N#xff0c;独占一行。(1≤N≤50) Output对每组数据#xff0c;输出一个整数#xff08;独…Problem设有一头小母牛从出生第四年起每年生一头小母牛按此规律第N年时有几头母牛 Input本题有多组数据。每组数据只有一个整数N独占一行。(1≤N≤50) Output对每组数据输出一个整数独占一行表示第N年时母牛的数量 Sample Input14520 Sample Output123872最容易写出来的。解决方法很简单母牛数等于自己加上它生的小牛数再加上它的小牛们自己生的小牛如此递归。/*此解答未被Accept原因运算时间超时1200ms而时间限制在1000ms*/#includestdio.hint F(int n){ int res n4?0:n-3;//该母牛所生的小牛数 if(n4) { for(int i1; in-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*/ #includestdio.h#includemalloc.h int* arr;//用于保存运算结果避免递归调用中的重复运算 int F(int n){ int res n4?0:n-3; if(n4) { for(int i1; in-3; i) { if( *(arri) -1 )//如果未运算该F(i) { *(arri) F(i);//则运算并保存结果 } res *(arri); } } return res;} int main(){ int n; while( scanf(%d,n) ! EOF) { int *array (int *)malloc(n*4); for(int i0; in; i) { *(arrayi) -1; } arr array; printf(%d\n,F(n)1); } return 0; } 转载于:https://www.cnblogs.com/zhouyinhui/archive/2006/05/06/392719.html
