双蛋问题

✍ dations ◷ 2025-10-22 12:34:17 #物理学专题,物理科学,物理学实验

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

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

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

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

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

容易的解决方案是二分法, log 2 100 6.644 < 7 {\displaystyle \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 {\displaystyle x} 人,第二组 ( x 1 ) {\displaystyle (x-1)} 人,第三组 ( x 2 ) {\displaystyle (x-2)} 人,……第x组1人,考虑到 x + ( x 1 ) + ( x 2 ) + + 3 + 2 + 1 = x ( x + 1 ) 2 > 100 {\displaystyle x+(x-1)+(x-2)+\cdots +3+2+1={\frac {x(x+1)}{2}}>100} ,解得 x > 13.65 {\displaystyle x>13.65} ,所以 x = 14 {\displaystyle x=14} 时,最多需要14次便可以找出临界楼层。

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

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

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

因此, f ( d , n ) = 1 + 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)。

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

根据我们的第一个方程

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 = + = g ( d 1 , n ) + g ( d 1 , n 1 ) {\displaystyle {\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\\&=+\\&=g(d-1,n)+g(d-1,n-1)\end{aligned}}} 函数 g ( d , n ) {\displaystyle g(d,n)} 可以写成 g ( d , n ) = ( d n ) {\displaystyle g(d,n)={\binom {d}{n}}} (参见二项式系数)

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

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

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

递归是仍然有效。

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

f ( d , n ) = + + + + f ( d , 0 ) . {\displaystyle {\begin{aligned}f(d,n)=&\\+&\\+&\cdots \\+&\\+&f(d,0).\end{aligned}}}

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

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

我们也知道

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


因此,

g ( d , n 1 ) + g ( d , n 2 ) + + g ( d , 0 ) = ( d n ) + ( d n 1 ) + + ( d 1 ) {\displaystyle 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 ) = i = 1 n ( d i ) {\displaystyle f(d,n)=\sum _{i=1}^{n}{\binom {d}{i}}}

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

f ( d , n ) k {\displaystyle f(d,n)\geqslant k}

使用我们最后的公式,

i = 1 n ( d i ) k {\displaystyle \sum _{i=1}^{n}{\binom {d}{i}}\geqslant k}

让我们来试验一下:

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

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

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

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

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

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

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

以下代码由C++编写

W ( n , h ) = 1 + m i n ( m a x ( W ( n 1 , i 1 ) , W ( n , h i ) ) ) {\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;}}

参见

  • 递归
  • 二项式系数
  • 取整函数、高斯符号


相关

  • 阿米塔布·巴沙坎阿米塔·巴强(英语:Amitabh Bachchan;.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gent
  • 己型肝炎己型肝炎又称F型肝炎(Hepatitis F),1994年由Deka等人报告提出。当时认为是非甲、非乙、非丙、非戊型的新型肝炎。后已确认为一种遗传变异的乙肝病毒。
  • 补体膜攻击复合物膜攻击复合物(MAC),是一种通常生成于致病细菌表面的结构。人体补体系统的替代补体途径、经典补体途径、凝集素途径均可产生这种复合物。该复合物是免疫系统的效应蛋白之一,它可
  • ɒ̈开央圆唇元音是一个用于一些口语的元音。由于国际音标中并没有特别用来标注与两个元音之间的符号,故在一般情况下仅使用⟨ɒ⟩来表示。若欲更清楚地描述这个元音,可以使用变音
  • 数理精蕴《御制数理精蕴》,简称《数理精蕴》,清朝康熙皇帝时期成的一本关于数学的书籍。康熙在位时既倡导西算,也重视中算。晚年他命陈厚耀、何国宗、明安图等人编纂天文算法书籍,包括《
  • 索普威思·骆驼式战斗机索普威思·骆驼式战斗机(Sopwith Camel)是英国第一次世界大战期间于1917年在西线引入的单座双翼战斗机,由索普威思飞机公司开发,是同公司的早期小狗式战斗机后继机型。索普威思
  • 二氯化钨二氯化钨是一种无机化合物,化学式为W6Cl12。它是八面体的高分子簇合物。它可溶于浓盐酸,生成(H3O)2(H2O),加热这种水合物会得到黄棕色的W6Cl12。它的结构和二氯化钼类似。二氯
  • 焦磷酸钙焦磷酸钙,化学式Ca2P2O7。焦磷酸钙是一种白色粉末,不溶于水和醇,溶于稀盐酸和硝酸,水悬浮液呈酸性。根据温度不同,可有三种不同的晶型:α型(1210 °C)、β型(750~900 °C)和γ型(530~75
  • 崔白崔白(生卒年不详),字子西,活跃于十一世纪,安徽凤阳人。北宋著名画家。仁宗时入画院,至神宗时辞去职务。擅长道释、山水、花木、鸟兽画,尤其是擅长花鸟写生,工花翎羽毛,重视勾勒填彩,笔
  • 虱目鱼肚粥虱目鱼肚粥,也称为虱目鱼粥,是台湾在台南地区盛行的一种小吃,为当地传统的早点。通常讲究的店家会使用虱目鱼骨来熬煮高汤,再加上盐来调味就是现成的高汤,取部分高汤来熬煮鱼肚与