双蛋问题

✍ dations ◷ 2025-09-17 14:37:22 #物理学专题,物理科学,物理学实验

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

参见

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


相关

  • 字型字型或字模(英语:font;传统英式英语:fount)是指印刷行业中某一整套具有同样样式、字重和尺码的字形,例如一整套用于内文的宋体5号字、一整套用于标题的10号字就叫一套字型。电脑早
  • 格尔德·宾宁格尔德·宾宁(德语:Gerd Binnig,1947年7月20日-),德国物理学家,扫描隧道显微镜和原子力显微镜的发明者之一,1986年获得诺贝尔物理学奖。1947年,格尔德·宾宁出生在法兰克福,他回忆说:“
  • 解析数论解析数论(analytic number theory),为数论中的分支,它使用由数学分析中发展出的方法,作为工具,来解决数论中的问题。它首次出现在数学家狄利克雷在1837年导入狄利克雷L函数,来证明
  • 海事及水务局国务院中央军委测绘机构海事及水务局(葡萄牙语:Direcção dos Serviços de Assuntos Marítimos e de Água),前身为港务局,是澳门特别行政区的局级政府部门,负责行使海事当局权
  • 莉莉丝游戏莉莉丝游戏,全称上海莉莉丝网络科技有限公司,成立于2013年5月,是中国大陆一家以网络游戏为主的公司,因为开发《小冰冰传奇》(原“刀塔传奇”)而知名。
  • 艾字节艾字节或艾可萨字节(英语:Exabyte,缩写为EB),是一种信息计量单位,现今通常在标示网络硬盘总容量,或具有大容量的存储介质之存储容量时使用。据估算,2011年整个互联网的容量总和不超
  • 陈世杰 (篮球运动员)陈世杰(1984年9月24日-),台湾男子篮球运动员,绰号溪湖,曾效力于超级篮球联赛桃园璞园建筑篮球队及中国男子篮球职业联赛福建鲟浔兴篮球俱乐部,位置是控球后卫。退休后转任南山高中
  • 西耶娜·米勒西耶娜·罗丝·米勒(英语:Sienna Rose Miller,1981年12月28日-)英国女演员、模特儿。西耶娜以她跟另一英国影星,裘德·洛(Jude Law)离离合合的恋情最为人熟悉。
  • 杉山元杉山元(1880年1月1日-1945年9月12日),日本帝国时代的陆军军人。元帅陆军大将、陆军大臣、教育総监、太平洋戦争开戦时参谋総长。福冈県出身。杉山元是日军决策中心的核心人物之
  • 天主教基拉卢教区天主教凯里教区(拉丁语:Dioecesis Laoniensis、爱尔兰语:Deoise Chiarraí)是爱尔兰一个罗马天主教教区。属卡舍尔暨埃姆利总教区。始于6世纪。范围包括克莱尔郡、北蒂珀雷里郡