拾人牙慧-copy自yssy

Google Interview Puzzle : 2 Egg Problem

* You are given 2 eggs.
* You have access to a 100-story building.
* Eggs can be very hard or very fragile means it may break if dropped from the
first floor or may not even break if dropped from 100th floor.Both eggs are i
dentical.
* You need to figure out the highest floor of a 100-story building an egg can
be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to brea
k 2 eggs in the process

------SOLUTION-----

0.假设最高层总能使鸡蛋破裂

1.扔一次可以辨别高为多少层的楼: 2

2.扔N次可以辨别高为多少层的楼:假设为s(N)
  第一个鸡蛋扔在第 N 层 破了->第二个鸡蛋逐层扔 最多扔 N-1 次
                        没破->其上s(N-1)层需要扔 N-1 次
  所以s(N)=s(N-1)+N

3.s(N)=N(N+1)/2+1

4.s(14)=106>101 s(13)<101

-----
14层 一次
碎，就从第一层 一层一层的实验，14次
不碎，14+13=27，
在27碎，就从15层实验26层， 一共是14次，（包括14层的一次）

不碎，27+12=39一次，同上 也是14次

过程是 14+13+12+。。。+4=99
在任何一个地方碎了第一个鸡蛋，一共只需要14次即可，
如果在99层还不碎，那么已经用了 （14-3）=11次，在用一次在100层一共是12

所以最多14次

-----
按照你的格式 我们看看一般情况吧

假设有k个蛋 扔N次 最高辨认s(k,N)层

0.假设最高层碎

1.k>=N时s=2^N return
  k==1时s=N   return

2.s(k,N)=s(k-1,N-1)+s(k,N-1)+1

应该能整理出式子,我不会

python代码如下

#welcome to Script@yssy
def s(k,N):
    if k>=N:
        return 2**N
    elif k==1:
        return N
    return s(k-1,N-1)+s(k,N-1)+1

if __name__=="__main__":
    print s(2,14)

输出:

106