第一次寫博客。

Problem Description：

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

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.

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 題目意思給你一個3*n矩形，用2*1的矩形將它填滿，有多少種情況。 這是一題遞推題，首先當n為奇數的時候，3*奇數=奇數，用2*1的矩形是怎樣都填不下去的。 所以只要考慮n為偶數的情況。 設3*n時情況有a[n]種； 當n=2時，有以下三種情況： 當n>2時，如果圖形中不包含n=2時的三種情況的話，那么就只會有2種情況。 例如n=4： 將其反過來又是一種。 根據以上兩種情況可以將長為n的矩形分兩塊：n-2+2；n-4+4；n-6+6……n-n+n； ①n-2+2的情況有a[n-2]*3; ②n-4+4的情況有a[n-4]*2;為什么這里是*2而不是*a[4]?因為4分成2與2的話會與②中的重復，所以只需考慮4中不能分成2與2情況 …… 所以a[n]=a[n-2]*3+2*（a[n-4]+a[n-6]+……+a[n-(n-2)]+a[0](注意a[0]=1)）; #include<stdio.h> int a[35]={1,0,3}; int f(int x) {int sum=0;for(int i=x;i>=0;i-=2)sum+=a[i]*2;return sum; }int main() {int n;for(int i=4;i<=30;i+=2){a[i]=a[i-2]*3+f(i-4);a[i-1]=0;}while(scanf("%d",&n)!=EOF){if(n==-1)break;printf("%d\n",a[n]);} }

?

轉載于:https://www.cnblogs.com/-yuxia/p/5268675.html

總結

以上是生活随笔為你收集整理的Tri Tiling的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。