poj 2506 Tiling(递推+大数加法)
发布时间:2020-12-14 03:40:02 所属栏目:大数据 来源:网络整理
导读: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 in
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 2 8 12 100 200 Sample Output 3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251 公式为:f[x]=f[x-1]+2*f[x-2]; 至于为什么f[0]为1,我也不知道。。。我是根据公式以及给出的案例反推的f[0]. #include <stdio.h> #include <string.h> char s[260][200]; int main() { int n,i,a,j,x,b; memset(s,'0',sizeof(s)); s[0][0]='1'; s[1][0]='1'; s[2][0]='3'; for(i=3;i<=250;i++) { for(j=0;j<100;j++) { a=(2*(s[i-2][j]-'0')+s[i-1][j]-'0'+s[i][j]-'0'); s[i][j]=a%10+'0'; s[i][j+1]=a/10+'0'; } } while(scanf("%d",&n)!=EOF) { x=0; for(i=100;i>=0;i--) { if(s[n][i]!='0') { x=i; break; } } for(i=x;i>=0;i--) { printf("%c",s[n][i]); } printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |