扔鸡蛋问题

倪举鹏

你拥有两个鸡蛋，鸡蛋从某一特定楼层及以上的楼层扔下会破粹，从以下的楼层扔下会完好无损。两个鸡蛋完全相同。现在有一个 100 层的大楼，只有两个鸡蛋可以使用，你需要找出让鸡蛋摔碎的临界楼层，问题是你将怎么扔鸡蛋，保证找到临界楼层，所扔次数的期望值最小？    3个鸡蛋以上呢

kastin

楼层和高度成正比，可看做是已经排好序的表的查找问题，一般选择二分搜索法或者黄金分割搜索法，平均次数是 O(log n) 级别。

zeroieme

100层楼其实是99倍单层楼高，
第一只第11楼起隔10层试验，碎了。用第二只试验第一只碎的下9层开始逐层试验。

王守恩

1，拥有1个鸡蛋。从第1，2，3，4，5......层依次扔下，直到碎了为止。(从第1层开始逐层往上走)。

2，拥有2个鸡蛋。第1个鸡蛋从第50，75，87...层依次扔下，直到碎了为止。(从第1层开始加半往上走)。
                             第2个鸡蛋从安全层开始逐层往上走。

3，拥有3个鸡蛋。第1个鸡蛋从第1层开始加半往上走。
                             第2个鸡蛋从安全层开始加半往上走。
                             第3个鸡蛋从安全层开始逐层往上走。

4，拥有4个鸡蛋。第1个鸡蛋从第1层开始加半往上走。
                             第2个鸡蛋从安全层开始加半往上走。
                             第3个鸡蛋从安全层开始加半往上走。
                             第4个鸡蛋从安全层开始逐层往上走。

5，拥有5个鸡蛋。第1个鸡蛋从第1层开始加半往上走。
                             第2个鸡蛋从安全层开始加半往上走。
                             第3个鸡蛋从安全层开始加半往上走。
                             第4个鸡蛋从安全层开始加半往上走。   
                             第5个鸡蛋从安全层开始逐层往上走。   

sheng_jianguo

让题设更严谨些：在1至 100 层的大楼中，临界楼层处于2 ~ 99层，即鸡蛋从100楼层扔下肯定会破碎，鸡蛋从1楼层扔下肯定会完好无损。
由于扔一个鸡蛋后，问题方向是确定的。所以我认为二分法是最佳的寻找临界楼层的方法。
对于只有两个鸡蛋，具体方案如下：
选楼层，[(99+2)/2]=50（取整），从50层往下扔，
如果破碎，从2层开始往下仍，不碎上一层再仍，直到碎为止就可找到临界楼层；
如果不破碎，选楼层，[(99+51)/2]=75，重复上述过程，直到找到临界楼层。

3个鸡蛋（或以上）方法类似，只是如果还有鸡蛋，当仍下碎时，不是从最近不碎层往上一层层仍鸡蛋，而是继续二分法找临界楼层。

注：写的时候没看到楼上帖子，我的方法和楼上的一致。不知这个方法是否是最佳方法（扔次数的期望值最小）?

mathe

二分法肯定不是最好的。第一次第50层如果破碎，只有一个鸡蛋可以检测下面的楼层，但是如果没有破碎，有两个鸡蛋可以检测上面的楼层。
这个显然是一个动态规划问题

mathe

首先我们需要考虑有多少个有效楼层，比如sheng的理解方案下就只有98个有效楼层，1楼和100楼均不需要检测。既然谈到期望，还有先验分布问题，比如按我们先验知识，正常鸡蛋二楼就会破裂，直接到二楼验证即可。所以我们需要在我们的模型上规定，对于n个有效楼层，出现的n+1种情况我们要求等概率

mathe

于是一个鸡蛋检测n个有效楼层平均(n+1)/2次

mathe

对于两个鸡蛋假设检测n个楼层期望为a(n),那么第一次选第k层，如果碎裂，还需要平均k/2次，没碎，还需要a(n-k)

mathe

a(0)=0,a(1)=1,a(n)=1+min{k/(n+1)*k/2+(n+1-k)/(n+1)*a(n-k)}