骨牌铺方格

Problem Description

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

 

 

Input

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

 

 

Output

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

 

 

Sample Input

1

3

2

 

Sample Output

1

3

2

---

问题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2046

问题分析：

• 观察图形的规律，f ( 1 ) = 1 , f ( 2 ) = 2 , f ( 3 ) = 3 。
• 最后一个木块只有两种排行方式。1. 竖排：那么前n-1格有f(n-1)种方案 ； 2. 横排：前n-2格有f(n-2)种方案。
• 由此可推出公式，f（ n ）= f（ n-1 ）+ f ( n-2 )

源代码

mport java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long [] a= new long [51];    
		a[1]=1;
		a[2]=2;
		a[3]=3;
		for(int i=4;i<51;i++)
			a[i]=a[i-1]+a[i-2];
		while(sc.hasNext()) {
			int n=sc.nextInt();
			System.out.println(a[n]);
		}
	}
}