Tri Tiling
三瓷磚
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2676 Accepted Submission(s): 1511
Problem Description In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle. 用2 x1的多米諾骨牌鋪在3 x n 的矩形瓷磚中,能鋪多少種?下面是一個示例3 x12矩形的瓷磚。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZwpmLx0yM0ETMvw1cldWYtl2LcFGdhR2Lc52YuUHZl5SdkhmLtNWYvw1LcpDc0RHaiojIsJye.jpg)
Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.
輸入包含多個測試用例,-1表示輸入結束。每個測試用例的第一行包含一個整數0≤n≤30,表示測試用例的個數。
Output For each test case, output one integer number giving the number of possible tilings.
在單獨的一行輸出所有可能的總數目。
Sample Input
2
8
12
-1
Sample Output
3
153
2131
如果長度L是2,那麼有3種拼法,是以是3*f[n-2]
如果長度L是4或以上,有2種拼法,是以是2*f[n-L] (L 從4到n)
前面我們最初拼的時候隻取了對稱的兩種情況之一,是以,如果x>2,
拼出一個不能被豎線切割的矩形的方法隻有兩種。
那麼遞推公式自然就有了,f(n)=3*f(n-2)+2*f(n-4)+…+2*f(0),
然後再寫出f(n-2)的遞推式後兩式作差就可以得到f(n)=4*f(n-2)-f(n-4),
遞歸的邊界是f(0)=1,f(2)=4。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] mat = new int[31];
mat[0] = 1;//初始為1***
mat[2] = 3;
for (int i = 4; i < mat.length; i+=2) {
mat[i] = mat[i-2]*4 - mat[i-4];
}
while (sc.hasNext()) {
int n = sc.nextInt();
if (n == -1) {
return;
}
if ((n & 0x01) == 0) {// 偶數
System.out.println(mat[n]);
}else{
System.out.println(0);
}
}
}
}