一幢 200 層的大樓，給你兩個雞蛋。如果在第 n 層扔下雞蛋，雞蛋不碎，那麼從第 n-1 層扔雞蛋，都不碎。這兩隻雞蛋一模一樣，不碎的話可以扔無數次。最高從哪層樓扔下時雞蛋不會碎？

11-25

谷歌面試題，前兩年用它K了許多成名人物。提出一個策略, 保證能測出雞蛋恰好會碎的樓層, 並使此策略在最壞情況下所扔次數最少

看到靠譜的答案都沉了, 就發了篇文章在blog上:Problem of Two Eggs . 主要內容粘過來, 公式格式懶得轉了.

題目嚴謹描述:
一幢 200 層的大樓,給你兩個雞蛋. 如果在第 n 層扔下雞蛋,雞蛋不碎,那麼從前 n-1 層扔雞蛋都不碎.
這兩隻雞蛋一模一樣,不碎的話可以扔無數次. 已知雞蛋在0層扔不會碎.
提出一個策略, 要保證能測出雞蛋恰好會碎的樓層, 並使此策略在最壞情況下所扔次數最少.

搞清楚這題的意思:
第一個雞蛋用來試探, 只要它從 k 層樓扔下去沒碎, 則目標就在[k+1, 200]之間了.
但一旦運氣不好碎了, 對於已知的區間, 我們只能用剩下一個雞蛋從小到大一層層試,
因為我們要保證策略必須成功, 不能冒險了.

"最壞情況下代價最小"這句話十分重要, 它反映了題目的重要數學結構:
我們可以把任何一種策略都看成一個決策樹,
每一次扔瓶子都會有兩個子節點, 對應碎與不碎的情況下下一步應該扔的樓層.
那麼, 策略的一次執行, 是樹中的一條從根往下走的路,
當且僅當這條路上出現過形如 k 沒碎與 k+1 碎了的一對節點時, 路停止, 當前節點不再擴展.
那麼要找的是這麼一棵樹, 使得所有路里最長者盡量短, 也即, 要找一個最矮的決策樹.

再看一個節點處, 選擇樓層時會發生什麼.
容易看出, 選擇的樓層如果變高, 那麼"碎子樹"高度不減, "不碎子樹"高度不增.
同樣的, 選擇的樓層變矮的話, "碎子樹"高度不增, "不碎子樹"高度不減.

這時候答案很明顯了: 為了使兩子樹中高度最大者盡量小, 我們的選擇應當使兩子樹高度盡量接近.
最終希望的結果是, 整個二叉樹盡量像一個滿二叉樹.

假設第一次在根節點上, 我們選擇扔k層, 其"碎子樹"的高度顯然是k - 1.
為了考慮不碎子樹的高度, 設不碎後第二次扔m層(顯然m &> k ),
則這個新節點的碎子樹高度為 m - k - 1, 不碎子樹高度仍然未知,
但按照滿二叉樹的目標, 我們認為它與碎子樹相同或少1就好.
那麼在根節點上的不碎子樹的高度就是m -k-1 + 1, 令它與碎子樹高度相同, 於是:
m - k - 1 + 1 = k - 1 =&> m = k + k - 1

也即, 如果第一次扔在k層, 第二次應該高k-1 層, 這可以有直觀一點的理解:
每扔一次, 就要更保守一些, 所以讓區間長度少1. [1, k) -&> [k + 1, 2k - 1).
用類似剛才的分析, 可以繼續得到, 下一次應該增高k - 2, 再下一次應該增高k - 3.

如果大樓100層, 考慮:
$k + (k-1) + cdots + 1 = frac{k(k+1)}{2} = 100 Rightarrow k approx 14$

所以第一次扔14層, 最壞需要14次(策略不唯一, 樹的葉子可以交換位置).200層的話, 類似得到k =20.

