牛客网乙级1007：母牛的故事

母牛的故事

时间限制 1000ms 内存限制 32768KB 代码长度限制 100KB 判断程序 Standard

题目描述

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

输入描述:

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

输出描述:

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

每个输出占一行。

输入例子:

2
4
5

输出例子:

2
4
6

思路

根据提供的输入输出例子，发现，属于母体的那只母牛第一年生的小母牛并没有算在当年的母牛数量中，因此，第一年是1头母牛，第二年是2头，第三年是3头，第四年是4头。到了第五年，最早生的那只小母牛也生了一只小母牛，因此，第五年是5+1=6头。不难发现规律：当年的母牛数量是去年的+去年的去年的去年的数量。即：a[i] = a[i - 1] + a[i - 3]。
仔细审题，我们发现题目给出了n的范围，因此我们可以事先算出每一年母牛的数量，然后直接调用，减少时间内复杂度。
另外，题目是输入多个数据。因此可以用while (scanf("%d", &n) != EOF)来防止每输入一次就结束程序。

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