首页 > 专题系列 > Java解POJ > POJ 2663 Tri Tiling [解题报告] Java
2013
11-11

POJ 2663 Tri Tiling [解题报告] Java

Tri Tiling

问题描述 :

In how many ways can you tile a 3xn rectangle with 2×1 dominoes?

Here is a sample tiling of a 3×12 rectangle.

输入:

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.

输出:

For each test case, output one integer number giving the number of possible tilings.

样例输入:

2
8
12
-1

样例输出:

3
153
2131

解题代码:

方法一:
import java.util.Scanner;
import java.util.Arrays;
public class Main{

  static long S(int n) //S(n)=3*S(n-2)+2*(S(n-4)+S(n-6)+...+S(2)+S(0))
{
    long s;
    int i;
    if(n==0)return 1;
     else
    {
        s=3*S(n-2);
        for(i=n-4;i>=0;i-=2)
        {
            s+=2*S(i);
        }
        return s;
    }
}

 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);  
    int n;
    n=sc.nextInt();
    while(n>=0) 
    { 
        if(n%2!=0) System.out.printf("0\n");
        else if(n==0) System.out.printf("1\n");
        else System.out.printf("%d\n",S(n));    
        n=sc.nextInt();
    } 
  }
}

方法二:
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

    public static void main(String[] args) throws IOException{
        int N=33;
       // BufferedInputStream bin = new BufferedInputStream(new FileInputStream("in.txt"));
       // System.setIn(bin);
        Scanner cin = new Scanner(System.in);
        int i,j,k;
        BigInteger[] res = new BigInteger[N];
        BigInteger temp = BigInteger.ONE;
        res[0] = BigInteger.ONE;
        res[1] = BigInteger.ZERO;
        res[2] = new BigInteger("3");
        res[3] = new BigInteger("0");
        for(i=4;i< N;i++)
        {
            j=i-2;
            temp = res[j].multiply(new BigInteger("3"));
            j-=2;
            while(j>=0)
            {
                temp = temp.add(res[j].multiply(new BigInteger("2")));
                j-=2;
            }
            res[i] = temp;
        }
        while(cin.hasNextInt())
        {
            i=cin.nextInt();
            if(i==-1){
                break;
            }
            System.out.println(res[i]);
        }
    }

}