查看“︁双蛋问题”︁的源代码

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

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

==问题假设==
为了更加精确地思考问题，该问题中必须满足以下的条件：
#如果鸡蛋在某一层没有碎,它不会在任何更低层的破碎。
#如果鸡蛋在某一层碎了，它在更高层上一定会碎。
#鸡蛋可能在一楼摔破，也可能在最高层还不摔破。

==解决方案==
此时，你有2个鸡蛋，楼高100层。我们可以先思考有1个鸡蛋和有无数个鸡蛋的情况<ref>{{cite web|url=http://datagenetics.com/blog/july22012/index.html|title=The Two Eggs Problem|accessdate=2020-06-20|archive-date=2020-08-19|archive-url=https://web.archive.org/web/20200819071945/http://www.datagenetics.com/blog/july22012/index.html|dead-url=no}}</ref>。
===1个鸡蛋===
此时，由于只有一个鸡蛋，所以一旦破碎，那么就无法继续进行试验，我们只能从第1层开始，一层一层地实验。在这种情况下最多需要99次实验。

===无数个鸡蛋===
容易的解决方案是二分法，<math>\log_2{100}\approx 6.644 < 7 </math>  ,所以如果我们有无数个鸡蛋，我们最多只需要7次就可以试验出。比如，先在64楼扔一次鸡蛋，如果碎了，那就到32层扔第二次，如果第二次扔鸡蛋又碎了，再到16层去扔第三次，如果这次没有碎，那你可以再到第24层去扔第四次，又没碎，那就去28层扔第五次，还是没有碎，再到30层扔第六次，这次又碎了，再到29层扔第七次，第七次碎了，那么临界楼层就是第28层，第七次没碎，临界楼层就是第29层。所以无数个鸡蛋最多只需要7次就可以实验。
===两个鸡蛋===
借助于二分法提供的分组思想，我们可以尝试将100平均分成10组，用第一个鸡蛋在每组最后一层进行实验，这样可以实验出临界楼层在哪一组。然后再用第二个鸡蛋从该组第一层依次实验。这种方案的最坏情况是19次。

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

==推广问题==
下面是双蛋问题的几个推广问题<ref>{{cite web|url=https://brilliant.org/wiki/egg-dropping/#a-better-approach|title=Egg Dropping|accessdate=2020-06-20|archive-date=2020-06-23|archive-url=https://web.archive.org/web/20200623064944/https://brilliant.org/wiki/egg-dropping/#a-better-approach|dead-url=no}}</ref><ref>{{cite web|url=http://spencermortensen.com/articles/egg-problem/|title=The egg problem|accessdate=2020-06-20|archive-date=2020-03-12|archive-url=https://web.archive.org/web/20200312061225/http://spencermortensen.com/articles/egg-problem/|dead-url=no}}</ref>。

===2个鸡蛋，k层楼===
类似于之前的方法，只需要<math>x+(x-1)+(x-2)+\cdots+3+2+1=\frac{x(x+1)}{2} > k</math>即可，可以求出<math>k=\left\lceil\frac{-1+\sqrt{1+8k}}{2}\right\rceil</math>（参见[[取整函数]]、[[高斯符号]]）
===n个鸡蛋，k层楼===
让我们定义一个函数<math>f(d,n)</math>,表示有<math>n</math>个鸡蛋，通过<math>d</math>次实验就一定能够判断出临界楼层的最大楼层。 如果鸡蛋打破,我们将能够将临界楼层范围缩小到f(d−1,n−1)层；否则我们将能够把范围缩小到 f(d-1,n)层。 

因此，<math>f(d,n) = 1 + f(d-1,n-1) + f(d-1,n)</math>。这只是一个[[递归]]关系，而我们必须找到一个函数 f(d,n)。 

因此,我们将定义一个辅助函数<math>g(d,n):g(d,n)=f(d,n+1)-f(d,n)</math>

根据我们的第一个方程

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

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

我们可以通过重定义<math>g(d,n)</math>修复这个问题如下：

<math>g(d,n)= \binom{d}{n+1}</math>

[[递归]]是仍然有效。

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

<math>\begin{aligned} f(d,n)= &[f(d,n)-f(d,n-1)]\\ +&[f(d,n-1)-f(d,n-2)]\\ +&\cdots \\ +&[f(d,1)-f(d,0)] \\ +&f(d,0). \end{aligned}</math>

我们知道<math>f(d,0)=0</math>,因此

<math>f(d,n)=g(d,n-1)+g(d,n-2)+\cdots+g(d,0)</math>

我们也知道

<math>g(d,n)=\binom{d}{n+1}</math>


因此，

<math>g(d,n-1)+g(d,n-2)+\cdots+g(d,0)=\binom{d}{n}+\binom{d}{n-1}+\cdots+\binom{d}{1}</math>

最后，

<math>f(d,n) = \sum_{i=1}^{n}{\binom{d}{i}}</math>

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

<math>f(d,n) \geqslant k</math>

使用我们最后的公式,

<math>\sum_{i=1}^{n}{\binom{d}{i}} \geqslant k</math>

让我们来试验一下:

<math>f(t,3)=\sum_{i=1}^{3}{\binom{t}{i}}=\frac{t(t^2+5)}{6}</math>

因此有<math>f(8,3) = 92,f(9,3) = 129</math>

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

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

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

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

我们可以编写上述结果为确定找到下面的递归<math>W(n,h)</math>:

以下代码由C++编写

<math>W(n,h)=1+min(max(W(n-1,i-1),W(n,h-i)))</math>

<syntaxhighlight lang="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;
}
}
</syntaxhighlight>

==参见==
*[[递归]]
*[[二项式系数]]
*[[取整函数]]、[[高斯符号]]


== 參考資料 ==
{{Reflist}}

== 外部連結 ==
#[https://blog.csdn.net/u012803274/article/details/104824421 双蛋问题的另一个递归程序]{{Wayback|url=https://blog.csdn.net/u012803274/article/details/104824421 |date=20200621024033 }}
#[https://www.bilibili.com/video/BV1KE41137PK 李永乐老师]{{Wayback|url=https://www.bilibili.com/video/BV1KE41137PK |date=20200621045312 }}
#[https://www.geeksforgeeks.org/solve-dynamic-programming-problem/ 相关动态规划问题]{{Wayback|url=https://www.geeksforgeeks.org/solve-dynamic-programming-problem/ |date=20200621080246 }}

[[Category:物理学专题]]
[[Category:物理科学]]
[[Category:物理學實驗]]