扔雞蛋問題詳解(Egg Dropping Puzzle)

NO IMAGE

經典的動態規劃問題,題設是這樣的:
如果你有2顆雞蛋,和一棟36層高的樓,現在你想知道在哪一層樓之下,雞蛋不會被摔碎,應該如何用最少的測試次數對於任何答案樓層都能夠使問題得到解決。

  • 如果你從某一層樓扔下雞蛋,它沒有碎,則這個雞蛋你可以繼續用
  • 如果這個雞蛋摔碎了,則你可以用來測試的雞蛋減少一個
  • 所有雞蛋的質量相同(都會在同一樓層以上摔碎)
  • 對於一個雞蛋,如果其在樓層i扔下的時候摔碎了,對於任何不小於i的樓層,這個雞蛋都會被摔碎
  • 如果在樓層i扔下的時候沒有摔碎,則對於任何不大於i的樓層,這顆雞蛋也不會摔碎
  • 從第1層扔下,雞蛋不一定完好,從第36層扔下,雞蛋也不一定會摔碎。

實際上,我們的終極目的是要找出連續的兩層樓i,i 1在樓層i雞蛋沒有摔碎,在樓層i 1雞蛋碎了,問題的關鍵之處在於,測試之前,你並不知道雞蛋會在哪一層摔碎,你需要找到的是一種測試方案,這種測試方案,無論雞蛋會在哪層被摔碎,都至多只需要m次測試,在所有這些測試方案中,m的值最小。

對於只有1顆雞蛋的情況,我們別無選擇,只能從1樓開始,逐層向上測試,直到第i層雞蛋摔碎為止,這時我們知道,會讓雞蛋摔碎的樓層就是i(或者直到頂層,雞蛋也沒有被摔碎),其他的測試方案均不可行,因為如果第1次測試是在任何i>1的樓層扔下雞蛋,如果雞蛋碎了,你就無法確定,i-1層是否也會令雞蛋摔碎。所以對於1顆雞蛋而言,最壞的情況是使雞蛋摔碎的樓層數i>=36,此時,我們需要測試每個樓層,總共36次,才能找到最終結果,所以1顆雞蛋一定能解決36層樓問題的最少測試次數是36.

對於2個雞蛋,36層樓的情況,你可能會考慮先在第18層扔一顆,如果這顆碎了,則你從第1層,到第17層,依次用第2顆雞蛋測試,直到找出答案。如果第1顆雞蛋沒碎,則你依然可以用第1顆雞蛋在27層進行測試,如果碎了,在第19~26層,用第2顆雞蛋依次測試,如果沒碎,則用第1顆雞蛋在32層進行測試,……,如此進行(有點類似於二分查詢)。這個解決方案的最壞情況出現在結果是第17/18層時,此時,你需要測試18次才能找到最終答案,所以該方案,解決36層樓問題的測試次數是18.

相較於1顆雞蛋解決36層樓問題,測試次數實現了減半,但是18並不是確保解決2顆雞蛋,36層樓問題的最小值(實際的最小值是8).

我們可以將這樣的問題簡記為W(n,k),其中n代表可用於測試的雞蛋數,k代表被測試的樓層數。對於問題W(2,36)我們可以如此考慮,將第1顆雞蛋,在第i層扔下(i可以為1~k的任意值),如果碎了,則我們需要用第2顆雞蛋,解決從第1層到第i-1層樓的子問題W(1,i-1),如果這顆雞蛋沒碎,則我們需要用這兩顆雞蛋,解決從i 1層到第36層的子問題W(2,36-i),解決這兩個問題,可以分別得到一個嘗試次數p,q,我們取這兩個次數中的較大者(假設是p),與第1次在i層執行測試的這1次相加,則p 1就是第一次將雞蛋仍在i層來解決W(2,36)所需的最少測試次數次數ti。對於36層樓的問題,第一次,我們可以把雞蛋仍在36層中的任何一層,所以可以得到36中解決方案的測試次數T{t1,t2,t3,……,t36},在這些結果中,我們選取最小的ti,使得對於集合T中任意的值tj(1<=j<=36,j!=i),都有ti<=tj,則ti就是這個問題的答案。用公式來描述就是W(n,
k) = 1 min{max(W(n -1, x -1), W(n, k – x))}, x in {2, 3, ……,k},其中x是第一次的測試的樓層位置。

其中W(1,k) = k(相當於1顆雞蛋測試k層樓問題),W(0,k) = 0,W(n, 0) = 0

