楼层扔鸡蛋问题

----google面试题----

题目描述:有一栋100层的建筑物,若从第N层或者更高的楼层扔下来,鸡蛋会摔碎,若从第N层以下的楼层扔下来则不会摔坏。给定两个鸡蛋,找出N的值,使最差情况扔鸡蛋数目最少。

具体做法:

首先尝试着从10层开始仍,然后20层,....

1).如果我们从第10层扔下来鸡蛋1摔破了,那么最多我们还需要仍10次;

2).如果鸡蛋1最后扔下楼(100层)才摔破,那我们需要扔19次(10、20、30、40、50、60、70、80、90、91、。。。、99);

上述仅是考虑了最差的情况。

获取最差情况的最少次数的方法是:

假定最少需要判断次数为k,每丢一个鸡蛋1,应该减少一次丢鸡蛋2的次数,比如说鸡蛋1从20楼往下扔没坏,接下来从第三十楼往下扔,此时鸡蛋2就可能需要仍9次,若鸡蛋1再扔一次,我们必须要使得鸡蛋2仍喜楼的次数降8次,

由此可知,鸡蛋1必须从X层往下扔,每次增加层数为x=x-1,...,最终到达100层;

求解方程式为:

x+(x-1)+(x-2)+...+1=100   ---->x=14

也就是我们先从14层开始,然后27层,然后39层,... ,以此类推,最差情况需要仍14次

原文地址:https://www.cnblogs.com/lujun1949/p/5817621.html