这节是留给用改善过的program来求解F(1,300,3)的。

在(四.三)中,我们碰见了递归program的运算时间太长问题,f(29,2)半天出不来结果,问题出在什么地方呢?

回顾递归式子,发现如下规律:

  • f(floors,balls) 的值是固定的,0<=floors<=300, 2<=balls<=3
  • 求f(300,3)时,不仅一次的要求出f(299,3),f(200,2)的值,而这些值在求值过程中并没有保留下来

结论就是,增加一个数组来保留求出的f(floors,balls)值;

rengqiu={}
topfloor=301
maxballs=3
for i in range(0,topfloor):
    for j in range(2,maxballs+1):
        rengqiu[i,j]=-1
rengqiu[0,2]=0
rengqiu[1,2]=1
rengqiu[0,3]=0
rengqiu[1,3]=1
rengqiu[2,3]=2

def f(floors, balls):
    if balls!=2 and balls!=3:
        print("exception")
        return -1
    if rengqiu[floors,balls]!=-1:
        return rengqiu[floors,balls]
    if balls==3:
        minimum=10000
        for i in range(1, floors):
            for j in range(i+1, floors+1):
                b1=f(i,2)+1
                b2=f(j-i-1,2)+2
                b3=f(floors-j,3)+2
                maximum=max(b1,b2,b3)
                if maximum<minimum:
                    minimum=maximum
    else:
        minimum=10000
        for i in range(1, floors+1):
            b1=i
            b2=f(floors-i,2)+1
            maximum=max(b1,b2)
            if maximum<minimum:
                minimum=maximum
    rengqiu[floors,balls]=minimum
    return minimum

>>> f.f(299,3)
13

版权所有,引用请注明出处

Advertisements