瓷砖覆盖问题——from《编程之美》

rockins

               
               
               
                #!/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()


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/270/showart_1275341.html

holly2008

强
支持一个