bnuoj_24430 Tiling

n 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 2x
n?rectangle.

Sample Input

2
8
12

Sample Output

3
171
2731

//递推加大数（正数）相加
#include<stdio.h>
#include<string.h>
int a1[100],b1[100];char c[120];
int f(int x,int y){return x>y?x:y;}
void add(char *a,char *b){
	int lena,lenb,i,j,k,flag;
		lena=strlen(a);lenb=strlen(b);
		memset(a1,sizeof(a));memset(b1,sizeof(b));memset(c,sizeof(c));
		for(i=0;i<lena;i++) a1[i]=a[i]-'0';
		for(j=0;j<lenb;j++) b1[j]=b[j]-'0'; 
		if(lenb>=lena){  //判断长度
		                 for(i=lena-1,j=lenb-1;i>=0&&j>=0;i--,j--) {b1[j]+=a1[i];} //从低位到高位计算
		  for(i=lenb-1;i>=1;i--)  //从低位到高位进位
		  {
		  	if(b1[i]>=10) {
			   b1[i-1]+=b1[i]/10;
			   b1[i]%=10;
			  }
		  } 
		  flag=0;    //判断是否有前置 1
		 if(b1[0]>=10) {flag=1;b1[0]%=10;}
		 
		 if(flag) {j=1;c[0]='1';}
		 else {j=0;}
	   	 
		for(i=j,k=0;k<lenb;k++,i++)  //赋值到全局变量
			c[i]=b1[k]+'0';
			c[i]='\0';
		               }
	    else{
	    		for(i=lena-1,j--) {a1[i]+=b1[j];} 
		for(i=lena-1;i>=1;i--)
		  {
		  	if(a1[i]>=10) {
			   a1[i-1]+=a1[i]/10;
			   a1[i]%=10;
			  }
		  } 
		 flag=0;
		 if(a1[0]>=10) {flag=1;a1[0]%=10;}
		 
		 if(flag) {j=1;c[0]='1';}
		 else {j=0;}
	   	 
		for(i=j,k=0;k<lena;k++,i++)
			c[i]=a1[k]+'0';
			c[i]='\0';
		}				                      
	}
int main(){
	 char c1[251][120];
	 int n,i;	  
	strcpy(c1[0],"1"); 
    strcpy(c1[1],"1");
    strcpy(c1[2],"3");
 for(i=3;i<=250;i++)
 {
 	  add(c1[i-2],c1[i-1]);strcpy(c1[i],c);
	  add(c1[i],c1[i-2]);strcpy(c1[i],c);
 }
	while(~scanf("%d",&n)){printf("%s\n",c1[n]);}
return 0;
}