【题目描述】

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

【输入描述】

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。

n=0表示输入数据的结束，不做处理。

【输出描述】

对于每个测试实例，输出在第n年的时候母牛的数量。

每个输出占一行

【样例输入】

2  4  5  0

【样例输出】

2  4  6

【题目分析】

我们先列出一个表格，把每一年对应的母牛数量写出来。问题的关键分清每年牛的数量。确定数量后再推导规律。

表格参考下面：（大牛表示每年都可以生牛的牛，牛1表示大牛第二年的生的牛，牛2表示大牛第三年生的牛,牛3表示第4年生的牛）

解释：第一年，只有1头母牛（根据测试样例中，第二年有2头，说明题目中说的年初是第二年年初，而不是第一年年初）

当第二年时：

解释：大牛在第二年年初生了一头小牛。这时牛1还不到第四年，所以一共2头牛

当第三年时：

解释：牛1才第二年，不能生小牛。大牛继续生小牛。所以一共3头牛。

当第四年时：

解释：牛1是第三年，不能生小牛。牛2是第二年，不能生小牛。牛3是第一年，不能生小牛。所以一共4头牛。

当第五年时：

也可以通过下面的图进行分析：（实线表示生育关系，虚线表示成长关系）

可以用下面这个表格来表示：

规律就是该年母牛的数量就是一年前的数量再加上三年前的数量，

用公式表示就是 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;  }

(adsbygoogle = window.adsbygoogle || []).push({});