基本介紹
- 中文名：扔雞蛋問題
- 外文名：The egg problem
- 所屬學科：計算機算法
- 求解方法：動態規劃
問題描述,分析求解,結果討論,
問題描述
有一幢樓房高 M 層。某人準備了 N 個雞蛋供試驗。他想知道雞蛋從幾層扔下不會摔碎，並確定出最高安全樓層。試驗過程中，雞蛋沒有摔碎則可以繼續使用，摔碎了則需要換一個雞蛋繼續試驗。為保證試驗成功，此人要設計一個程式，以最小化最壞情況的試驗次數 F(M,N). 作為一個數學抽象，本問題採用一些理想化假設：所有雞蛋抗摔能力相同，不計重複墜地的累積損傷，且忽略試驗結果的偶然性。試驗成功的標準是在 N 個雞蛋用完之前，精確確定最高安全樓層是哪一層。允許有雞蛋剩餘。
分析求解
如果只有 N = 1 個雞蛋供試驗，則為了保證試驗成功，只能從一層開始逐層往上試驗。這相當於採用順序查找算法，最壞試驗次數 F(M, 1) = M. 如果一層就碎了，則最高安全樓層為 0. 如果 M 層還不碎，則最高安全樓層為 M.
如果有 N = ∞ 個雞蛋供試驗，則完全不用擔心雞蛋摔碎的問題。此時可以採用二分查找算法，最壞試驗次數 F(M, ∞) = ceil [log2(M+1)]，其中 ceil 表示向上取整。因為最高安全樓層有 0 到 M 共 M+1 種可能，而 F(M, ∞) 次試驗最多有 2 種可能。令 2 ≥ M+1 即得到上述結果。
有趣的是 N ≥ 2 且有限的情況。採用動態規劃思想，枚舉第一個雞蛋扔在第 k = 1~M 層的全部 M 種情況有
如果第一個雞蛋沒有碎，則待試驗樓層的範圍縮小為第 k+1 到 M 層，剩餘 M-k 個樓層和 N 個雞蛋，最多還需試驗 F(M-k, N) 次。如果第一個雞蛋碎了，則待試驗樓層的範圍縮小為第 1 到 k-1 層，剩餘 k-1 個樓層和 N-1 個雞蛋，最多還需試驗 F(k-1, N-1) 次。取兩種情況中的最壞情況，枚舉 k = 1~M 對其最小化，即得上式。遞推的邊界條件是 F(M, 1) = M 和 F(0, N) = 0.
結果討論
按照上述動態規划算法，求出 F(M,N) 的結果如下表。對於每個固定的樓層數 M，雞蛋數 N 多到一定程度就足夠了，最多試驗次數 F(M,N) = ceil [log2(M+1)] 會等於二分查找的結果。對於雞蛋數 N 固定的情況，則在 M→∞ 極限下有 F(M,N) = O(M). 有兩個雞蛋和只有一個雞蛋相比，試驗次數已經由 M 減少為 √M 量級。
F(M, N) \ M = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
N = 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
N = 2 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 |
N ≥ 3 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
當 M 較大時，達到二分查找效率所需的雞蛋數 N 會比較多。例如 M = 100 時，F(M, 1) = 100，F(M, 2) = 14，F(M, 3) = 9，F(M, 4) = 8，F(M, N ≥ 5) = 7. 故最多需要 5 個雞蛋，即可在最壞 7 次試驗之內確定 100 層樓房的最高安全樓層。節省了兩個雞蛋是因為 F(25, 3) = 5，而 F(14, 3) = F(10, 2) = 4. 故先用兩個雞蛋二分查找把樓層範圍減少為 25 個樓層以後，第三個雞蛋應扔在第 11 層。如果碎了，剩下 10 個樓層和 2 個雞蛋；如果沒碎，剩下 12 至 25 共 14 個樓層和 3 個雞蛋，都能在最多 4 次試驗內確定最高安全樓層。第三次扔在 11 層比中間樓層（12 或 13 層）略低一點，以在剩餘雞蛋和排除樓層之間達到最好的平衡。F(14, 3) 和 F(10, 2) 的 4 次試驗的執行方案可繼續用遞推式追溯，直至構建出整個策略樹。
