博客

题目描述

兔子有着不可想象的繁殖能力，不信你计算一下。

假设有一对新生的兔子，从第三个月开始他们每个月月初都生一对兔子（一公一母），新生的兔子从第三个月月初开始又每个月生一对兔子。按此规律，并假定兔子没有死亡，n（n<=40）个月月末共有多少对兔子？

输入

多组测试数据，第一行是测试数据组数K（K<20），紧接着是N行数据，每行一个整数，表示月数n（n<=40）.

输出

多行，每行表示一组测试数据的结果，为该月末兔子的对数。

样例输入

5
1
4
9
5
8

样例输出

1
3
34
5
21

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