2013
11-11

# 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)
{
j-=2;
}
res[i] = temp;
}
while(cin.hasNextInt())
{
i=cin.nextInt();
if(i==-1){
break;
}
System.out.println(res[i]);
}
}

}

1. 源自粗鄙的人的心理防卫机制，通过贬低某些人的优秀品质来寻求心里平衡。之所以某些人觉得不粗鄙就无法融入别人的圈子，那是因为粗鄙的人数实在太多了。