答案1(递推):
#include<stdio.h>
int main()
{
int n=0,i=0;
int a[55] = { 0,1,2,3,4 }; //数组下标就相当于过了几年,以第四年母牛生出的第一只小母牛成年为周期,初始化前四年的值
while (scanf("%d", &n) == 1 && (n >= 0 && n < 55)) //使输入符合
if (n == 0) //如果输入0
break; //跳出循环
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(递归):
# include<stdio.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 n=0;
while (scanf("%d", &n) == 1 && (n >= 0 && n < 55)) //使输入符合题目要求
if (n == 0) //如果n=0
{
break; //跳出循环
}
else //如果n不为0
printf("%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上本题只能用递推,递归会超时