如果你有兩枚雞蛋，同時，你想知道，從樓上將雞蛋摔下而不讓它碎掉的樓層極限是多少，你會怎麼做？

剛才朋友問的一個面試題。學霸們老司機們出出奇招吧

---

1.這是一道google的面試題

有一個一百層高的大廈，從這個大廈的某一層扔下棋子恰好就會碎（稱這一層為臨界層）。請你用手中的兩個玻璃圍棋子，找出一個最優的策略來得出那個最優層。

分析：題目要求策略最優，因而要使得在最壞的情況下投擲的總次數最少。首先考慮只有一個棋子的情況，條件若為多個棋子則可轉化為一個棋子的情況。

2.解答

(1)一個棋子

棋子必須在臨界層扔下的時候碎，所以唯一的策略是從1層往上逐層投擲，此時，臨界層為99層或100層（因為題目告訴100層肯定會碎，如果99層沒碎，那表示臨界層即為100）

(2)兩個棋子

利用多的這個棋子縮小查找的範圍，因而把100層分成若干段：先利用一個棋子來確定臨界層所在的段，再利用另一個棋子確定臨界層，總的投擲次數等於確定臨界段的次數和確定臨界層的次數的和

現把100層平均分成n段（n是100的正因數），有

由均值不等式可知n=10時，為最小值，此時臨界段為第80~90層，臨界層為第89層。如果把100層分成12段：1~9,10~18,...91~99,100,與上述n=10的情況相比雖然每段的層數在減少（從而在減少），但所分的段數在增加（從而在增加），因而並沒有減少。如果把100層分成其他段（比如9段：），情況也是如此.

• 根據上面的討論，如何把100層合理地分段是關鍵。上述對100層所分段數的調整並沒有使得減少的原因在於每段包含的層數比較均勻(圖1)，因而出現和此消彼長的情況。鑒於此我們做出以下方式的調整：

• 把100層分成若干段，從下往上，每段的層數逐漸少1（圖2），這樣就使得在最壞的情況下，增加1的同時減少1，因而與的總和不變（等於第一段的層數n）,為確定n的值，只需要解不等式,從而得到n=14,從而有如下最優策略：

• 從第14層開始扔第一枚棋子，如果沒有碎則從第14+13=27層開始扔，如果還沒有碎則從14+13+12=39層開始扔，以此類推，此時,臨界層可為第27層，第39層，...第99層。

3.推廣

從上面的討論可以發現此題的關鍵是（高階）等差數列：

兩個棋子：1 2 3 4 5...

三個棋子：1 3 6 10 15....

因而我們還可以考慮大樓有m層，棋子有k個的情況

本文來自《中國初等數學研究2009卷》------一道經典面試題的解析與推廣

---

這個我學過

歸納法可證最差需要次數是O(n^(1/k))

k是雞蛋數量

下面的證明來自我寫的作業...雖然描述不太一致 但本質是一樣的。

直接複製文本比較亂 湊活著看吧（不知道知乎是不是支持latex）

(a) 我們把 n 個高度平均分成 √n 組，即第 1 個到第 [√n] 個高度一組，第 [√n] + 1 到第 [2?√n] 個高度一組, 等等。（[n] 表示 n 的整數部分。） 首先我們用第 1 個瓶子從低到高來試每一組最低的那個高度直到它碎掉，這樣我們就能 知道安全高度在哪個組裡。然後我們拿第 2 個瓶子從低到高來試這個組的每個高度直到它碎 掉，這樣我們就能確定它的安全高度在哪個位置上。 在這個方法下，這兩個瓶子都最多試 √n 次（最多再多一次），我們就有這個方法複雜度 是 O(n1/2) 的。易知這個方法滿足條件。

(b)

我們斷言，對任意的正整數 k，我們都有一個複雜度為 O(n^1/k) 的演算法。 我們對這個結論使用歸納法。由原題，有結論對 1 成立。由 (a)，我們知道結論對 2 成 立。我們現在假設結論對 k 成立，來考慮 k + 1 時的演算法。 我們將 n 個高度平均分成 n^1/(k+1) 組，即第 1 個到第 [n^k/(k+1)] 個高度一組，第 [n^k/(k+1)] + 1 到第 [2 ? n^k/(k+1)] 個高度一組, 等等。首先我們用第 1 個瓶子從低到高來 試每一組最低的那個高度直到它碎掉，這樣我們就能知道安全高度在哪個組裡。這最多 試 n^1/(k+1) + 1 次。然後我們使用歸納假設，對每組的最多 [n^k/(k+1)] + 1 個高度，有一個 O(n^k/(k+1)?(1/k) = n^1/(k+1)) 的演算法。則我們把這兩步需要的次數加起來，它仍然是一個 O(n^1/(k+1)) 的演算法。 則由歸納原理，有結論對每一個正整數均成立。即對任意的正整數 k，我們都有一個復 雜度為 O(n^1/k) 的演算法。則這一系列演算法滿足題目要求。

---