所以在計算W(2,36)之前,我們需先計算出所有W(1,0),……,W(1,36),W(2,0),……,W(2,35)這些的值,可以用遞推的方法實現,程式碼如下:

unsigned int DroppingEggsPuzzle(unsigned int eggs, unsigned int floors)
{
unsigned int i, j, k, t, max;
unsigned int temp[eggs   1][floors   1];
for(i = 0; i < floors   1;   i)
{
temp[0][i] = 0;
temp[1][i] = i;
}
for(i = 2; i < eggs   1;   i)
{
temp[i][0] = 0;
temp[i][1] = 1;
}
for(i = 2; i < eggs   1;   i)
{
for(j = 2; j < floors   1;   j)
{
for(k = 1, max = UINT_MAX; k < j;   k)
{
t = temp[i][j - k] > temp[i - 1][k -1] ?  temp[i][j - k] : temp[i - 1][k -1];
if(max > t)
{
max = t;
}
}
temp[i][j] = max   1;
}
}
return temp[eggs][floors];
}

該演算法的空間複雜度是O(nk),時間複雜度是O(nk^2),對於規模較大的問題,無論是空間還是時間複雜度都很可觀。

這個演算法可以計算出W(2,36)問題的最少測試次數是8,但是卻不能給出用2顆雞蛋解決36層樓問題的具體方案,這裡我就給出一個測試方案:

  • 用第一顆雞蛋分別在8,15,21,26,30,33,35層進行測試
  • 如果雞蛋在某一層碎了(例如26層),則在前一測試點由下到上依次測試,例如(22,23,24,25),直到找到滿足條件的樓層為止
  • 如果雞蛋在第35層的測試中也沒碎,則用該雞蛋在第36層再測試一次

該方案可以保證,無論滿足條件的樓層是多少,都可以在最多8次測試之後找到答案,例如目標樓層為28時,該方案的測試順序為8,15,21,26,30,27,28,總共測試7次,有興趣的讀者可以嘗試一下其他情況。

該方案解決W(2,36)問題比較優雅,但是卻暗藏一個很大的玄機,那就是一般我們見到的這個問題的題面,往往是W(2,15),W(2,36),不知道讀者考慮過沒有,為什麼非讓我們計算2顆雞蛋測試36層樓的情況,而不是35層或者37層?下面是用之前的演算法解決W(4,50)問題的遞推結果表格(其中,行代表樓層數1~50,列代表雞蛋數1~4),我們會發現,W(2,36)=8,W(2,37) = 9,那麼是不是用2顆雞蛋測試8次,最多隻能解決36層樓問題,對於37層就無能為力了呢?

 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950
1223334444555556666667777777888888889999999991010101010
12233334444444555555555556666666666666666777777777
12233334444444455555555555555566666666666666666666

這裡引出了一個問題:n個雞蛋,測試m次(簡記為D(n,m)),最大可以解決幾層樓的問題,通過對遞推結果表格的觀察,我們可以得到如下結論

  1. D(1,m) = m
  2. D(n,n) = 2^n – 1
  3. D(n,m){m <= n} = D(m,m)

對於第二點,以D(4,4)為例,我們第1次在8樓扔下雞蛋,如果碎了,則第二次在4樓扔下雞蛋,否則在12樓扔下雞蛋,對於在4樓扔下雞蛋的情況,之後可以分別在2樓或者6樓扔下雞蛋,如此進行,就可以找到答案樓層,方法與二分查詢一樣。例如答案樓層是5的情況,測試序列為8,4,6,5。

對於第三點,如果有5個雞蛋讓你測試3次,即使三次測試雞蛋都碎了,剩下的2個雞蛋也派不上用場,所以D(5,3) = D(3,3)

發現這些關係之後,我們似乎找到解決n個雞蛋測試m次最大能夠解決樓層數的方法。對於D(n,m){n < m}而言,對於其能夠測試的最大樓層數k,我們可以構造這樣的場景,將第一顆雞蛋仍在樓層i,使得第i 1層到第k層是D(n,m-1)可以解決的最大樓層數,第1層到第i – 1層是D(n-1,m-1)可以解決的最大樓層數,由此得到遞推關係D(n,m) = D(n -1,m-1) 1 D(n,m-1),然後對D(n,m-1),D(n-1,m-1)再按照上述公式分解,直到得出剛才所列的三種可計算情況(n
= 1,或者m <= n)為止,再進行回溯累加,就可以得到D(n,m)的值,程式碼如下:

