本文共 1932 字，大约阅读时间需要 6 分钟。

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 is a sequence of lines, each line containing an integer number 0 <= n <= 250. 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 2812 Output for the sample input 31712731 Original: Albert 2001

解题：

       瓷砖有2x1 和2x2的，就如图所示的那样的，可以随便组合而成。要问我们2xn矩形里面铺瓷砖，一共有多少种铺法，0<=n<=250。当n为0的时候，方法只有1种那就是不铺（切记），下面看下其他的。

则tiles[n]=tiles[n-1]+tiles[n-2]*2;

每次增加一个，我们在上一个的基础上再考虑额外的情况，要用到大数加法和乘法。

#include <iostream>#include <string>using namespace std;#define MaxSize 252void add(char a[],char b[],char back[]){ int i,j,k,up,x,y,z,l; char* c; if (strlen(a)>strlen(b)) l=strlen(a)+2; else l=strlen(b)+2; c=(char*)malloc(l*sizeof(char)); i=strlen(a)-1; j=strlen(b)-1; k=0,up=0; while(i>=0 || j>=0) { if(i<0) x='0'; else x=a[i]; if(j<0) y='0'; else y=b[j]; z=x-'0'+y-'0'; if(up) z+=1; if(z>9) {up=1;z%=10;} else up=0; c[k++]=z+'0'; i--,j--; } if(up) c[k++]='1'; i=0; c[k]='/0'; for (k-=1;k>=0;k--) back[i++]=c[k]; back[i]='/0';}void mult(char c[],char t[],int m){ int i,l,k,flag,add=0; char s[100]; l=strlen(c); for(i=0;i<l;i++) s[l-i-1]=c[i]-'0'; for(i=0;i<l;i++) { k=s[i]*m+add; if(k>=10) { s[i]=k%10;add=k/10;flag=1; } else { s[i]=k;flag=0;add=0; } } if (flag) { l=i+1;s[i]=add; } else l=i; for(i=0;i<l;i++) t[l-1-i]=s[i]+'0'; t[l]='/0';}void tiling(char a[][MaxSize*4]){ memset(a,'/0',sizeof(a)); int i,j,l=MaxSize; a[0][0]='1',a[0][1]='/0'; a[1][0]='1',a[1][1]='/0'; a[2][0]='3',a[2][1]='/0'; for(i=3;i<l;i++) { mult(a[i-2],a[MaxSize-1],2); add(a[i-1],a[MaxSize-1],a[i]); }}int main(){ int n; char tiles[MaxSize][MaxSize*4]; tiling(tiles); while (cin>>n) { cout<<tiles[n]<<endl; } return 0;}

转载地址：http://wcid.baihongyu.com/