Tiling（递推+大数）

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

没什么好说的，递推题，大数自己看看吧，方法很多，我用的数组模拟；

 1 #include <stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int s[261][160],i,j,k,a,t;
 6     memset(s,0,sizeof(s));
 7     s[0][1]=1;
 8     s[1][1]=1;
 9     s[2][1]=3;
10     t=1;
11     for(i=3; i<251; i++)
12     {
13         for(j=1; j<=t; j++)
14             s[i][j]=s[i-1][j]+2*s[i-2][j];//这是地推公式
15         for(k=1; k<=t; k++)
16             if(s[i][k]>9)
17             {
18                 s[i][k+1]+=(s[i][k]/10);//大数进位
19                 s[i][k]=s[i][k]%10;
20             }
21         while(s[i][t]>9)//大数进位
22         {
23             s[i][t+1]=s[i][t]/10;
24             s[i][t]=s[i][t]%10;
25             t++;
26         }
27         for(t+=1; s[i][t]==0;t--);
28     }
29     while(~scanf("%d",&a))
30     {
31         for(i=150; s[a][i]==0; i--);
32         for(i=i; i>0; i--)
33             printf("%d",s[a][i]);
34         printf("
");
35     }
36     return 0;
37 }

View Code