经典谷歌面试题-扔鸡蛋问题_谷歌扔鸡蛋算法题

假如有100层楼，总共有2个鸡蛋。需要多少次才能试探出临界点，比如，在第三层扔下去，不碎；在第四层扔下去，碎了，那第三层和第四层就是临界点。 
　　如果之前没准备过的话，大概第一个想到的就是二分法。

1. 二分法

　　首先在第50层丢第一个鸡蛋，若鸡蛋碎了，则在第一层开始往上丢鸡蛋，最坏情况是试探49+1次，为什么要从第一层开始尝试呢，因为只有2个鸡蛋；若鸡蛋没碎，则在75层丢第二次，若碎了则在(50,75）区间从下往上尝试。。。

　　结论：二分法最坏尝试次数是50次。

　　显然二分法不是一个好的解决方案

2. 平方根法

　　因为100是10的平方，我们可以把10作为一个区间去尝试，即第一次在第10层丢，碎了，则需在[1,9]之间尝试；不碎，则去第20层丢。。。，一直到第90层丢，还不碎的话，则在[91,100]层逐一尝试，最坏情况是9+10=19次。现在19次了，比二分法要前进了一半以上了。并且平方根法还可以再优化一下：以15层作为起点，步伐是10。即第一层是15，第二次是25，第三次是35,45…95。这种优化后的呢，最坏情况下，是在第9次（第95层碎），然后在(85,95)区间尝试9次，即优化后的最坏尝试次数是9+9=18次。

　　结论：平方根法最坏情况下是19次，平方根优化法最坏情况下是18次。

3.解方程法

　　这里介绍下解方程法，算法的思想呢是假设最优解是x次，第一次扔的楼层也是x层。为什么第一次扔的楼层也要是x层呢？因为如果最优解成立

①当第一次扔的楼层是x+1层时，若碎了，则需要在[1,x]层里依次尝试，最坏情况是在x层碎，即尝试总次数是：1+x次，和假设不符；同理，第一次在x+1层上面的话总次数只会更多

②当第一次扔的楼层是x-1层时，若碎了，则需要在[1,x-2]层里依次尝试，最快情况是在x-2层碎，即尝试总次数是：1+x-2=x-1次，和假设不符；同理，第一次在x-1层下面的话，总次数只会更少

　　综上所述，假设最优解是x次时，第一层扔的楼层也得是x层。

开始扔鸡蛋了

        第一次是在x层扔鸡蛋，结果也就两种情况：蛋碎，蛋不碎

        蛋碎了，那么加下来只需在[1,x-1]之间扔鸡蛋即可，最坏需要x-1次，总次数即1+x-1=x次

　　蛋不碎

　　第二次得在(x,100]区间内扔鸡蛋了，具体是哪一个层呢？应该是在x层上的x-1层。为什么是x-1层呢？因为[1,100]区间，尝试次数是x次，在x层不碎，则问题转化成了在(x,100]层，最优解是x-1次，同理，扔鸡蛋的最优楼层数也得是x层上的x-1层。

　　第三次得再加x-2层扔

　　第四次得再加x-3层扔

　　以此类推…

转化成方程式是： x + (x-1) + (x-2) + (x-3) + … + 2 + 1 = 100，左边的都能理解，右边的为什么是100呢？因为楼层是100层，方程式的左边肯定小于等于100，取最坏情况那就是方程式右边是100。

　　根据等差数列求和公式Sn=n(a1+an)/2 ，x向上取整得14，即第一次在14层扔，第二次是在 14+(14-1)=27层，后面依次是39,50,60,69,77,84,90,95,99,100

所以尝试的最优解为

14,27,39,50,60,69,77,84,90,95,99,100

按照这种办法尝试，无论哪种情况下，我们的最坏尝试次数都不会超过14次

举例1：在14层碎了，我们只需尝试[1,13]层之间，每层扔一下即可，最坏情况在13层才碎，也就是一共尝试14次

举例2：前面都没碎，在39层碎了，那么我们需要在(27,38]层之间，每层扔一下即可，最坏情况在38层才碎，也就是一共尝试前面3次（14,27,39层）+后面11次=14次

举例3：前面都没碎，在99层碎了，那么我们需要在(95,98]层之间，每层扔一下即可，最坏情况在98层才碎，也就是一共尝试了前面11次（14,27,39,50,60,69,77,84,90,95,99层）+后面3次=14次

举例4：前面都没碎，在100层碎了，那就更简单了，因为前面的99层没碎，直接可得结论，99-100层是临界点，尝试总次数只有12次（14,27,39,50,60,69,77,84,90,95,99,100层）

综上抽检

无论哪种情况下，都可以做到最坏14次找到临界点