双蛋问题（**'）是一个经典的算法问题，它经常被描述为“给你两个相同的异常坚硬的鸡蛋，通过在一栋100层的楼的不同层扔下鸡蛋进行实验，试验出可以摔碎该鸡蛋的最高楼层（临界楼层）。已知未碎的鸡蛋可以重复使用。求最少的实验次数n,使得在n次实验后，一定能判断出该临界楼层。”
该问题可以扩展为这样一类问题： 在N个鸡蛋，k层楼的条件下，找到一个最小的m，使得存在一种方案，在m次实验以后，一定能找到鸡蛋的临界楼层。
问题假设
为了更加精确地思考问题，该问题中必须满足以下的条件：
#如果鸡蛋在某一层没有碎,它不会在任何更低层的破碎。
#如果鸡蛋在某一层碎了，它在更高层上一定会碎。
#鸡蛋可能在一楼摔破，也可能在最高层还不摔破。
解决方案
此时，你有2个鸡蛋，楼高100层。我们可以先思考有1个鸡蛋和有无数个鸡蛋的情况。
1个鸡蛋
此时，由于只有一个鸡蛋，所以一旦破碎，那么就无法继续进行试验，我们只能从第1层开始，一层一层地实验。在这种情况下最多需要99次实验。
无数个鸡蛋
容易的解决方案是二分法，\log_2{100}\approx 6.644 ,所以如果我们有无数个鸡蛋，我们最多只需要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:裡;}-一部分？为此，有以下方案，第一组x人，第二组(x-1)人,第三组(x-2)人,……第x组1人，考虑到x+(x-1)+(x-2)+\cdots+3+2+1=\frac{x(x+1)}{2} > 100，解得x > 13.65，所以x=14时，最多需要14次便可以找出临界楼层。
推广问题
下面是双蛋问题的几个推广问题。
2个鸡蛋，k层楼
类似于之前的方法，只需要x+(x-1)+(x-2)+\cdots+3+2+1=\frac{x(x+1)}{2} > k即可，可以求出k=\left\lceil\frac{-1+\sqrt{1+8k}}{2}\right\rceil（参见取整函数、高斯符号）
n个鸡蛋，k层楼
让我们定义一个函数f(d,n),表示有n个鸡蛋，通过d次实验就一定能够判断出临界楼层的最大楼层。 如果鸡蛋打破,我们将能够将临界楼层范围缩小到f(d−1,n−1)层；否则我们将能够把范围缩小到 f(d-1,n)层。
因此，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)
根据我们的第一个方程
\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}
函数g(d,n)可以写成g(d,n)= \binom{d}{n}（参见二项式系数）
但是我们有一个问题：根据之前的关系f和g，对于任何n，f(0,n)以及g(0,n)都是0。然而,在n=0时会发生矛盾，因为g(0,0)=\binom{0}{0}=1，但对于每一个n，g(0,n)应该是0!
我们可以通过重定义g(d,n)修复这个问题如下：
g(d,n)= \binom{d}{n+1}
递归是仍然有效。
现在，展开f(d,n),我们可以把它写成
\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}
我们知道f(d,0)=0,因此
f(d,n)=g(d,n-1)+g(d,n-2)+\cdots+g(d,0)
我们也知道
g(d,n)=\binom{d}{n+1}
因此，
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) = \sum_{i=1}^{n}{\binom{d}{i}}
我们知道f(d,n)是所有最少实验次数为d的总楼层数中最大的一个，我们只要找到一个k满足以下条件即可：
f(d,n) \geqslant k
使用我们最后的公式,
\sum_{i=1}^{n}{\binom{d}{i}} \geqslant k
让我们来试验一下:
f(t,3)=\sum_{i=1}^{3}{\binom{t}{i}}=\frac{t(t^2+5)}{6}
因此有f(8,3) = 92,f(9,3) = 129
所以我们如果有三个鸡蛋，可以保证在9次实验之内找到临界楼层。
其他方法
除了解析法之外，最常见的方法是递归法。
想象以下情况：n个鸡蛋，k层楼，然后你把鸡蛋在连续的h层中的第i层进行试验。
如果鸡蛋打破：这个问题会减少为n-1鸡蛋和 i-1个剩余楼层的问题；如果不打破：这个问题会减少为n鸡蛋和h-i个剩余楼层的问题。
现在我们可以定义一个函数W(n,h)计算所需的最小实验次数：
我们可以编写上述结果为确定找到下面的递归W(n,h):
以下代码由C++编写
W(n,h)=1+min(max(W(n-1,i-1),W(n,h-i)))
#include
#include
#include
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>e;
cout>f;
cout
参见
*递归
*二项式系数
*取整函数、高斯符号
參考資料
外部連結
#[https://blog.csdn.net/u012803274/article/details/104824421 双蛋问题的另一个递归程序]
#[https://www.bilibili.com/video/BV1KE41137PK 李永乐老师]
#[https://www.geeksforgeeks.org/solve-dynamic-programming-problem/ 相关动态规划问题]
评论 (0)