雙蛋問題

雙蛋問題（The Two Eggs Problem）是一個經典的算法問題，它經常被描述為「給你兩個相同的異常堅硬的雞蛋，通過在一棟100層的樓的不同層扔下雞蛋進行實驗，試驗出可以摔碎該雞蛋的最高樓層（臨界樓層）。已知未碎的雞蛋可以重複使用。求最少的實驗次數n,使得在n次實驗後，一定能判斷出該臨界樓層。」

該問題可以擴展為這樣一類問題： 在N個雞蛋，k層樓的條件下，找到一個最小的m，使得存在一種方案，在m次實驗以後，一定能找到雞蛋的臨界樓層。

問題假設

為了更加精確地思考問題，該問題中必須滿足以下的條件：

1. 如果雞蛋在某一層沒有碎,它不會在任何更低層的破碎。
2. 如果雞蛋在某一層碎了，它在更高層上一定會碎。
3. 雞蛋可能在一樓摔破，也可能在最高層還不摔破。

解決方案

此時，你有2個雞蛋，樓高100層。我們可以先思考有1個雞蛋和有無數個雞蛋的情況。

1個雞蛋

此時，由於只有一個雞蛋，所以一旦破碎，那麼就無法繼續進行試驗，我們只能從第1層開始，一層一層地實驗。在這種情況下最多需要99次實驗。

無數個雞蛋

容易的解決方案是二分法，$\log _{2}{100}\approx 6.644<7$ ,所以如果我們有無數個雞蛋，我們最多只需要7次就可以試驗出。比如，先在64樓扔一次雞蛋，如果碎了，那就到32層扔第二次，如果第二次扔雞蛋又碎了，再到16層去扔第三次，如果這次沒有碎，那你可以再到第24層去扔第四次，又沒碎，那就去28層扔第五次，還是沒有碎，再到30層扔第六次，這次又碎了，再到29層扔第七次，第七次碎了，那麼臨界樓層就是第28層，第七次沒碎，臨界樓層就是第29層。所以無數個雞蛋最多只需要7次就可以實驗。

兩個雞蛋

藉助於二分法提供的分組思想，我們可以嘗試將100平均分成10組，用第一個雞蛋在每組最後一層進行實驗，這樣可以實驗出臨界樓層在哪一組。然後再用第二個雞蛋從該組第一層依次實驗。這種方案的最壞情況是19次。

我們發現，如果19層是臨界樓層，只需要實驗11次，而如果臨界層是99層，就需要實驗19次。因此我們是否可以將19次平均到11次裡一部分？為此，有以下方案，第一組$x$人，第二組$(x-1)$人,第三組$(x-2)$人,……第x組1人，考慮到$x+(x-1)+(x-2)+\cdots +3+2+1={\frac {x(x+1)}{2}}>100$，解得$x>13.65$，所以$x=14$時，最多需要14次便可以找出臨界樓層。

推廣問題

下面是雙蛋問題的幾個推廣問題。

2個雞蛋，k層樓

類似於之前的方法，只需要$x+(x-1)+(x-2)+\cdots +3+2+1={\frac {x(x+1)}{2}}>k$即可，可以求出$k=\left\lceil {\frac {-1+{\sqrt {1+8k}}}{2}}\right\rceil$（參見取整函數、高斯符號）

n個雞蛋，k層樓

讓我們定義一個函數$f(d,n)$,表示有$n$個雞蛋，通過$d$次實驗就一定能夠判斷出臨界樓層的最大樓層。 如果雞蛋打破,我們將能夠將臨界樓層範圍縮小到f(d−1,n−1)層；否則我們將能夠把範圍縮小到 f(d-1,n)層。

因此，$f(d,n)=1+f(d-1,n-1)+f(d-1,n)$。這只是一個遞歸關係，而我們必須找到一個函數 f(d,n)。

因此,我們將定義一個輔助函數$g(d,n):g(d,n)=f(d,n+1)-f(d,n)$

根據我們的第一個方程

${\begin{aligned}g(d,n)&=f(d,n+1)-f(d,n)\\&=f(d-1,n+1)+f(d-1,n)+1-f(d-1,n)-f(d-1,n-1)-1\\&=[f(d-1,n+1)-f(d-1,n)]+[f(d-1,n)-f(d-1,n-1)]\\&=g(d-1,n)+g(d-1,n-1)\end{aligned}}$ 函數$g(d,n)$可以寫成$g(d,n)={\binom {d}{n}}$（參見二項式係數）

但是我們有一個問題：根據之前的關係$f$和$g$，對於任何$n$，$f(0,n)$以及$g(0,n)$都是$0$。然而,在$n=0$時會發生矛盾，因為$g(0,0)={\binom {0}{0}}=1$，但對於每一個$n$，$g(0,n)$應該是$0$!

我們可以通過重定義$g(d,n)$修復這個問題如下：

$g(d,n)={\binom {d}{n+1}}$

遞歸是仍然有效。

現在，展開f(d,n),我們可以把它寫成

${\begin{aligned}f(d,n)=&[f(d,n)-f(d,n-1)]\\+&[f(d,n-1)-f(d,n-2)]\\+&\cdots \\+&[f(d,1)-f(d,0)]\\+&f(d,0).\end{aligned}}$

我們知道$f(d,0)=0$,因此

$f(d,n)=g(d,n-1)+g(d,n-2)+\cdots +g(d,0)$

我們也知道

$g(d,n)={\binom {d}{n+1}}$

因此，

$g(d,n-1)+g(d,n-2)+\cdots +g(d,0)={\binom {d}{n}}+{\binom {d}{n-1}}+\cdots +{\binom {d}{1}}$

最後，

$f(d,n)=\sum _{i=1}^{n}{\binom {d}{i}}$

我們知道$f(d,n)$是所有最少實驗次數為$d$的總樓層數中最大的一個，我們只要找到一個$k$滿足以下條件即可：

$f(d,n)\geqslant k$

使用我們最後的公式,

$\sum _{i=1}^{n}{\binom {d}{i}}\geqslant k$

讓我們來試驗一下:

$f(t,3)=\sum _{i=1}^{3}{\binom {t}{i}}={\frac {t(t^{2}+5)}{6}}$

因此有$f(8,3)=92,f(9,3)=129$

所以我們如果有三個雞蛋，可以保證在9次實驗之內找到臨界樓層。

其他方法

除了解析法之外，最常見的方法是遞歸法。

想象以下情況：n個雞蛋，k層樓，然後你把雞蛋在連續的h層中的第i層進行試驗。

如果雞蛋打破：這個問題會減少為n-1雞蛋和 i-1個剩餘樓層的問題；如果不打破：這個問題會減少為n雞蛋和h-i個剩餘樓層的問題。 現在我們可以定義一個函數$W(n,h)$計算所需的最小實驗次數：

我們可以編寫上述結果為確定找到下面的遞歸$W(n,h)$:

以下代碼由C++編寫

$W(n,h)=1+min(max(W(n-1,i-1),W(n,h-i)))$

#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;
}
}

參見

• 遞歸
• 二項式係數
• 取整函數、高斯符號

外部連結

1. 雙蛋問題的另一個遞歸程序（頁面存檔備份，存於網際網路檔案館）
2. 李永樂老師（頁面存檔備份，存於網際網路檔案館）
3. 相關動態規劃問題（頁面存檔備份，存於網際網路檔案館）