題主問題不對，應該是谷歌問題：

小明拿著兩個相同的轉基因雞蛋站在100層的大樓上。雞蛋可能很結實，從樓頂掉下也不會摔破；可能很易碎，在一樓摔下就破碎。那麼，請問小明最少試驗多少次可以找出雞蛋不會被摔碎的最高樓層

---

這是一道動態規劃題，而且已經有現成的答案。 具體可以百度搜索關鍵字 「poj 3783」

既然題主問了兩枚雞蛋，那我也簡單地就兩枚來回答一下。

假設是兩枚雞蛋從樓上往下扔，想要確定雞蛋的最高承受度x——即雞蛋在x層不會破，而在x+1層會破。且大樓最高層數為L，x&<=L,問至少需要扔幾次？

首先做一些解釋，扔一次雞蛋，如果它沒碎，則可以繼續撿回來利用，如果碎了，則手中的雞蛋數量-1。

假設變數dp[i][j]表示手中有i個雞蛋，最高樓層為j時，在最壞情況下的最少扔雞蛋次數。

假設只有一枚雞蛋，則確定這個x需要從第1層開始逐層扔x+1次，直到它破碎。

最壞情況下需要扔L次。

dp[1][L]=L;

當我們有兩枚雞蛋時，假設我們第一次在k層扔，分兩種情況：

①雞蛋破了：則我們只剩1個雞蛋，則確定x&②雞蛋沒破：則我們仍有兩個雞蛋，則確定x&>=k。 問題轉化成樓層減少k層變成L-k層,雞蛋個數為2的子問題。

考慮較壞情況，dp[2][L]= 1+ max( dp[1][k-1] , dp[2][L-k] ) = 1+ max( k-1 , dp[2][j-k] ) 。

考慮最優的取值k，

可以建立轉移方程 dp[2][j]= min( 1+ max( k-1 , dp[2][j-k] ) ). 1&<=k&<=j

然後對於j和k寫個二維循環即可得到解dp[2][L]。

註：演算法非本人所原創，我以前訓練ACM做這題的時候也是去搜題目解答的。

---

http://www.douban.com/note/247482028/#!/i!/ckDefault

補充，作為一個程序員面試題，要是不會首先就應該Google，百度，必應，雅虎…總有一款適合你

---

是不是摔過沒碎的蛋就不能用了？那麼從一樓開始摔，99%碎。

如果沒碎，上二樓。

如果再沒碎，把這個蛋拿去做研究吧，估計能發不少 paper。

---

二分法。

---

我覺得從一樓摔下去它就會碎……

==========================

好吧，嚴肅一點說，我可以首先假設不摔碎的極限樓層之概率服從幾何分布，其中參數p未知。然後採取以下步驟：

1、將第一個雞蛋從k,2k,3k,...丟下，直到其摔碎，沒有摔碎的最高樓層是nk；

2、將第二個雞蛋從nk+1,nk+2,..直到它摔碎為止。

算出雞蛋次數m(k,p)，對於滿足某種分布的p，求m(k,p)的期望m(k)，令m最小……不過我依然覺得p接近1的概率特別大……所以我還是會從一層開始扔下去……

===================

當然也可以採取別的策略，比如每扔一次，如果沒摔碎的話，給出新的置信率最大的p的分布，然後重新計算下一次扔出去的樓層……但是鑒於它是個雞蛋我依然會從一層開始扔下去……

---

首先，把兩個雞蛋孵出來，如果剛好一公一母最好，如果不是，拿一隻和別人換，湊成一公一母，然後雞生蛋，蛋生雞，雞雞蛋蛋，蛋蛋雞雞，你會有無窮多的蛋，你想怎麼試就怎麼試，隨便。

---

感覺應該是第一個雞蛋用來二分出一個包含極限的區間，然後第二個直接在這個區間從低到高暴力測試吧。

---

憑直覺這就是個動態規劃啊，設f(i,j)表示手裡有i個雞蛋樓高j層的最小扔雞蛋次數，f(i,j)=min{max{f(i-1,k-1),f(i,j-k-1)}}+1,(1&<=k&<=j)，k表示在第k層樓扔。max中的前者表示蛋碎了只剩下i-1個雞蛋了，不過只用檢查比第k層低的樓層，後者表示蛋沒碎，仍然是i個雞蛋，不過只用檢查比k高比j低的那j-k-1層樓就成。然後取一個代價最小的樓層k，把每一步最優決策k都記下來就是答案，不管你手裡有兩個雞蛋還是3個雞蛋還是n個雞蛋都這麼做就能得到解。。

---

表示有點像前幾天剛做的uva原題，當時dp胡搞過去的，然後。

---

求一滴水從多高落下就會砸死人！

---

引用前人回答

用2個玻璃球找到從一100層的大樓的某一層落下剛好會摔碎，如何制定最優策略？ - bh lin 的回答

---

是不是quant面試的題目？

我之前面試實習生時常問這題，14次吧

---

請查看algorithms4這本書的第二章課後題

---