• Python来求解扔球问题
    def f(floors, balls):
        if balls!=2 and balls!=3:
            print("exception")
            return -1
        if floors==0 and balls==2:
            return 0
        if floors==1 and balls==2:
            return 1
        if floors==0 and balls==3:
            return 0
        if floors==1 and balls==3:
            return 1
        if floors==2 and balls==3:
            return 2
        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
        return minimum
  • 结果验证 balls=2

    >>> for i in range(1,27):
        tries=f.f(i,2)
        print(i,tries)

    1 1
    2 2
    3 2
    4 3
    5 3
    6 3
    7 4
    8 4
    9 4
    10 4
    11 5
    12 5
    13 5
    14 5
    15 5
    16 6
    17 6
    18 6
    19 6
    20 6
    21 6
    22 7
    23 7
    24 7
    25 7
    26 7

  • 虽然这个结果证明f(floors,balls)是正确的,但是性能很差,因为f(29,2)要花很长时间才能返回结果,更别提f(300,2)和f(300,3)了。
    如何提高它的性能,又是另外一篇文章了
  • 问个问题
    将这段program给某个人看,而此人事先不知道这个program是用来求解经典问题的,你说他能判断出来此program的意图么?

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

Advertisements