瓷砖覆盖问题——from《编程之美》
#!/usr/bin/env python
#coding=utf-8
# this problem stems from Beauty of Programming pp.281
# the problem is stated as follows:
# assume there's a 8x8 floor, the worker need to cover
# the floor in bricks, which are 1x2 dimension. the
# question is: how many manners to layout bricks in the
# floor? what about NxM floor? What about NxM floor and
# the brick's size PxQ?
def covManners(N, M):
"""NxM floor, 1x2 brick
"""
# defensive precaution
if ((N * M) % 2 != 0):
return (0)
# boundary
if ((N = 1 and M 2) or
(N 2 and M = 1) or
(N = 0) or (M = 0)):
return (0)
if ((N == 1 and M == 2) or
(N == 2 and M == 1)):
return (1)
# recursion
retval = (
covManners(N, M-2) +
covManners(N-1, M) -
covManners(N-1, M-2)
) + (
covManners(N, M-1) +
covManners(N-2, M) -
covManners(N-2, M-1)
)
return (retval)
def covMannersGeneral(N, M, p, q):
"""NxM floor, PxQ brick
"""
# defensive precaution
if (p = 0 or q = 0):
return (0)
if ((N * M) % (p * q) != 0):
return (0)
# boundary
if ((N = p and M q) or
(N q and M = p) or
(N = 0) or (M = 0)):
return (0)
if ((N == p and M == q) or
(N == q and M == p)):
return (1)
# recursion
retval = (
covMannersGeneral(N, M-q, p, q) +
covMannersGeneral(N-p, M, p, q) -
covMannersGeneral(N-p, M-q, p, q)
) + (
covMannersGeneral(N, M-p, p, q) +
covMannersGeneral(N-q, M, p, q) -
covMannersGeneral(N-q, M-p, p, q)
)
return (retval)
def main():
# test
p, q = 1, 2
for n in range(-5, 9):
for m in range(-5, 9):
assert covManners(n, m) == covMannersGeneral(n, m, p, q)
print "%+d x %+d floor, %+d x %+d brick: %d" %(n, m, p, q,
covManners(n, m))
p, q = 2, 3
for n in range(-5, 9):
for m in range(-5, 9):
print "%+d x %+d floor, %+d x %+d brick: %d" %(n, m, p, q,
covMannersGeneral(n, m, p, q))
if __name__ == '__main__':
main()
