编写一个以网格的宽度、W和高度H为输入的程序,并输出使用(2x1)多米诺骨牌绘制W-by H网格的不同方式的数目。
我知道如何用3xN网格来解决这个问题,但是编写递归公式对我来说太难了!
我不知道怎么做!
我创建了两个函数F(n) --对3xN的不完全平铺方式的数目,有两个函数F(N)--直到N和S(n)的完全拼接方式!但是在这里,由于高度是可变的,我想不出任何东西

约束:(0 W+H≤22)
发布于 2015-07-11 12:45:08
这有点像引擎盖下面的DPish。这个想法是IVlad的:回溯和回忆录。
memo = {}
def count_tilings_recursive(uncovered):
if len(uncovered) & 1:
return 0
if not uncovered:
return 1
if uncovered not in memo:
i, j = min(uncovered)
memo[uncovered] = count_tilings_recursive(uncovered - {(i, j), (i, j + 1)}) + count_tilings_recursive(uncovered - {(i, j), (i + 1, j)})
return memo[uncovered]
def count_tilings(m, n):
return count_tilings_recursive(frozenset((i, j) for i in range(max(m, n)) for j in range(min(m, n))))
print(count_tilings(18, 4))这里的诀窍是防止州数爆炸。首先,我们总是选择最左边的,然后是最上面的平方来覆盖,这样部分覆盖就可以按最左的最上面的顺序描述为连续覆盖的平方数,然后是部分覆盖的#行,总共最多(#rows *#列+ 1) * 2^#rows状态。第二,我们对网格进行定向,使至少有与行相同的列,将后一个数字与有趣的计算结合起来10 (因为11乘11是琐碎的)。
发布于 2015-07-11 08:38:22
对于这类问题,有一种很好的、一般的方法:
1)计算前几个值。
0 1 0 1 0 1
1 2 3 5 8 13
0 3 0 11 0 41
1 5 11 36 95 281
0 8 0 95 0 1183
1 13 41 281 1183 67282)在Integer序列在线百科全书中搜索这些值。您可以通过输入级联的反对角线来搜索方阵,也可以对几个大项进行无序搜索。成功:https://oeis.org/A099390,包括一个包含余弦的产品公式。
据我所知,没有特别好的方法直接通过动态规划来实现这一点,比如在最小维数小于指数级的多个状态下。有些高等数学是有联系的。请参阅来自OEIS条目或维基百科的引用。
Kasteleyn的余弦积公式可以用精确的算法实现。实际上,它可以使用动态规划来完成。
2 cos x = e^ix + e^-ix所以,Kasteleyn的产品
(4+2 cos 2pi j/(w+1) + 2 cos 2pi k/(h+1)) 在1<= j <= w/2范围内,当z^((w+1)*(h+1))=z^0时,1 <= k <= h/2可以写成多项式,其中指数可以计算为mod (w+1)*(h+1)。这个多项式乘积可以用动态规划来计算,在这里,您可以跟踪从0到(w+1)*(h+1)-1的每个n的z^n的系数。
// part of a C# implementation using a custom CircularVector class
using System.Numerics; // BigInteger
CircularVector cv = new CircularVector(w, h);
cv.setToOne();
for (int i = 1; i<=w/2; i++)
for (int j = 1; j <= h / 2; j++)
cv = cv.multiplyWith(new CircularVector(w, h, i, j));结果是(w+1)*(h+1)项的求和,它是z中小于(w+1)*(h+1)的多项式。例如,对于w=3,h=4,我们得到
{18, 1, 0, 1, 5, 8, 0, 1, 5, 1, 2, 1, 5, 1, 0, 8, 5, 1, 0, 1}
= 18 + z + z^3 + 5z^4 + 8z^5 + z^7 + 5z^8 + z^9 + 2 z^10 + ...找出与这个多项式z相等的整数是必要的,为此,可以用摆线多项式 Phi((w+1)*(h+1))除以多项式。
// part of a C# implementation
public static BigInteger[] cyclotomic(int n)
{
BigInteger[] working = nthRoots(n); // x^n - 1
for (int i = 1; i<n; i++)
if (n % i == 0)
working = polynomialExactDivision(working, cyclotomic(i));
return working;
}除以摆线多项式后的余数是(大)整数,它计算矩形的多米诺倾斜数。这在一个处理器上花费了0.014秒来计算20x20平方的倾斜数,1269984011256235834242602753102293934298576249856,与OEIS A004003中的值一致。计算可以在O(w^2h^2) BigInteger加法中完成,因为您可以执行大小为wh的多项式的wh乘以5项因子的wh乘法。
发布于 2015-07-11 18:26:15
在代码中写出不同状态之间的关系。高度达到2的情形等价于斐波纳契序列。具有高度3的情况可以用9个相互递归的序列(有点繁琐!)的公式编写,也可以用大小为9的向量的线性递归表示。
对于H>=4,请看一下这个文章。
R. C. Read,关于用多米诺群岛打矩形的注记,Fibonacci季刊,18.1 (1980),24-27。
从n * 2网格的情况开始。填充方法的数量是n-th Fibonacci数。为什么?因为在右边有两种方法来完成网格,或者用一个垂直多米诺骨牌,或者用两个水平多米诺骨牌。
查看它的另一种方法是从一个空网格开始,并从左到右填充它。考虑到这一点,我们可以根据它们的“轮廓”类型,即右侧的边界,对所有可能不完整的网格进行分组。
例如,对于H=2情况,有两种类型的配置文件,对于H=3,有九种配置文件类型

