[算法技术]2 Egg Problem
操作方法
- 01
2 Egg Problem 继续我们的推理问题之旅，今天我们要对付的是一个Google的面试题：Two Egg Problem. 我们开始吧！ No.2 Google Interview Puzzle : 2 Egg Problem * You are given 2 eggs. * You have access to a 100-storey 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 identical. * You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process 分析与解答： 题目要求试的最大次数最小。首先，讨论两个比较trivial的方案。 方案1：从第一层开始扔鸡蛋，如果鸡蛋不碎，则上一层再扔。这样，如果鸡蛋在某一层碎的话，该层就是临界的层。这种方案的优点在于省鸡蛋，只会摔破一个鸡蛋。还有一个鸡蛋可以带回家，做个鸡蛋羹，补充营养个! :) 缺点就是，如果鸡蛋在100层才碎的话，那就要试100次啦。那你等电梯要等死啦，而且还要接受别人的打量的目光，心说这怪咖为什么每次都只坐一层楼啊… 方案2： 想必很多人都会想到这个方案。我只能说，这是中国计算机教育的成功啊。这就是“二分查找法”。首先在第50层楼扔鸡蛋，如果鸡蛋不碎的话，就去75楼。如果碎了的话，那么对不起，同志。由于你只剩一个鸡蛋了，所以你得小心地从第一层开始，这样才能保证你在鸡蛋碎完的时候能找到临界楼层。这种方法的优势在于，如果你知道你的鸡蛋比较硬的话，你就采用这个方法吧。临界楼层越高，这个方法尝试的次数越小。但这种优势是用临界楼层比较小时比较大的尝试次数为代价获得的。我们看到，如果临界层数在49层的话，我们要尝试50次，而临界层数为100层的时候，尝试次数只有7次。但是，现在的问题是，全部情况下的最大尝试次数最小。这样，虽然在某些情况下，这种方法的性能很好。但是就最差情况而言，还是要尝试50次，好像还是有点大。这边，我们想起来，“二分查找法”的目标是平均性能最佳，并不是最差性能最佳。我们似乎走错了路！！！不过，方案二相比方案一来讲还是有进步的。 方案2似乎陷入了“短板效应”的泥沼，由于最坏情况下的坏性能制约了总体性能的提高。解决这个问题的总的原则应是：“一碗水端平”，尽量做到各种情况下的尝试次数尽量差不多。这正应合GOOGLE的信条Don't be evil，不以别的情况为代价换取另一些情况的指标的提高。做到“不伤害”.(呵呵，这是我瞎联想的)。那么，就照着这条路走吧，我假设每种情况下最大的尝试次数为x. 则第一次扔蛋的楼层应为x; 第二次扔蛋的楼层应为 x+(x-1); … 依次类推。 从上面看到，每次我们增加的楼层都是前一次减1.我们所要保证的就是应该在增加的层数变成0之前到顶楼，所以有： x+(x-1)+…+1≥100 这是一个等差数列，整理后有： x2+x-200≥0 发现x≥14。 我们总结一下： 第一次在14楼扔，如果碎了的话从一楼再开始扔； 否则在14+13=27层扔，如果碎了的话从15层开始扔； 否则在27+12=39层扔，如果碎了的话从28层开始扔； …… 这样，最大尝试次数为14次就行了。不信你试试。 最后，为了体现严谨性，给出本题的模型： 转移方程： minNum[n ] = min(1 + max(i – 1, minNum[n-i])) ，for 1≤i ≤n 边界条件: minNum[0] = 0; minNum[1] = 1 这里，n为楼层数，i为起始楼层数。 据说这是一个动态规划问题，我还没来得及仔细研究。其实，我的感觉是，很多理论最初的来源都是很朴素的真理，只是我们没学懂，所以把它们想复杂了。所以，很好的理论就这样不被大多数人所理解了。