双蛋问题

✍ dations ◷ 2025-08-16 15:53:20 #物理学专题,物理科学,物理学实验

双蛋问题(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;}}

参见

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


相关

  • 2019冠状病毒病英国疫情,介绍在2019新型冠状病毒疫情中,在英国及其属地发生的情况。2020年1月, 希思罗机场加强了对每周从武汉接收的三班直达航班的监控;每一个人都将要接受海关
  • 十br /一第八第十埃及第十一王朝是古埃及历史上第一中间时期的一个王朝,其首都位于底比斯。
  • 地方性公民投票中华民国地方性公民投票是依照《公民投票法》,在中华民国各直辖市、县、市为范围实施的公民投票。投票以普通、平等、直接、无记名等方式进行。截至2020年03月为止,经由中华民
  • 氯化钇氯化钇是一种无机化合物,化学式为YCl3,易溶于水。固体氯化钇有和AlCl3一样的结构。无水氯化钇通常由氯化铵和水合氯化钇、氧化钇、或氯氧化钇反应首先得到(NH4)2:然后将(NH4)2
  • 双电层电容器双电层电容器(EDLC)有时也称为电双层电容器,或超级电容器,是拥有高能量密度的电化学电容器,比传统的电解电容容量高上数百倍至千倍不等。一个标准电池大小的电解电容电容为几十
  • 番长番长(ばんちょう),日语用语,原指日本律令官制的官职之一,在20世纪时、常用于日本不良少年组织对其领导者的称呼,而女性则称为“女番 / スケ番”,团体为小学生以下者称“ガキ大将”(
  • 台北州立台北第二中学校台湾日治时期的台北州立台北第二中学校于1922年(大正11年)5月8日以地方人士之倡议设立,设校于万华的艋舺清水祖师庙(台北市万华区康定路),1925年(大正14年)于台北市中正区创建校舍,翌
  • 托尼·朱特托尼·罗伯特·朱特(英语:Tony Robert Judt,又译为东尼·贾德,1948年1月2日-2010年8月6日),英国历史学家、作家、大学教授、社会民主主义者。他以其对欧洲历史的贡献而闻名,是纽约大
  • 杨得礼杨得礼,字嘉甫,湖广应城人,明朝政治人物、进士出身。洪武十八年,登进士,授户部主事,后调工部营缮郎中,迁陕西参议,升任参政,死于任内。有元孙杨绍芳、杨继方。
  • 企业号航天飞机企业号航天飞机(Space Shuttle Enterprise,NASA内部编号OV-101),又译为进取号,是NASA打造的第一架航天飞机。“企业号航天飞机”实际上只是一个的航天的测试平台,没有引擎等相关部