1.题目描述

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

2.输入描述:

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

3.输出描述:

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

4.输入例子:

2
4
5

5.输出例子:

2
4
6

6.解题思路:

类似于斐波那契数列,我们只需要找出规律即可,
如果单纯算出前几项,我们很难发现规律,但我们根据题意可知,每头小母牛在第四个年头开始也生小母牛,所以规律在于4个年头的循环
前四年我们可知所以小母牛都是由一头母牛所生,而在四年后,小母牛也开始陆续开始生小母牛,也就是第n年的母牛数量=《初始母牛所生的数量》+《新生母牛所生小母牛》=《初始母牛n-1年所生的数量》+《初始母牛n-3年所生的数量》
<mark>该公式的推导思想与斐波那契数列一模一样,我们可以先用递归的思想画出二叉树,然后再用非递归的方法推导,这样会好理解些。</mark>

7.源代码:

#include<stdio.h>
int main()
{ 
	int i,n,num[60];
	num[1]=1;
	num[2]=2;
	num[3]=3;
	num[4]=4;
	for(i=5;i<=56;i++)
		num[i]=num[i-1]+num[i-3];
	while(scanf("%d",&n)!=-1)
	{
		printf("%d\n",num[n]);
	}
	return 0;
}