兔子的繁殖问题（斐波那契数列）

数列）"/>

兔子的繁殖问题（斐波那契数列）

Problem A: 兔子的繁殖问题
假设一对兔子每月能生一对小兔（一雌一雄），每对小兔出生后的下一个月是没有繁殖能力的，至出生后的第三个月开始又可以每月生一对小兔，问从一对刚出生的小兔开始，经过若干个月后一共有多少兔子（假设在此过程中兔子没有死亡）？

这个问题是意大利数学家菲波那契（Fibonacci）在他1202年出版的《算盘全书》中提出来的，从第一对刚出生的小兔开始每月的兔子数被称作菲波那契序列。

Input

输入的第一个数为n，接下来有n个数字。每个数字为一个月份m（m<=45）。

Output

输出为n行，每行为第m个月后的兔子总数。

Sample Input

6
1 2 3 4 5 10

Sample Output

1
2
3
5
8
89

HINT

超时了吧！

使用递归计算菲波那契序列，这合适吗？

用数组写比较方便，用循环直接算也不超时。

#include <stdio.h>
#include <stdlib.h>
#define N 45
int main()
{int a[50],i,m,n,k;scanf("%d",&n);for(i=0;i<n;i++){a[0]=1;a[1]=2;scanf("%d",&m);if(m<=2)printf("%d\n",a[m-1]);else{for(k=2;k<m;k++)a[k]=a[k-1]+a[k-2];printf("%d\n",a[k-1]);}}}