Tiling
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 6444 Accepted: 3149
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 www.2cto.com
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
2
8
12
100
200
Sample Output
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
Source
The UofA Local 2000.10.14
考察點 ：遞推公式 f(n)=f(n-1)+2*(n-2);
大數相加
注意： 當輸入0的時候輸出1而不是0
[cpp]
#include <iostream>
#include <iomanip>
#include <string.h>
#include <math.h>
using namespace std;
struct num
{
int s[1000];
int top;
}a[260];
int main()
{
void deal(int x,int y,int z);
int i,j,n,m,s,t;
(a[1].s)[0]=1; (a[2].s)[0]=3;
a[1].top=1; a[2].top=1;
for(i=3;i<=250;i++)
{
deal(i-1,i-2,i);
}
while(cin>>n)
{
if(n==0)
{
cout<<1<<endl;
}else
{
for(i=a[n].top-1;i>=0;i--)
{
cout<<(a[n].s)[i];
}
cout<<endl;
}
}
return 0;
}
void deal(int x,int y,int z)
{
int i,j,l1,l2,max;
int b[1000],c[1000],d[1000];
l1=a[x].top; l2=a[y].top;
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(i=0;i<=l1-1;i++)
{
b[i]=(a[x].s)[i];
}
for(i=0;i<=l2-1;i++)
{
c[i]=2*((a[y].s)[i]);
}
if(l1>l2)
{
max=l1;
}else
{
max=l2;
}
for(i=0;i<=max-1;i++)
{
d[i]=b[i]+c[i];
}
for(i=0;i<=max-1;i++)
{
if(d[i]>=10)
{
d[i+1]+=d[i]/10;
d[i]=d[i]%10;
if(i==max-1)
{
max+=1;
}
}
}
a[z].top=max;
for(i=0;i<=max-1;i++)
{
(a[z].s)[i]=d[i];
}
}
