NO IMAGE

文章轉自:Acm之家 http://www.acmerblog.com/egg-dropping-puzzle-5591.html

據說這是一道google的面試題. 看似是一個智力題,實際是程式設計題。

兩個軟硬程度一樣但未知的雞蛋,它們有可能都在一樓就摔碎,也可能從一百層樓摔下來沒事。現有座36層的建築,要你用這兩個雞蛋確定哪一層是雞蛋可以安全落下的最高位置,可以摔碎兩個雞蛋,要求用最少的測試次數。

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

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

為什麼是兩個雞蛋呢?如果只有一個雞蛋,我們只能從下往上一層一層的測試。對於2個雞蛋,比較容易想到的就是使用二分的方法,現在18層測試,如果這顆碎了,則你從第1層,到第17層,依次用第2顆雞蛋測試。否則繼續用兩個雞蛋測試上半部分的樓層,最多需要18次測試,減少了一半。看似是個不錯的方法,可惜正確答案是8次。

其實,對於任何連續的M層,這M層在下面或在下面,對於這M層來說需要的測試次數都沒有影響。因此,可以把這個問題一般化,考慮n個雞蛋 k層樓,記為E(n,k)。解決的辦法是試著從每一層掉落一個雞蛋(從1到k)並遞迴計算需要在最壞的情況下需要的最小測試次數。考慮用程式來窮舉所有情況找到答案。

1) 最優子結構

當我們從一個樓層x扔下雞蛋時,有可能出現兩種情況(1)雞蛋破(2)雞蛋不破。

1)雞蛋破,那麼我們只需要用剩下的雞蛋測試 x層以下的樓層; 所以問題簡化為x-1層和n-1個雞蛋
2)如果雞蛋沒有破,那麼我們只需要檢查比x較高的樓層; 所以問題簡化為 k-x 和n個雞蛋。

最優子結構可以表示為:

1 k
==> 樓層數
2 n
==> 雞蛋數
3   eggDrop(n,
k) ==>最少需要的測試次數(考慮所有情況)
4   eggDrop(n,
k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)):
5                  x
屬於 {1, 2, ..., k}}

下面用遞迴的方法解決這個問題:

01 #
include <stdio.h>
02 #
include <limits.h>
03  
04 int max(int a, int b)
return (a
> b)? a: b; }
05  
06 int eggDrop(int n, int k)
07 {
08     //
基本情況
09     if (k
== 1 || k == 0)
10         return k;
11  
12     //如果只有一個雞蛋,最壞的情況下需要k測試
13     if (n
== 1)
14         return k;
15  
16     int min
= INT_MAX, x, res;
17  
18     //
考慮從第1層到底k層扔下雞蛋的所有情況 的最小結果
19     for (x
= 1; x <= k; x++)
20     {
21         res
= max(eggDrop(n-1, x-1), eggDrop(n, k-x));
22         if (res
< min)
23             min
= res;
24     }
25     return min
+ 1;
26 }
27  
28 /*
測試 */
29 int main()
30 {
31     int n
= 2, k = 10;
32     printf ("\nMinimum
number of trials in worst case with %d eggs and "
33              "%d
floors is %d \n"
,
n, k, eggDrop(n, k));
34     return 0;
35 }

上面的程式問題是複雜度太大 O(2^k)。如果k=36的話,基本是跑不出結果。

重疊子問題

因為上面的程式重複計算了很多子問題。以E(2,4)為例:

01                          E(2,4)
02                            |                     
03           -------------------------------------
04           |            
|           |         |  
05           |            
|           |         |      
06       x=1/\         
x=2/\      x=3/ \    x=4/ \
07         
\           /  \       ....      ....
08        /   
\         /    \
09  E(1,0) 
E(2,3)     E(1,1)  E(2,2)
10           /\ 
/\...         /  \
11       x=1/ 
\               .....
12         /   
\
13      E(1,0) 
E(2,2)
14             /  
\
15             ......
16 對於2個雞蛋,4層樓
部分遞迴

因此完全可以用動態規劃解決。

01 #
include <stdio.h>
02 #
include <limits.h>
03 int max(int a, int b)
return (a
> b)? a: b; }
04 int eggDrop(int n, int k)
05 {
06     /*
eggFloor[i][j] 表示對於 i個雞蛋 j 層樓,需要的最少測試次數 */
07     int eggFloor[n+1][k+1];
08     int res;
09     int i,
j, x;
10     //
初始化
11     for (i
= 1; i <= n; i++)
12     {
13         eggFloor[i][1]
= 1;
14         eggFloor[i][0]
= 0;
15     }
16  
17     //只有一個雞蛋,沒得優化,需要j次
18     for (j
= 1; j <= k; j++)
19         eggFloor[1][j]
= j;
20  
21     //
最優子結構的遞推
22     for (i
= 2; i <= n; i++)
23     {
24         for (j
= 2; j <= k; j++)
25         {
26             eggFloor[i][j]
= INT_MAX;
27             for (x
= 1; x <= j; x++)
28             {
29                 res
= 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
30                 if (res
< eggFloor[i][j])
31                     eggFloor[i][j]
= res;
32             }
33         }
34     }
35     return eggFloor[n][k];
36 }
37  
38 /*
測試*/
39 int main()
40 {
41     int n
= 2, k = 36;
42     printf ("\nMinimum
number of trials in worst case with %d eggs and "
43              "%d
floors is %d \n"
,
n, k, eggDrop(n, k));
44     return 0;
45 }

參考:http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/