poj 2506 Tiling——递推和大数模拟

发布时间：2020-12-14 03:32:56 所属栏目：大数据来源：网络整理

导读：Tiling Time Limit: ?1000MS Memory Limit: ?65536K Total Submissions: ?7362 Accepted: ?3589 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 sequen

Tiling

Time Limit:?1000MS		Memory Limit:?65536K
Total Submissions:?7362		Accepted:?3589

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

Source

The UofA Local 2000.10.14

这个题是递推，还是比较好分析的，不过看下面的数据，似乎要用到大数模拟...

递推公式:s[0]=1;s[1]=1;while(i>=2) s[i]=s[i-1]+2*s[i-2];

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mx 2010

int ls[mx];
int s[260][mx];//用于存储250种情况的数

int main()
{
    int n,i,j;
    memset(ls,sizeof(ls));
    memset(s,sizeof(s));
    s[0][0]=1;
    s[1][0]=1;
    for(i=2;i<=250;i++)
    {
        for(j=0;j<=mx-10;j++)
        {
            ls[j]=s[i-1][j]+s[i-2][j]+s[i-2][j];//这里2倍就这么处理：多加一个s[i-2]；
        }
        for(j=0;j<mx;j++)
        {
            ls[j+1]+=(ls[j]/10);
            ls[j]%=10;
        }
        for(j=0;j<=mx;j++)
        {
            s[i][j]=ls[j];
        }
        memset(ls,sizeof(ls));
    }
    while(~scanf("%d",&n))
    {
        j=mx-1;
        while(s[n][j]==0)
            j--;
        for(;j>=0;j--)
        {
            printf("%d",s[n][j]);
        }
        printf("n");
    }

    return 0;
}

如果你看不懂，就去看看大数吧...链接http://blog.csdn.net/codeblf2/article/details/28908565

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!