双蛋问题

双蛋问题（The Two Eggs Problem）是一个经典的算法问题，它经常被描述为“给你两个相同的异常坚硬的鸡蛋，通过在一栋100层的楼的不同层扔下鸡蛋进行实验，试验出可以摔碎该鸡蛋的最高楼层（临界楼层）。已知未碎的鸡蛋可以重复使用。求最少的实验次数n,使得在n次实验后，一定能判断出该临界楼层。”

该问题可以扩展为这样一类问题： 在N个鸡蛋，k层楼的条件下，找到一个最小的m，使得存在一种方案，在m次实验以后，一定能找到鸡蛋的临界楼层。

为了更加精确地思考问题，该问题中必须满足以下的条件：

此时，你有2个鸡蛋，楼高100层。我们可以先思考有1个鸡蛋和有无数个鸡蛋的情况。

此时，由于只有一个鸡蛋，所以一旦破碎，那么就无法继续进行试验，我们只能从第1层开始，一层一层地实验。在这种情况下最多需要99次实验。

容易的解决方案是二分法， ,所以如果我们有无数个鸡蛋，我们最多只需要7次就可以试验出。比如，先在64楼扔一次鸡蛋，如果碎了，那就到32层扔第二次，如果第二次扔鸡蛋又碎了，再到16层去扔第三次，如果这次没有碎，那你可以再到第24层去扔第四次，又没碎，那就去28层扔第五次，还是没有碎，再到30层扔第六次，这次又碎了，再到29层扔第七次，第七次碎了，那么临界楼层就是第28层，第七次没碎，临界楼层就是第29层。所以无数个鸡蛋最多只需要7次就可以实验。

借助于二分法提供的分组思想，我们可以尝试将100平均分成10组，用第一个鸡蛋在每组最后一层进行实验，这样可以实验出临界楼层在哪一组。然后再用第二个鸡蛋从该组第一层依次实验。这种方案的最坏情况是19次。

我们发现，如果19层是临界楼层，只需要实验11次，而如果临界层是99层，就需要实验19次。因此我们是否可以将19次平均到11次里一部分？为此，有以下方案，第一组${\displaystyle x}$人，第二组${\displaystyle (x-<!--\; -\; -->1)}$人,第三组${\displaystyle (x-<!--\; -\; -->2)}$人,……第x组1人，考虑到${\displaystyle x+(x-<!--\; -\; -->1)+(x-<!--\; -\; -->2)+\cdots <!--\; \cdots \; -->+3+2+1=\frac{x(x+1)}{2}>100}$，解得${\displaystyle x>13.65}$，所以${\displaystyle x=14}$时，最多需要14次便可以找出临界楼层。

下面是双蛋问题的几个推广问题。

类似于之前的方法，只需要${\displaystyle x+(x-<!--\; -\; -->1)+(x-<!--\; -\; -->2)+\cdots <!--\; \cdots \; -->+3+2+1=\frac{x(x+1)}{2}>k}$即可，可以求出${\displaystyle k=\lceil \frac{-<!--\; -\; -->1+\sqrt{1+8k}}{2}\rceil }$（参见取整函数、高斯符号）

让我们定义一个函数${\displaystyle f(d,n)}$,表示有${\displaystyle n}$个鸡蛋，通过${\displaystyle d}$次实验就一定能够判断出临界楼层的最大楼层。 如果鸡蛋打破,我们将能够将临界楼层范围缩小到f(d−1,n−1)层；否则我们将能够把范围缩小到 f(d-1,n)层。

因此，${\displaystyle f(d,n)=1+f(d-<!--\; -\; -->1,n-<!--\; -\; -->1)+f(d-<!--\; -\; -->1,n)}$。这只是一个递归关系，而我们必须找到一个函数 f(d,n)。

因此,我们将定义一个辅助函数${\displaystyle g(d,n):g(d,n)=f(d,n+1)-<!--\; -\; -->f(d,n)}$

根据我们的第一个方程

函数${\displaystyle g(d,n)}$可以写成${\displaystyle g(d,n)=(\genfrac{}{}{0ex}{}{d}{n})}$（参见二项式系数）

但是我们有一个问题：根据之前的关系${\displaystyle f}$和${\displaystyle g}$，对于任何${\displaystyle n}$，${\displaystyle f(0,n)}$以及${\displaystyle g(0,n)}$都是${\displaystyle 0}$。然而,在${\displaystyle n=0}$时会发生矛盾，因为${\displaystyle g(0,0)=(\genfrac{}{}{0ex}{}{0}{0})=1}$，但对于每一个${\displaystyle n}$，${\displaystyle g(0,n)}$应该是${\displaystyle 0}$!

我们可以通过重定义${\displaystyle g(d,n)}$修复这个问题如下：

${\displaystyle g(d,n)=(\genfrac{}{}{0ex}{}{d}{n+1})}$

递归是仍然有效。

现在，展开f(d,n),我们可以把它写成

我们知道${\displaystyle f(d,0)=0}$,因此

${\displaystyle f(d,n)=g(d,n-<!--\; -\; -->1)+g(d,n-<!--\; -\; -->2)+\cdots <!--\; \cdots \; -->+g(d,0)}$

我们也知道

${\displaystyle g(d,n)=(\genfrac{}{}{0ex}{}{d}{n+1})}$

因此，

${\displaystyle g(d,n-<!--\; -\; -->1)+g(d,n-<!--\; -\; -->2)+\cdots <!--\; \cdots \; -->+g(d,0)=(\genfrac{}{}{0ex}{}{d}{n})+(\genfrac{}{}{0ex}{}{d}{n-<!--\; -\; -->1})+\cdots <!--\; \cdots \; -->+(\genfrac{}{}{0ex}{}{d}{1})}$

最后，

${\displaystyle f(d,n)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{d}{i})}$

我们知道${\displaystyle f(d,n)}$是所有最少实验次数为${\displaystyle d}$的总楼层数中最大的一个，我们只要找到一个${\displaystyle k}$满足以下条件即可：

${\displaystyle f(d,n)⩾<!--\; ⩾\; -->k}$

使用我们最后的公式,

${\displaystyle \underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{d}{i})⩾<!--\; ⩾\; -->k}$

让我们来试验一下:

${\displaystyle f(t,3)=\underset{i=1}{\overset{3}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{d}{i})=\frac{t(t^2+5)}{6}}$

因此有${\displaystyle f(8,3)=92,f(9,3)=129}$

所以我们如果有三个鸡蛋，可以保证在9次实验之内找到临界楼层。

除了解析法之外，最常见的方法是递归法。

想象以下情况：n个鸡蛋，k层楼，然后你把鸡蛋在连续的h层中的第i层进行试验。

如果鸡蛋打破：这个问题会减少为n-1鸡蛋和 i-1个剩余楼层的问题；如果不打破：这个问题会减少为n鸡蛋和h-i个剩余楼层的问题。现在我们可以定义一个函数${\displaystyle W(n,h)}$计算所需的最小实验次数：

我们可以编写上述结果为确定找到下面的递归${\displaystyle W(n,h)}$:

以下代码由C++编写

${\displaystyle 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 oneint max(int a,int b) {    int ans=(a>b)?a:b;    return ans;}//Compares 2 values and returns the smaller oneint 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;}}