# 双蛋问题

## 问题假设

1. 如果鸡蛋在某一层没有碎,它不会在任何更低层的破碎。
2. 如果鸡蛋在某一层碎了，它在更高层上一定会碎。
3. 鸡蛋可能在一楼摔破，也可能在最高层还不摔破。

## 推广问题

### n个鸡蛋，k层楼

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

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

{\displaystyle {\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}}}

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

${\displaystyle g(d,n)={\binom {d}{n+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}}}$

${\displaystyle f(d,n)=\sum _{i=1}^{n}{\binom {d}{i}}}$

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

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

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

### 其他方法

${\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 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;
}
}


## 參考資料

1. ^ The Two Eggs Problem. [2020-06-20]. （原始内容存档于2020-08-19）.
2. ^ Egg Dropping. [2020-06-20]. （原始内容存档于2020-06-23）.
3. ^ The egg problem. [2020-06-20]. （原始内容存档于2020-03-12）.