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

全部博文(102)

文章存档

2011年(6)

2010年(55)

2009年(16)

2008年(25)

分类: Python/Ruby

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()

阅读(1657) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2009-04-28 17:25:21

冒似错了吧 我把covmanner转成c跑了一下covManner(3,4) 得7 但是我手工都画了9种了 #include int covManners(int N,int M) { int ret; //N,M均为奇数时 if(((N*M)&1)!=0) ret=0; //一块砖都放不下 else if(N<=0|M<=0|M*N==1) ret=0; else if(N*M==2) ret=1; else ret = (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)); printf("%d %d %d\n",N,M,ret); return ret; //return (covManners(N,M-2)+covManners(N-1,M)-covManners(N-1,M-2))+ // (cov