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為起始樓層數。
據說這是一個動態規劃問題，我還沒來得及仔細研究。其實，我的感覺是，很多理論最初的來源都是很樸素的真理，只是我們沒學懂，所以把它們想複雜了。所以，很好的理論就這樣不被大多數人所理解了。