(这来自于本文中的图2)。
对于一般情况,使用H >= 2,我们预先计算了配置文件的列表。每个配置文件可以通过两位掩码进行编码。请注意,第一个列不应该表示完整的列,这样表示就没有歧义。
要枚举配置文件类型,同时将它们链接起来,我们尝试将一个多米诺骨牌水平放置,然后垂直放置在最左边、可用的最低单元格中。这会生成另一个配置文件,如果它是新的,我们就将它添加到列表中。每个配置文件最多可以链接到两个配置文件,这种方式。

有关H的其他选择,请参见下面的代码。这个过程给出了填充r多米诺骨牌和填充r+1多米诺骨牌的不完全网格之间的递归“公式”。它实际上不是一个公式,它是在next_profile字典中编码的。它相当于本文中的公式(1.1),用于H=3。
from collections import defaultdict
def disambiguation(a,b):
if a == (1<<H) - 1:
return disambiguation(b,0)
return (a,b)
def generate_next_profile():
global next_profile
next_profile = {}
q = [(0,0)]
done = {(0,0): True}
while q != []:
a,b = q.pop(0)
next_profile[(a,b)] = []
i = 0
while i < H and a & 1<<i != 0:
i += 1
if i+1 < H and a & 1<<(i+1) == 0:
c, d = disambiguation(a | 1<<i | 1<<(i+1), b )
next_profile[(a,b)].append((c,d))
if (c,d) not in done:
q.append((c,d))
done[(c,d)] = True
c, d = disambiguation(a | (1<<i), b | (1<<i))
next_profile[(a,b)].append((c,d))
if (c,d) not in done:
q.append((c,d))
done[(c,d)] = True
def count_it(_W, _H):
W = _W
H = _H
result = 0
if W * H % 2 == 0:
u = 0
v = 1
num = [{(0,0): 1}, {}]
n_steps = W * H // 2
for step in range(n_steps):
num[v] = defaultdict(int)
for key, value in num[u].items():
for pair in next_profile[key]:
num[v][pair] += value
u, v = v, u
result = num[n_steps % 2][(0,0)]
return result
WMAX = 10
HMAX = 10
for W in range(1, WMAX):
for H in range(1, HMAX):
generate_next_profile()
res = count_it(W, H)
print(res, end = "\t")
print()https://stackoverflow.com/questions/31354624
复制相似问题