用2x1的多米诺骨牌，你可以以多少种方式铺设一个3xn的矩形？

Question

我每天都在苦苦思索算法问题，尝试在这里提问我无法回答的问题。如果我给您带来了任何困扰，请谅解。

这是来自滑铁卢大学ACM编程竞赛的问题。

你可以用2x1的多米诺骨牌如何铺满一个3xn的矩形？

涅槃：闻起来像递归精神。

- user467871

Answer 1

这是对taskinoor答案中隐式给出的方程的明确解决方案：

或者

f[n]=((1 + (-1)^n)*((2 - Sqrt[3])^(n/2)*(-1 + Sqrt[3]) + 
     (1 + Sqrt[3])* (2 + Sqrt[3])^(n/2)))/(4*Sqrt[3]) 

如果有人在意的话。

我们展示10个数值（对于奇数n没有解）{n,f[n]}：

{6, 41.},   
{12, 2131.},   
{18, 110771.},   
{24, 5.75796*10^6},   
{30, 2.99303*10^8},   
{36, 1.5558*10^10}, 
{42, 8.08717*10^11},  
{48, 4.20377*10^13}, 
{54, 2.18515*10^15}, 
{60, 1.13586*10^17}

- Dr. belisarius

---

+1。真的很困惑，不知道该接受哪个正确答案。谢谢你们两位。 - user467871

@taskinoor 它与斐波那契显式形式有着奇妙的相似之处 http://upload.wikimedia.org/math/a/f/9/af9b6b5e3dea6654db4794bd066dd433.png - Dr. belisarius

@hilal 答案是由 taskinoor 提供的。我只是对此进行了详细阐述。 - Dr. belisarius

请注意，$(2+\sqrt3)^{1/2}=(1+\sqrt3)/\sqrt2$，因此可以简化。 - Akiva Weinberger

事实上，对于任意偶数 $n$，它是最接近以下整数的值：$$\dfrac{(1+\sqrt3)^{n+1}}{2^{n/2+1}\cdot\sqrt3}$$ - Akiva Weinberger

Answer 2

您可以使用动态规划来解决这个问题。请查看此链接获取可能的解决方案。

- taskinoor

---

@hitesh_noty 这个链接已经失效了。我很久以前写了这个答案，当时我还不理解只有链接的答案存在的问题。我在这里找到了另一个解释：http://cs.stackexchange.com/questions/42170/why-do-these-recurrences-determine-the-number-of-ways-of-tiling-a-3xn-rectangle 但是，老实说，我需要编辑这个答案，将解释添加到这里，这样它就不依赖于其他链接了。 - taskinoor

Answer 3

关于如何获得显式解公式的注释，诀窍是将其作为矩阵乘法写成递归形式，然后使用矩阵的特征值公式来计算第n次幂。 对于上述递归，方程为：

(不可用)

您可以在belisarius的显式公式中看到四个特征值。

- Yaroslav Bulatov

---

如果你只是在寻找一个算法，那么可以在O(logn)的时间内计算矩阵的幂，这样做的优点是只使用整数运算。 - Aryabhatta

图片丢失。 - taskinoor