母牛的故事(PAT)

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;
}