Tiling

递推公式：:f[x]=f[x-1]+f[x-2]*2
需要用到大数。
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define max 100
 4 int f[500][max];
 5 int h[max];
 6 int main()
 7 {
 8     int n,j;
 9     while(scanf("%d",&n)!=EOF)
10     {
11         if(n==0) {printf("1
");continue;}
12         memset(f,0,sizeof(f));
13         f[1][0]=1;
14         f[2][0]=3;
15         for(int i=3; i<=n; i++)
16         {
17             int c=0;
18             for(j=0; j<max; j++)
19             {
20                 int s=f[i-2][j]*2+c;
21                 h[j]=s%10;
22                 c=s/10;
23             }
24             int t=0;
25             for(int k=0; k<max; k++)
26             {
27                 int m=h[k]+f[i-1][k]+t;
28                 f[i][k]=m%10;
29                 t=m/10;
30             }
31         }
32         for(j=max-1; j>0; j--)
33         {
34             if(f[n][j])break;
35         }
36         for(int x=j; x>=0; x--)
37         {
38             printf("%d",f[n][x]);
39         }
40         printf("
");
41     }
42     return 0;
43 }
View Code