題目來源:http://poj.org/problem?id=2506
Tiling
Time Limit: 1000MS | Memory Limit: 65536K |
Total Submissions: 11145 | Accepted: 5169 |
Description
In how many ways can you tile a 2xn rectangle by2x1 or 2x2 tiles?
Here is a sample tiling of a 2x17 rectangle.
Input
Input is a sequence of lines, each linecontaining an integer number 0 <= n <= 250.
Output
For each line of input, output one integernumber in a separate line giving the number of possible tilings of a 2xnrectangle.
Sample Input
2
8
12
100
200
Sample Output
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
Source
The UofA Local 2000.10.14
-----------------------------------------------------
解題思路
遞推+Java高精度
坑點:為什麼N=0的時候結果是1???
-----------------------------------------------------
代碼
import java.math.BigDecimal;
import java.util.Scanner;
public class Main {
public static void main(String args[])
{
Scanner s = new Scanner(System.in);
int n = 0, i = 0;
while (s.hasNext())
{
n = s.nextInt();
if (n==0)
{
System.out.println(1);
continue;
}
else if (n==1)
{
System.out.println(1);
continue;
}
else if (n==2)
{
System.out.println(3);
continue;
}
BigDecimal pans = new BigDecimal(1);
BigDecimal ans = new BigDecimal(3);
BigDecimal tmp = new BigDecimal(1);
BigDecimal multiplier = new BigDecimal(2);
for (i=0; i<n-2; i++)
{
tmp = pans;
pans = ans;
ans = tmp.multiply(multiplier).add(ans);
}
System.out.println(ans);
}
}
}