繼續(xù)我們的推理問題之旅，今天我們要對(duì)付的是一個(gè)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
分析與解答：
題目要求試的最大次數(shù)最小。首先，討論兩個(gè)比較trivial的方案。
方案1：從第一層開始扔雞蛋，如果雞蛋不碎，則上一層再扔。這樣，如果雞蛋在某一層碎的話，該層就是臨界的層。這種方案的優(yōu)點(diǎn)在于省雞蛋，只會(huì)摔破一個(gè)雞蛋。還有一個(gè)雞蛋可以帶回家，做個(gè)雞蛋羹，補(bǔ)充營養(yǎng)個(gè)! :) 缺點(diǎn)就是，如果雞蛋在100層才碎的話，那就要試100次啦。那你等電梯要等死啦，而且還要接受別人的打量的目光，心說這怪咖為什么每次都只坐一層樓啊…
方案2： 想必很多人都會(huì)想到這個(gè)方案。我只能說，這是中國計(jì)算機(jī)教育的成功啊。這就是“二分查找法”。首先在第50層樓扔雞蛋，如果雞蛋不碎的話，就去75樓。如果碎了的話，那么對(duì)不起，同志。由于你只剩一個(gè)雞蛋了，所以你得小心地從第一層開始，這樣才能保證你在雞蛋碎完的時(shí)候能找到臨界樓層。這種方法的優(yōu)勢在于，如果你知道你的雞蛋比較硬的話，你就采用這個(gè)方法吧。臨界樓層越高，這個(gè)方法嘗試的次數(shù)越小。但這種優(yōu)勢是用臨界樓層比較小時(shí)比較大的嘗試次數(shù)為代價(jià)獲得的。我們看到，如果臨界層數(shù)在49層的話，我們要嘗試50次，而臨界層數(shù)為100層的時(shí)候，嘗試次數(shù)只有7次。但是，現(xiàn)在的問題是，全部情況下的最大嘗試次數(shù)最小。這樣，雖然在某些情況下，這種方法的性能很好。但是就最差情況而言，還是要嘗試50次，好像還是有點(diǎn)大。這邊，我們想起來，“二分查找法”的目標(biāo)是平均性能最佳，并不是最差性能最佳。我們似乎走錯(cuò)了路！！！不過，方案二相比方案一來講還是有進(jìn)步的。
方案2似乎陷入了“短板效應(yīng)”的泥沼，由于最壞情況下的壞性能制約了總體性能的提高。解決這個(gè)問題的總的原則應(yīng)是：“一碗水端平”，盡量做到各種情況下的嘗試次數(shù)盡量差不多。這正應(yīng)合GOOGLE的信條Don't be evil，不以別的情況為代價(jià)換取另一些情況的指標(biāo)的提高。做到“不傷害”.(呵呵，這是我瞎聯(lián)想的)。那么，就照著這條路走吧，我假設(shè)每種情況下最大的嘗試次數(shù)為x.
則第一次扔蛋的樓層應(yīng)為x;
第二次扔蛋的樓層應(yīng)為 x+(x-1);
…
依次類推。
從上面看到，每次我們?cè)黾拥臉菍佣际乔耙淮螠p1.我們所要保證的就是應(yīng)該在增加的層數(shù)變成0之前到頂樓，所以有：
x+(x-1)+…+1≥100
這是一個(gè)等差數(shù)列，整理后有：
x2+x-200≥0
發(fā)現(xiàn)x≥14。
我們總結(jié)一下：
第一次在14樓扔，如果碎了的話從一樓再開始扔；
否則在14+13=27層扔，如果碎了的話從15層開始扔；
否則在27+12=39層扔，如果碎了的話從28層開始扔；
……
這樣，最大嘗試次數(shù)為14次就行了。不信你試試。
最后，為了體現(xiàn)嚴(yán)謹(jǐn)性，給出本題的模型：
轉(zhuǎn)移方程：
minNum[n ] = min(1 + max(i – 1, minNum[n-i])) ，for 1≤i ≤n
邊界條件:
minNum[0] = 0; minNum[1] = 1
這里，n為樓層數(shù)，i為起始樓層數(shù)。
據(jù)說這是一個(gè)動(dòng)態(tài)規(guī)劃問題，我還沒來得及仔細(xì)研究。其實(shí)，我的感覺是，很多理論最初的來源都是很樸素的真理，只是我們沒學(xué)懂，所以把它們想復(fù)雜了。所以，很好的理論就這樣不被大多數(shù)人所理解了。
參考文獻(xiàn)：
1. http://blog.csdn.net/TravelInHistory/archive/2006/12/07/1434098.aspx
2. http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html