【题解】母牛的故事
【题目描述】
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
【输入描述】
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。
【输出描述】
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行
【样例输入】
2 4 5 0
【样例输出】
2 4 6
【题目分析】
我们先列出一个表格，把每一年对应的母牛数量写出来。问题的关键分清每年牛的数量。确定数量后再推导规律。
表格参考下面：（大牛表示每年都可以生牛的牛，牛1表示大牛第二年的生的牛，牛2表示大牛第三年生的牛,牛3表示第4年生的牛）
| 年数 | 大牛 | 牛1 | 牛2 | 牛3 | 总数 |
| 第一年 | 1 | 0 | 0 | 0 | 1 |
解释：第一年，只有1头母牛（根据测试样例中，第二年有2头，说明题目中说的年初是第二年年初，而不是第一年年初）
当第二年时：
| 年数 | 大牛 | 牛1 | 牛2 | 牛3 | 总数 |
| 第二年 | 1 | 1 | 0 | 0 | 2 |
解释：大牛在第二年年初生了一头小牛。这时牛1还不到第四年，所以一共2头牛
当第三年时：
| 年数 | 大牛 | 牛1 | 牛2 | 牛3 | 总数 |
| 第三年 | 1 | 1 | 1 | 0 | 3 |
解释：牛1才第二年，不能生小牛。大牛继续生小牛。所以一共3头牛。
当第四年时：
| 年数 | 大牛 | 牛1 | 牛2 | 牛3 | 总数 |
| 第四年 | 1 | 1 | 1 | 1 | 4 |
解释：牛1是第三年，不能生小牛。牛2是第二年，不能生小牛。牛3是第一年，不能生小牛。所以一共4头牛。
当第五年时：
| 年数 | 大牛 | 牛1 | 牛2 | 牛3 | 总数 |
| 第五年 | 2 | 1 | 1 | 1 | 4 |
也可以通过下面的图进行分析：（实线表示生育关系，虚线表示成长关系）
可以用下面这个表格来表示：
| 第 n年： | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| f[n] 头牛: | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 |
规律就是该年母牛的数量就是一年前的数量再加上三年前的数量，
用公式表示就是 f[n] = f[n-1] + f[n-3]
参考代码：
#include<iostream>
using namespace std;
int f[55];
int main()
{
int n, i;
f[0]=0,f[1]=1,f[2]=2,f[3]=3;
for (i = 4; i < 55; i++)
f[i] = f[i - 1] + f[i - 3];
while (1)
{ cin>>n;
if(n==0){
return 0
}
cout << f[n] << endl;
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。