我一直试图解决
this programming problem,但由于我无法弄明白,我在网上找到了一个解决方案.但我真的不明白为什么这个解决方案有效..
任务是计算3 * n(n> = 0,n是唯一输入)矩形可以用2 * 1多米诺骨牌完全填充多少种方式.
例如(红线代表多米诺骨牌)：
这是我在阅读文本时首先在一张纸上绘制的内容,我看到3 * 2矩形可以有三种可能的组合,如果n是奇数,则解是0,因为没有办法然后填满整个矩形(一块将始终被多米诺骨牌覆盖).
所以我认为解决方案只是3 ^ n,如果n是偶数,如果n是奇数.原来,我错了.
我发现了一个相对简单的解决方案：
- #include <iostream>
- using namespace std;
- int main()
- {
- int arr[31];
- arr[0]=1;
- arr[1]=0;
- arr[2]=3;
- arr[3]=0;
- for(int i = 4; i < 31; i++) {
- arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
- }
- int n;
- while(1) {
- cin >> n;
- if(n == -1) {
- break;
- }
- cout << arr[n] << endl;
- }
- return 0;
- }
为什么这样做？！
解决方法
设T(n)是可以用2×1瓦片平铺3×n板的方式的数量.另外,让P(n)是可以平铺3×n板的方式的数量,其中一个角被移除2×1个瓦片.假设n足够大(> = 4).
然后考虑如何从左边开始平铺(或者右边,无关紧要).
您可以通过两种方式将瓷砖放在左上角,垂直或水平.如果将其垂直放置,则必须将覆盖左下角的瓷砖水平放置,从而进行配置
- |
- ==
这留下P(n-1)种方法来平铺剩余部分.如果将其水平放置,可以将瓷砖水平或垂直放置在左下角.如果你垂直放置它,你处于和以前一样的情况,只是反射,如果你把它水平放置,你必须在它们之间水平放置一块瓷砖,
- ==
- ==
- ==
给你留下一块3×(n-2)的瓷砖.从而
- T(n) = T(n-2) + 2*P(n-1) (1)
现在,考虑到3×(n-1)板有一个被移除(已经被覆盖)的角(让我们假设是左上角),你可以在它下面垂直放置一个瓦片,给出
- =
- |
然后给你一块3×(n-2)的瓷砖,或者你可以在它下面水平放置两块瓷砖
- =
- ==
- ==
然后你别无选择,只能将另一块瓷砖水平放置在顶部,离开你
- ===
- ==
- ==
用3×(n-3)板减去角落,
- P(n-1) = T(n-2) + P(n-3)
加起来,
- T(n) = T(n-2) + 2*(T(n-2) + P(n-3))
- = 3*T(n-2) + 2*P(n-3) (2)
但是,使用(1)用n-2代替n,我们看到了
- T(n-2) = T(n-4) + 2*P(n-3)
要么
- 2*P(n-3) = T(n-2) - T(n-4)
将其插入(2)会产生重复
- T(n) = 4*T(n-2) - T(n-4)
证明完毕
