雙蛋問題

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

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

## 問題假設

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

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

## 解決方案

此時，你有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)))$$

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

## 參見

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