poj 2506Tiling

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?
Here is a sample tiling of a 2x17 rectangle.

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

Sample Input

Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

假设我们已经铺好了2*（n-1)的，要铺成2*n的只能用2*1的地板
假设我们已经铺好了2*（n-2)的，要铺成2*n的可以用1个2*2的，也可以用两个2*1的
所以得到递推公式f（n）=f（n-1)+2*f（n-2);
根据题目的范围考虑用高精度模拟实现即可

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 char a[260][1000];
 4 void add(char b[],char c[],char d[])
 5 {
 6     int i,j,k=0,up=0;
 7     int x,y,z,t;
 8     i=strlen(b)-1,j=strlen(c)-1;
 9     while(i>=0||j>=0)
10     {
11         if(i<0) x=0;else x=b[i]-'0';
12         if(j<0) y=0;else y=c[j]-'0';
13         z=x+y+up;
14         if(z>9)
15         {
16             up=1;
17             z-=10;
18         }
19         else
20             up=0;
21         d[k++]=z+'0';
22         i--,j--;
23     }
24     if(up)
25         d[k++]='1';
26     d[k]='\0';
27     for(i=0;i<k/2;i++)
28     {
29         t=d[i];
30         d[i]=d[k-i-1];
31         d[k-i-1]=t;
32     }
33 }
34 void init()
35 {
36     int i;
37     char b[1000];
38     strcpy(a[0],"1");
39     strcpy(a[1],"1");
40     for(i=2;i<=250;i++)
41     {
42         add(a[i-2],a[i-2],b);
43         add(a[i-1],b,a[i]);
44     }
45 }
46 
47 int main()
48 {
49     init();
50     int n;
51     while(scanf("%d",&n)!=EOF)
52     {
53        printf("%s\n",a[n]);
54     }
55     return 0;
56 }