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

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

问题假设

编辑

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

  1. 如果鸡蛋在某一层没有碎,它不会在任何更低层的破碎。
  2. 如果鸡蛋在某一层碎了,它在更高层上一定会碎。
  3. 鸡蛋可能在一楼摔破,也可能在最高层还不摔破。

解决方案

编辑

此时,你有2个鸡蛋,楼高100层。我们可以先思考有1个鸡蛋和有无数个鸡蛋的情况[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]

2个鸡蛋,k层楼

编辑

类似于之前的方法,只需要 即可,可以求出 (参见取整函数高斯符号

n个鸡蛋,k层楼

编辑

让我们定义一个函数 ,表示有 个鸡蛋,通过 次实验就一定能够判断出临界楼层的最大楼层。 如果鸡蛋打破,我们将能够将临界楼层范围缩小到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;
}
}

参见

编辑


参考资料

编辑
  1. ^ The Two Eggs Problem. [2020-06-20]. (原始内容存档于2020-08-19). 
  2. ^ Egg Dropping. [2020-06-20]. (原始内容存档于2020-06-23). 
  3. ^ The egg problem. [2020-06-20]. (原始内容存档于2020-03-12). 

外部链接

编辑
  1. 双蛋问题的另一个递归程序页面存档备份,存于互联网档案馆
  2. 李永乐老师页面存档备份,存于互联网档案馆
  3. 相关动态规划问题页面存档备份,存于互联网档案馆