POJ 2506 Tiling(大数递推&&(数组模拟||JAVA))

发布时间：2020-12-14 02:49:52 所属栏目：大数据来源：网络整理

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

Tiling

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?7910	?	Accepted:?3844

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

递推公式f[i] = f[i-1] + 2*f[i-2];
不明白的是0的时候为什么输出1，让我WA了好几遍
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 300;
char a[N][N];
void sum(int x,char s1[],char s2[])
{
    int len1=strlen(s1);
    int len2=strlen(s2);
    int e1[N],e2[N];
    memset(e1,sizeof(e1));
    memset(e2,sizeof(e2));
    for(int i=0; i<len1; i++)
        e1[i]=s1[len1-i-1] - '0';
    for(int i=0; i<len2; i++)
        e2[i]=s2[len2-i-1] - '0';
    int k=len1;
    if(k<len2)
        k=len2;
    for(int i=0; i<k; i++)
    {
        e1[i]+=e2[i] + e2[i];
        if(e1[i]>=10)
        {
            e1[i+1]+=e1[i]/10;
            e1[i]=e1[i]%10;

        }
    }
    int ee=0;
    for(int i=N-1; i>=0; i--)
    {
        if(e1[i]!=0)
        {
            for(int j=i; j>=0; j--)
                a[x][ee++]=e1[j]+'0';
            break;
        }
    }
    a[x][ee]='';
}
int main()
{
    strcpy(a[0],"1");
    strcpy(a[1],"1");
    strcpy(a[2],"3");
    for(int i=3; i<=250; i++)
    {
        sum(i,a[i-1],a[i-2]);
    }
    int n;
    while(cin>>n)
    {
        cout<<a[n]<<endl;
    }
    return 0;
}

JAVA 就比较简单了。。。
import java.util.*;
import java.math.*;
public class Main {

	public static void main(String[] args) {
		BigInteger []a=new BigInteger [311];
		a[0]=BigInteger.valueOf(1);
		a[1]=BigInteger.valueOf(1);
		a[2]=BigInteger.valueOf(3);
		for(int i=3;i<301;i++){
			a[i]=a[i-1].add(a[i-2].add(a[i-2]));
			}
		Scanner cin=new Scanner(System.in);
		while(cin.hasNextInt()){
			int n=cin.nextInt();
			System.out.println(a[n]);
			
		}
		cin.close();
	}
}

（编辑：李大同）

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

POJ 2506 Tiling(大数递推&amp;&amp;(数组模拟||JAVA))

POJ 2506 Tiling(大数递推&&(数组模拟||JAVA))