骨牌铺方格(PAT)

1.题目描述

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

2.输入描述:

输入数据由多行组成，每行包含一个整数n，表示该测试实例的长方形方格的规格是2×n (1≤n≤90)。

3.输出描述:

对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

4.输入例子:

1
3
2

5.输出例子:

1
3
2

6.解题思路：

推导在2×n的一个长方形方格中，有多少种方法用一个1× 2的骨牌铺满方格
n=1（1种）、n=2（2种）、n=3（3种）、n=4（5种）。。。。。
斐波那契数列

7.源代码：

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