上海元山建设有限公司网站,免费模板网站下载,小米wordpress,尚品网站建设答案1#xff08;递推#xff09;#xff1a; #includestdio.h
int main()
{int n0,i0;int a[55] { 0,1,2,3,4 }; //数组下标就相当于过了几年#xff0c;以第四年母牛生出的第一只小母牛成年为周期#xff0c;初始化前四年的值while (scanf(%d, …答案1递推 #includestdio.h
int main()
{int n0,i0;int a[55] { 0,1,2,3,4 }; //数组下标就相当于过了几年以第四年母牛生出的第一只小母牛成年为周期初始化前四年的值while (scanf(%d, n) 1 (n 0 n 55)) //使输入符合if (n 0) //如果输入0break; //跳出循环else //如果输入不是0{if (n 4) //如果在四年内就没必要递推printf(%d\n, a[n]); //直接打印母牛个数else //如果超过四年就要用递推了{for (i 5; i n; i) //从最小递推年数第5年开始循环至n年要用不然第5年就直接没算了{a[i] a[i - 1] a[i - 3]; //母牛递推规律推导解释在文末if (i n) //如果到了输入的n年{a[n] a[i]; //将此时的个数赋值给输出printf(%d\n, a[n]); //打印第n年母牛的个数}}}} return 0;
}
答案2递归
# includestdio.h
int fun(int n) //定义母牛个数的函数
{if (n 1) //第一年的个数return 1;else if (n 2) //第二年的个数return 2;else if (n 3) //第三年的个数return 3;else if (n 4) //第四年的个数return 4;else //超出四年{return fun(n - 1) fun(n - 3); //用递归母牛的规律公式推导解释在文末}
}
int main()
{int n0;while (scanf(%d, n) 1 (n 0 n 55)) //使输入符合题目要求if (n 0) //如果n0{break; //跳出循环}else //如果n不为0printf(%d\n, fun(n)); //调用上面函数然后打印return 0;
}
关于本题的知识点以及需要理解的点
1.第一年母牛是不生的也就是说从第二年母牛才开始生这是要理解题目的点大概是题目里每年年初是暗示吧
2.
母牛个数规律推导
首先今年母牛的个数等于去年母牛的个数今年新生的小母牛个数然后去年母牛的个数等于去年的去年母牛的个数去年新生的小母牛个数……直到第四年只有初始母牛在生小母牛
所以
f[i]今年母牛的个数 f[i-1]去年母牛的个数 f[i-3]3年前母牛的个数今年成年的母牛的个数因为3年前加上本年等于4年今年能够生小母牛的母牛个数即满4年的成年母牛的个数今年新生的小母牛个数 f[i]今年母牛的个数f[i-1]去年母牛的个数f[i-3]今年新生的小母牛个数 故f[i] f[i - 1] f[i - 3]
3.递推和递归的区别
递推本题求第n年的牛总数已知第一年为“1”头进而推出第二年“2”头第三年“3”头“4”头“6”头“9”头……
递归要想求第“n”年的牛的总数只要知道“n-1”和“n-3”年的牛的总数再依次向前推所以递推和递归是一个正向思维一个逆向思维
4.在TZOJ上本题只能用递推递归会超时
