一个有趣的问题

前言

　　这个问题来自于看到的一个面试题，其中的解题过程比较有趣，有很多值得借鉴的地方，这里写出来作为记录。

题目

假设一栋100层的楼，两个完全一样的鸡蛋。存在某一层N，当鸡蛋从大于或等于N的楼层落下时会碎掉，当鸡蛋从小于N层落下时不会碎。问用两个鸡蛋找到N的最佳方案，以及此时最坏情况下需要实验几次。

　　非完美的5分解决方案：

　　　　解决方案一的灵感来自于已知两数的和，求两数的平方和的最小值。即假设两数和为25，求两数的平方和的最小值和最大值。

　　这个解法比较简单，直接设一个数位x，则另一个数为(25-x),两数的平方和为 x2 + (x-25)2 = 2x2 - 50x + 625 = 2(x - 12.5)2 + n 可以只当x为12.5的时候取得最小值。当x为25的时候取得最大值。由此可以猜想是否可将100分成10等份，每一等份的层数正好为10层（跟前面的题目没有任何关联，只是一种第六感）。此时方案就是分别从第10层，20层，30层.. 丢第一个鸡蛋，直到第一个鸡蛋碎掉。然后从碎之前的一次丢位子的后面一层开始一直往上一层丢，直到找到刚好第二个蛋碎的位置。此时最坏情况下需要试18次。

　　完美的解决方案：

　　我们可以假设最坏的情况下需要丢x次鸡蛋。假设刚开始应该在第y层开始丢。此时第一次如果鸡蛋碎了，那么最坏的情况下找到N还需要丢y-1次。所以此时有 1 + y - 1 = x; 可以得到开始应该在第x层丢。假设第一次丢蛋没碎，那么第二次丢肯定要在x层之上丢，假设第二次丢的层数比第一次丢的高z层，同第一次一样假设第二次丢鸡蛋碎了， 那么最坏的情况下找到N需要的次数应该是: 1 + 1 + z - 1 =x;  可以得到 z = x - 1;也就是第二次应该比第一次丢的楼层高x-1层。依此类推知道最后一次就能断定是否是N。所以有下面等式：

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

　 解上面的不等式得 x = 14. 所以完美的解决方案丢的层数应该依次是： 14, 27, 39, 50, 59, 67, 84, 90, 95, 99, 100. 最坏的情况下需要测试14次。