以上是數學做法...當然還有代碼做法....
設f(n, m)為n層樓, m個蛋所需次數, 那麼它成了一道DP題..
$egin{eqnarray} f(0, m) = 0, (m >= 1)\<br /> f(n, 1) = n, (n >= 1)\<br /> f(n, m) = min_{1 le i le n} { max{ f(i - 1, m - 1), f(n - i, m)}} + 1 \<br /> end{eqnarray}$

以下代碼python3 only:

import functools @functools.lru_cache(maxsize=None) def f(n, m): if n == 0: return 0 if m == 1: return n


    ans = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)]) + 1

    return ans

print(f(100, 2)) # 14 print(f(200, 2)) # 20

（剛開始看到一樓@吳育昕的分析比較高大上...看不懂...於是寫了一下求解代碼，發現和他最後的代碼是一樣的……忽略我吧）

python code:

ans = {0:0, 1:1}


def f(n):

    if n not in ans:

        ans[n] = min([1+max(k-1, f(n-k)) for k in range(1, n+1)])

    return ans[n]

if __name__ == "__main__": f(200) print(ans[200])

答案： 20

這題其實就是把Kleinberg 的《Algorithm Design》上的習題2.8改成了一個面試向的題目，答案 @吳育昕已經給出了，是 $lfloorsqrt{200} floor=14$ 。在這裡記錄一下窩的腦洞想法：

