Tri Tiling

第一次写博客。

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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。