2016-07-04 76 views
0

A.多米诺骨牌是2×1矩形。 2 x n矩形的平铺是由多米诺骨牌覆盖的不重叠。确定我们可以做到这一点的数量。建立一个递归关系。瓷砖盒的复现问题

B.瓦片是尺寸为2 x 2 x 1的三维盒子。大小为2 x 2 x n的盒子的瓦片是瓦片(以任何方式定向)的非重叠覆盖。确定我们可以做到这一点的方式的数量。建立一个递归关系。

rectangle and box

对于问题A,递推关系我所做的是:T(N)= T(N-1)+ T(N-2),这是一个斐波纳契数列。但对于问题B,这个问题有什么想法?

回答

2

按照与A相同的逻辑,每个位置都有3个选项,它们“消耗”1,2或2个“插槽”。这意味着递推关系是

T(N)= T(N-1)+ 2T(N-2)