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

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

 #include <stdio.h>

 #include<string.h>

 int main()

 {

     int s[][],i,j,k,a,t;

     memset(s,,sizeof(s));

     s[][]=;

     s[][]=;

     s[][]=;

     t=;

     for(i=; i<; i++)

     {

         for(j=; j<=t; j++)

             s[i][j]=s[i-][j]+*s[i-][j];//这是地推公式

         for(k=; k<=t; k++)

             if(s[i][k]>)

             {

                 s[i][k+]+=(s[i][k]/);//大数进位

                 s[i][k]=s[i][k]%;

             }

         while(s[i][t]>)//大数进位

         {

             s[i][t+]=s[i][t]/;

             s[i][t]=s[i][t]%;

             t++;

         }

         for(t+=; s[i][t]==;t--);

     }

     while(~scanf("%d",&a))

     {

         for(i=; s[a][i]==; i--);

         for(i=i; i>; i--)

             printf("%d",s[a][i]);

         printf("\n");

     }

     return ;

 }

巴特西

Tiling（递推+大数）

最新文章

热门文章