雙蛋問題(The Two Eggs Problem)是一個經典的算法問題,它經常被描述為「給你兩個相同的異常堅硬的雞蛋,通過在一棟100層的樓的不同層扔下雞蛋進行實驗,試驗出可以摔碎該雞蛋的最高樓層(臨界樓層)。已知未碎的雞蛋可以重複使用。求最少的實驗次數n,使得在n次實驗後,一定能判斷出該臨界樓層。」
該問題可以擴展為這樣一類問題: 在N個雞蛋,k層樓的條件下,找到一個最小的m,使得存在一種方案,在m次實驗以後,一定能找到雞蛋的臨界樓層。
為了更加精確地思考問題,該問題中必須滿足以下的條件:
- 如果雞蛋在某一層沒有碎,它不會在任何更低層的破碎。
- 如果雞蛋在某一層碎了,它在更高層上一定會碎。
- 雞蛋可能在一樓摔破,也可能在最高層還不摔破。
此時,你有2個雞蛋,樓高100層。我們可以先思考有1個雞蛋和有無數個雞蛋的情況[1]。
此時,由於只有一個雞蛋,所以一旦破碎,那麼就無法繼續進行試驗,我們只能從第1層開始,一層一層地實驗。在這種情況下最多需要99次實驗。
容易的解決方案是二分法,
,所以如果我們有無數個雞蛋,我們最多只需要7次就可以試驗出。比如,先在64樓扔一次雞蛋,如果碎了,那就到32層扔第二次,如果第二次扔雞蛋又碎了,再到16層去扔第三次,如果這次沒有碎,那你可以再到第24層去扔第四次,又沒碎,那就去28層扔第五次,還是沒有碎,再到30層扔第六次,這次又碎了,再到29層扔第七次,第七次碎了,那麼臨界樓層就是第28層,第七次沒碎,臨界樓層就是第29層。所以無數個雞蛋最多只需要7次就可以實驗。
藉助於二分法提供的分組思想,我們可以嘗試將100平均分成10組,用第一個雞蛋在每組最後一層進行實驗,這樣可以實驗出臨界樓層在哪一組。然後再用第二個雞蛋從該組第一層依次實驗。這種方案的最壞情況是19次。
我們發現,如果19層是臨界樓層,只需要實驗11次,而如果臨界層是99層,就需要實驗19次。因此我們是否可以將19次平均到11次裡一部分?為此,有以下方案,第一組
人,第二組
人,第三組
人,……第x組1人,考慮到
,解得
,所以
時,最多需要14次便可以找出臨界樓層。
下面是雙蛋問題的幾個推廣問題[2][3]。
類似於之前的方法,只需要
即可,可以求出
(參見取整函數、高斯符號)
讓我們定義一個函數
,表示有
個雞蛋,通過
次實驗就一定能夠判斷出臨界樓層的最大樓層。 如果雞蛋打破,我們將能夠將臨界樓層範圍縮小到f(d−1,n−1)層;否則我們將能夠把範圍縮小到 f(d-1,n)層。
因此,
。這只是一個遞歸關係,而我們必須找到一個函數 f(d,n)。
因此,我們將定義一個輔助函數
根據我們的第一個方程
函數
可以寫成
(參見二項式係數)
但是我們有一個問題:根據之前的關係
和
,對於任何
,
以及
都是
。然而,在
時會發生矛盾,因為
,但對於每一個
,
應該是
!
我們可以通過重定義
修復這個問題如下:
遞歸是仍然有效。
現在,展開f(d,n),我們可以把它寫成
我們知道
,因此
我們也知道
因此,
最後,
我們知道
是所有最少實驗次數為
的總樓層數中最大的一個,我們只要找到一個
滿足以下條件即可:
使用我們最後的公式,
讓我們來試驗一下:
因此有
所以我們如果有三個雞蛋,可以保證在9次實驗之內找到臨界樓層。
除了解析法之外,最常見的方法是遞歸法。
想像以下情況:n個雞蛋,k層樓,然後你把雞蛋在連續的h層中的第i層進行試驗。
如果雞蛋打破:這個問題會減少為n-1雞蛋和 i-1個剩餘樓層的問題;如果不打破:這個問題會減少為n雞蛋和h-i個剩餘樓層的問題。
現在我們可以定義一個函數
計算所需的最小實驗次數:
我們可以編寫上述結果為確定找到下面的遞歸
:
以下代碼由C++編寫
#include <iostream>
#include <iostream>
#include <limits.h>
using namespace std;
//Compares 2 values and returns the bigger one
int max(int a,int b) {
int ans=(a>b)?a:b;
return ans;
}
//Compares 2 values and returns the smaller one
int min(int a,int b){
int ans=(a<b)?a:b;
return ans;
}
int egg(int n,int h){
//Basis case
if(n==1) return h;
if(h==0) return 0;
if(h==1) return 1;
int minimum=INT_MAX;
//Recursion to find egg(n,k). The loop iterates i: 1,2,3,...h
for(int x=1;x<=h;x++) minimum=min(minimum,(1+max(egg(n,h-x),egg(n-1,x-1))));
return minimum;
}
int main()
{
int e;//Number of eggs
int f;//Number of floors
cout<<"Egg dropping puzzle\n\nNumber of eggs:";
cin>>e;
cout<<"\nNumber of floors:";
cin>>f;
cout<<"\nNumber of drops in the worst case:"<<egg(e,f);
return 0;
}
}
- 雙蛋問題的另一個遞歸程序(頁面存檔備份,存於互聯網檔案館)
- 李永樂老師(頁面存檔備份,存於互聯網檔案館)
- 相關動態規劃問題(頁面存檔備份,存於互聯網檔案館)