• 博客访问： 980577
• 博文数量： 102
• 博客积分： 10120
• 博客等级： 上将
• 技术积分： 2754
• 用 户 组： 普通用户
• 注册时间： 2006-09-13 23:00

2011年（6）

2010年（55）

2009年（16）

2008年（25）

2008-10-08 11:56:08

 ```#!/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网友2009-04-28 17:25:21