考慮 $n$ 層樓， $k$ 個雞蛋的情況：
考慮 $k=1$ 的情況，答案顯然為 $O(n)$ （線性枚舉）
考慮 $k=O(log_2n)$ 的情況，答案顯然為 $O(1)$ (二分查找）
當 $k=2$ 的時候，首先在 $sqrt{n}$ 的位置試驗，此時有兩種可能：

雞蛋A碎掉，問題轉化為在 $[1,sqrt{n}]$ 上一個雞蛋的問題
雞蛋A沒碎，則在 $2sqrt{n}$ 繼續測試...

容易發現兩隻雞蛋的試驗次數都不會超過 $O(sqrt{n})$
如果是三隻雞蛋的話，那麼就可以利用第一隻雞蛋將問題規模轉化到 $O(sqrt{n})$ 級別，所以試驗次數是 $O(n^{frac{1}{4}})$ ...

這樣就可以很方便的推廣到 $n$ 層樓 $k$ 個雞蛋的情況啦，答案就是 $O(n^{frac{1}{2^{k-1}}})$

步進20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5
最壞結果是20次

在手機上保存草稿就直接發布了，真奇怪。

這道題有兩種思路。樓上提到的DP（動態規劃）可以系統地推廣到 n 層樓 k 個蛋的情況。在 INFORMS Transactions on Education 上有專門一篇非常詳細的科普文章介紹。不再贅述。

文章地址在這：

OR/MS Games: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong: INFORMS Transactions on Education: Vol 4, No 1

另外一種更IQ題的思路，感覺有點優化理論中 primal dual 的思想。大概意思就是均攤扔壞兩個蛋所需要的最壞次數使得他們平均。Intuition 是，解很多對稱的二元方程時都是 x=y 時達到最優（這樣不一定嚴謹，只是一個思路）。具體來說，假設我們每10層樓扔第一個蛋，當在10x層扔壞，我們從10(x-1) 開始順序扔到 10x。那麼最壞情況下需要 10 + 9 = 19. 10 是第一個蛋的，9是第二個蛋的次數。按照這個方法，當第一個蛋達到最壞情況時，比第二個剛好多一。這樣是平衡的。問題在於，如果第一個蛋在10就碎了，那麼第二個蛋要扔9次，總共10次。兩種最壞情況不平衡。也就是說，我們希望動態地調整扔蛋一的層數，使得（蛋一+蛋二）的總和平均。

那麼考慮這個方法：假設蛋一第一次扔在X層，第二次扔在比原來高 X-1層，... 高2，高1，使得X+(X-1)+...+2+1=100，那麼最壞情況總的次數就是：

如果在第X層就碎，那麼蛋二最壞情況要扔X-1，所以總數是 1+X-1=X
如果在X+(X-1)碎，那麼蛋二最壞情況要扔 X-2，所以2+X-2=X
...

解得 X = 14.

這也算是道陳題了，目前看到的答案中正確的答案不多，即便是正確的演算法時間複雜度也不足夠好。我下面對這道題進行一個完整的分析。

重述一下題目，現在有一種雞蛋，其特性是在H樓及以下摔下去都不會碎，但在H+1樓以上摔下去都會碎。已知雞蛋在0樓的時候不會碎並且在N+1樓一定碎。現在有一棟高度為N樓的大廈，並且有K個這種雞蛋（一個雞蛋沒有碎就可以再次進行實驗），問在最壞情況下最少需要實驗多少次才能確定H的值。

--------------分割線--------------

第一大類的方法如@吳育昕所述，設F[i, j]為H的可行範圍為[0, i]，我手上還有j個雞蛋的時候，最壞情況下的最小試驗次數是多少。這個狀態方程能夠設立是基於這樣一種想法，如果H的可能範圍目前是[L, R]，那麼其狀態與[0, R-L]是完全一致的，所以我們僅僅記錄有可行範圍的寬度就可以了。我們的目標函數就是F[N, K]。

這種DP方程的狀態確立以後，轉移也是非常自然的，F[i, j]=min{max{F[k-1, j-1], F[i-k, j]}}+1，其中1&<=k&<=i。

k表示這一次實驗是從k樓把雞蛋扔下去，扔下去有兩種結果。一種是雞蛋碎了，那麼剩餘的雞蛋個數是j-1，H的可行範圍變為[0, k-1]，那麼需要的最少實驗次數為F[k-1, j-1]。另一種是雞蛋沒碎，那麼剩餘的雞蛋個數是j，H的可行範圍是[k, i]，那麼需要的最少實驗次數是F[k-i, j]。由於題目所求的是最壞情況下的最優策略，所以對每種k情況內取max，再對所有k取min。

邊界條件為F[0, j]=0，F[i, 1]=i。時間複雜度為O(NK^2)。根據從《鷹蛋》一題淺析對動態規劃演算法的優化一文，狀態轉移最多可以優化到O(logN)【註：這個優化過程還是有點複雜的，這裡就不贅述了，有興趣的可以看原文】，那麼這類總的時間複雜度最快可以達到O(NlogN)。

--------------分割線--------------

第一類演算法可以處理N相對不大的情況，但是受制於狀態設置所限，狀態數量為N，也就意味著時間複雜度最少為O(N)，這對於N較大的情況來說是無法接受。如果我們希望得到更優的結果，特別是在K較小N較大的情況下的更好的演算法，我們就需要先從狀態設置入手。

我們考慮這樣一個事實，F[i, j]&>=F[i-1, j]，也就是說，樓層少了一樓，最優實驗次數一定不增。那麼，對於一個給定的實驗次數u和一個給定的雞蛋個數v，一定存在一個G[u, v]，使得F[G[u, v], v]=u。在給定v的情況下變動u，一旦G[u, v]小於等於N，那麼我們就能得出最少實驗次數為u。

設G[u, v]表示用u次實驗，v個雞蛋能夠確定的H最大寬度。那麼我們可以得到狀態轉移方程G[u, v]=G[u-1, v]+G[u-1, v-1]+1。假如我們面對一個給定的H可行寬度G[u, v]以及雞蛋個數v，那麼第一個雞蛋在G[u-1, v-1]+1處實驗肯定是一個最優決策，那麼對應的沒碎的情況可以測出來的寬度是G[u-1, v]，兩者加和就可以得到遞推公式G[u, v]=G[u-1, v]+G[u-1, v-1]+1。

根據這一公式，根據題目的不同類型我們可以有不同的做法。

當K很小（K約為100），答案很大（超過10^6）時，我們可以使用矩陣快速冪進行遞推。

當K很小，N很大（N約為10^18），並且有多次詢問時，我們可以進行對答案遞推的預處理，預處理答案範圍可以到3·10^6，然後進行二分查找。這種情況下還需要對K=1, 2進行特判。

即便是沒有任何特殊條件的題目，使用這種方法也會比第一種方法更快，因為答案是O(N^(1/K))【這一結論純屬猜想】，那麼這個遞推過程的時間複雜度也就只有O(K·N^(1/K))。

我來完善一下 @謝德輝和 @Spirit_Dongdong 的回答吧。

假設總共有n層樓。如果第一雞蛋固定步長x來扔，那麼第一步最多需要扔n/x次（取整問題就忽略了），第二個雞蛋在第一步的某個步長之間試驗，最多要x-1次。總次數為x+n/x-1，為使其最小，有x=n^0.5。對於n=200來說，最多需要試驗27次。

如果第一步不固定步長，則用畫圖的方式說明。第i行中x的數量代表第一個雞蛋第i次試驗的步長。以n=36為例，如果每次試驗的步長是8,7,6,5,4,3,2,1（即分別在8,15,21,26,30,33,35,36樓扔一次），則表示為
occcccxx
dxxxxcx
dxxxxc
dxxxx
dxxx
ddd
xx
x

試驗的流程就像在這個圖上走貪食蛇一樣，從左上角開始先向下走，等到第一個雞蛋摔碎之後開始向右走，最差情況則是走到最右側邊界為止。
很顯然，安排成等腰三角形是最合適的，這時候從原點出發到斜邊的每一個點走的距離都是t（例如，圖中oddddddd和occccccc兩條路），其中t(t+1)/2=n。對於n=200來說，需要20步。

題最終是要找到臨界點，假設為K，就是對任何i小於等於K，雞蛋都不會碎。對任何i大於K，雞蛋都會變成一灘。。
所以對於邊界附近的值，只能從小到大一個一個嘗試。
我個人覺得這個題就是用第一個雞蛋劃分範圍，第二個雞蛋在範圍內一個個嘗試
比如在第10層扔個雞蛋，還沒碎就去第20層扔。。直到扔碎為止。假設第i次雞蛋被扔碎，那麼這個層數就在10*i+1到10*(i+1)之間
從10*i+1到10*(i+1)，每層扔次雞蛋，直到碎了為止。這一過程是不能跳躍的。
最壞情況是199層雞蛋才碎，一共需要扔第一個雞蛋20次+扔第二個雞蛋9次=29次

總結一下，第一個雞蛋用來劃分範圍，假設採用上面使用的線性範圍，那第1個雞蛋每次步進i（上面的例子，i=10）
第二個雞蛋用來在範圍內逐個搜索，步進為1
這樣最壞的情況，需要扔雞蛋的次數就是200/i + (i-1)。那麼算一下i為14（15）的時候最好。最壞情況，14的話是195層需要扔27次，15的話是194層也是扔27次

上述只是針對線性劃分，別的劃分方式是否會有更好結果暫時木有想到。。

最優次數= n + 向上取整（K/n）的最小值，其中K為樓的層數。極值條件為n=K/n，所以當n為K開方時取極值，此時得到的就是最優次數。

先扔一樓。沒碎，趕緊拿上雞蛋去賣。

首先基本策略是蛋1按一個遞增序列扔下樓, 因為我們事先不知道在哪層雞蛋會碎掉,
所以我們的策略是既定的, 我們設這個序列為 ${a_i}$ , i = 1, 2, 3...

當蛋1在某層 $a_k$ 碎掉而 $a_{k-1}$ 沒碎時, 能夠確定答案在 $[a_{k-1}, a_k-1]$ 區間內,
於是我們用蛋2依次測試區間內的層數, 即用蛋2從 $a_{k-1}+1$ 開始扔到 $a_k-1$ ,
直到蛋2碎掉或到達 $a_k-1$ 仍沒碎, 我們就能夠得到答案.
在這個區間內, 最壞情況是蛋2一直扔到 $a_k-1$ ,
加上蛋1的最壞情況總扔蛋次數為 $W_{k} = k + a_k - a_{k-1} -1$ .

方便起見, 引入 ${b_i}$ , i=1,2,3..., 其中 $b_i = a_i - a_{i-1}$ , 並約定 $a_0 = 0$ .
則最壞情況總扔蛋次數為 $W_k = k + b_k - 1$ .
對於第k+1個區間, 最壞情況總扔蛋次數為 $W_{k+1} = k+1 + b_{k+1} -1$ .

而 $sum_{i=1} b_i = 200$ , 對於給定的一個 ${ a_i }$ , $sum_{i = 1} W_i$ 是一個定值.
易知, 要使 $max{Wi}$ 最小, 每個 $W_i$ 應相等. 於是能夠知道 ${b_i}$ 是一個以1遞減的序列.
於是 $W = W_1 = 1+b_1 -1 = b_1$

但 $b_i$ &> 0 , 因此序列元素的個數n 應當小於 $b_1$ ,
由 $sum_{i = 1} ^ n b_i = 200$ 得到 $frac{n(b_1+(b_1+1-n))}{2} = 200$ ,
解出滿足上述條件且 $b_1$ 最小的整數解, $b_1$ = 20, n = 16.

於是扔蛋1的策略序列 ${a_i}$ 為
20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5.
共16個.
能夠保證最壞情況下的扔蛋次數不超過W=20次.

假設第一個雞蛋投出去的樓層分別為
$a_{1} ,a_{2},...,a_{i},i=1,2,3,...$ (1)
如果第一個雞蛋在 $a_{i}$ 樓層碎掉，那麼下面第二個雞蛋在保證必須檢測出樓層的情況下需扔出 $a_{i}-1 -( a_{i-1}+1)+1=a_{i} -a_{i-1}-1$ (2)
所以在若第一個雞蛋在 $a_{i}$ 層碎掉時，扔需要扔出的總次數為 $f(i)=a_{i}-a_{i-1}+i-1,i=1,2,3...$ (3)
最壞的情況（次數最多）可能出現在以下情況中
$f(1), f(2),...f(i)$ (4)
如果(4)中存在 $f(k) e f(j)$ ,不妨設 $f(j)geq f(k)$ ,那麼總可以通過選擇 $a_{j}$ 使 $f(k)= f(j)$
所以要使最壞情況次數最少，那麼(4)中各式相等.
即有，
$f(1)=a_{1}$
$f(2)=a_{2}-a_{1}+1=f(1)$
...
$f(i)=a_{i}-a_{i-1}+i-1=f(1)$

$Rightarrow$ $a_{i}=ia_{1}-frac{i(i-1)}{2}$ ,

可以看出 $left{ a_{i} ight}$ 為遞減數列，取 $max$ 時有 $a_{1}=i$ .
$maxgeq 200$ ，解出 $a_{1}=20$ .
所以扔的樓層差分別為20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5
次數為20.

最近在看控制論與科學方法論，不妨用控制論的思路試試:

M/Q≤mA

M代表事物總可能性空間，200層樓每層都可能讓雞蛋碎或者不碎，所以M=400
Q代表工具或人對事物的控制能力，也就是所求的值，由於有兩個蛋，所以Q=x∧2
mA代表預先設定的工作目標，找到剛好碎的樓層mA=1

很容易算出Q=400，所求的值為20，而20則是每個蛋的最大控制能力，即第一次從20層開始扔，然後每次遞減繼續，直到碎了，然後再用第二個蛋測試

思想：
第一個雞蛋：每次間隔固定樓層，比如5層，則第一個雞蛋扔的層數為5，10，15，20。。。
第二個雞蛋：如果雞蛋在15層扔的時候破了，就從第11層開始扔第二個雞蛋，每次加一層，可得到結果
現在需要考慮的問題是：第一次扔雞蛋時，每次間隔多少層，可以讓扔雞蛋的總次數最小？

設樓層總層數為k,第一次扔雞蛋間隔層數為x，扔雞蛋總次數為y,則
$y = k/x +x$ ：第一次扔雞蛋的次數＋第二次扔雞蛋的次數
$y$ :求導
$x = sqrt{k}$ 時， $y$ ，此時扔雞蛋的總次數最少。

即：第一個雞蛋每次間隔層數為樓層總高度開根號

這是好久以前的題目了，google真的這兩年又把它翻出來了？從《鷹蛋》一題淺析對動態規劃演算法的優化
1223. Chernobyl』 Eagle on a Roof @ Timus Online Judge

想那麼麻煩幹嘛？！
個人看法，別噴我。
第一個演算法，多少層樓，開個根號。
第二個演算法，後面的，隔一層樓扔一次。
100的如下：
100開平方根是10，最壞情況：跑到100樓碎了，然後最多再算9次，從91--99。
我的全部樓層檢測完，最壞情況是10+9次。
而200的那個：
200開平方根是14.14,14*14=196，餘4.
最壞情況，出現在182--196之間，總共需要扔14+13=27次。

回答之前我看了一眼大家的回答，有正確回答但是不多啊，有的還很複雜。這道題目也算是一道經典題了，我簡單說一下思路吧。

我們現在要做的事是最小化最壞情況。現在只有兩個蛋，那第一個蛋按一定間距扔，比如按10,20,30的層數來扔。如果10樓沒碎20樓碎了，那拿第二個雞蛋從11開始一層層往上扔蛋，最終能找到最高扔蛋不會碎的樓層。

按這種假設，無論第一個蛋扔幾次，第二個蛋最多都要扔九次。那麼為了最壞情況最小，第一個蛋多扔一次，就讓第二個蛋少扔一次才能平衡扔的次數，也就是說，我們在x層扔第一個蛋，沒碎就往上（x-1）層再扔，還沒碎就往上（x-2）層再扔，以此類推。

列出公式：x+（x-1）+（x-2）+ …… +2+1≥100，且x為整數。按這個碼代碼就好了嘛，最後求出來x=14

附上python代碼，可以在 lintcode 上直接online judge 一下 drop eggs ：

public class Solution { /** * @param n an integer * @return an integer */public int dropEggs(int n) { // Write your code herelong ans = 0; for (int i = 1; ; ++i) { ans += (long)i; if (ans &>= (long)n) return i; } } }

這是我看到的目前為止最簡潔的版本啦，還有JAVA和C++版本的，直接給你們鏈接扔雞蛋答案，代碼我就不貼過來了。

這道題在 lintcode上屬於偏簡單的題目，lintcode 上還有一道變形題，dropp eggs II , 則屬於中等難度的題目，把這道題也做一下，有助於加深對題目的理解，在面試中如果遇到面試官出變形題也可以不慌不亂了。

授人以魚不如授人以漁，代碼不是重點，重點是我說的思路，希望對大家有幫助吧~

一、n層，碎了，最壞是n-1層壞，要試n-1次，

二、n層，不碎，在上到第2n層

三、到200層時，不超過n-1的重複

只要有限的嘗試就可以了

1比如15，最壞14碎，1-14，14次

再到2x15=30層，3x15=45層，---------14X15=210〉200

15層開始

用公式表示：nX(n-1)〉200

設從 x 層開始扔，每隔 y 層扔一次，扔的次數為 i 。若某 x+(i-1)y 層把第一個雞蛋扔碎了(i&>1)，則回到 x+(i-2)y+1 層，一層一層往上扔，直到扔碎第二個雞蛋為止，扔的次數 i 繼續遞增。
編寫程序，取 1&

如果是數學題的話，x 和 y 的值當然要自己算出來，但是這既然是一道IT公司面試題，那應該可以用編程解決。200這個數字對於計算機來說並不大，即使是O(n^2)的時間複雜度也很快能算出來，那麼用窮舉法遍歷x與y的所有組合也是可以的吧。

哭了，2016年騰訊校招筆試題，答案剛好之前都看過了，就是寫不出了。。。