unsigned int DroppingMax(unsigned int eggs, unsigned times)
{
if(eggs == 1)
{
return times;
}
if(eggs >= times)
{
return (unsigned int)pow(2, times) - 1;
}
return DroppingMax(eggs, times -1)   DroppingMax(eggs -1, times - 1)   1;
}

根據此演算法,我們可以得出D(2,5)=15,D(2,8)=36,也就是說,2個雞蛋測試5次最多可以解決15層樓的問題,測試8次最多可以解決36層樓的問題。可見,出這個題的人並不是隨便找兩個樓層數陪咱們玩玩,而是對此問題認真研讀後的結果。有了此利器之後,我們解決扔雞蛋問題的的方法將得到大幅簡化,對於n個雞蛋解決k層樓的問題我們只需找到這樣的值m,使得D(n,m-1)<k<=D(n,m),程式碼如下

unsigned int DroppingEggsPuzzle2(unsigned int eggs, unsigned int floors)
{
unsigned int times = 1;
while(DroppingMax(eggs, times) < floors)
{
times;
}
return times;
}

該演算法的時間和空間複雜度不太好分析,但都要好於傳統的DP演算法,有興趣的讀者可以推敲一下,在我的機器上測試10個雞蛋,5000層樓的情況,第二個方法比第一個要快10萬倍!注意到演算法2也是一個動態規劃問題,所以可以用一個n*m的矩陣來儲存計算過程中的中間結果,演算法的效率還可以得到很大提升!

不管是演算法1,還是演算法2,都沒有給出用n個雞蛋如何通過m次測試,解決k層樓的問題,對此我根據演算法2給出一個思路。對於滿足條件D(n,m-1)<k<=D(n,m),的測試次數m,將D(n,m),和D(n,m-1)按照D(n,m) = D(n -1,m-1) 1 D(n,m-1) 的方式展開,這裡展開過程中要嚴格按照公式中各迭代的順序,也就是說先是D(n-1,m-1),然後是1,然後是D(n,m-1),順序不能亂,然後比較兩結果,例如

D(3,5) = D(1,3) 1[2] D(1,2) 1[3] D(2,2) 1[1] D(1,2) 1[3] D(2,2) 1[2] D(3,3)
D(3,4) =                                     D(1,2) 1[2] D(2,2) 1[1] D(3,3)

這其中每個單獨的1,都代表一次獨立測試,這些1後面中的中括號代表其是第幾次獨立測試,與其從公式中分離出來的時機相關,最早分離出來的1,其值就是[1],第二次分離出來的1,其值就是[2],這些1的目的就是把k層樓分解為若干個可直接計算的子部分。我們取出兩者不同的部分D(1,3) 1[2] D(1,2) 1[3] D(2,2) 1[1],這部分表示通過增加了一次測試,我們所獲得的額外的探測能力,通過改造這部,使得這部分的和等於k-D(n,m-1),然後將改裝部分與兩者的相同部分結合,形成新的結果,這些結果從前到後,對應著樓層從下到上的測試方案

上例中我們知道D(3,4)=14, D(3,5)=25,對於14 < k <= 25,我們用k減去14得到需要構造的值,儘量保留右側的算式,只改變最左側的算式,例如對於k = 15,不同部分可以用1替換,對於k = 16可以用D(1,1) 1替換,對於k = 18可以用D(2,2) 1替換,對於k = 21可以用D(1,2) 1 D(2,2) 1替換。以21為例,我們將改造結果和D(3,4),D(3,5)的相同部分結合,形成

D(1,2) 1[2] D(2,2) 1[1] D(1,2) 1[3] D(2,2) 1[2] D(3,3)
下面用圖說明如何用3個雞蛋測試5次,解決21層樓問題,這裡的規律是,對於獨立的測試而言,如果測試摔碎,則向低樓層執行後續的測試,如果沒有摔碎,則向高樓層執行後續的測試,其中的括號表示該測試執行的樓層/樓層區間。

實際上,對於D(n,m-1)<k<D(n,m)的情況,滿足條件的測試方案不止一種。
後記:

  • 這是國外牛人的一篇文章,對於扔雞蛋問題的理論分析,讓人歎服,有興趣的讀者可以看一看,進一步深挖這個問題
  • 對於演算法2的幾個前提,我沒能給出數學上的證明,那篇國外大牛的文章裡面有涉及,不過那篇文章太長了,我沒有看完。
  • 根據D(n,m)的遞推關係,也許可以得到這個數列的通項公式。
  • 扔雞蛋問題,與其說是一個動態規劃問題,不如說是一個在特定場景下的數學問題,程式在該問題中更多價值在於驗證結論。