鸡蛋、建筑与熵：双鸡蛋100层楼测试最优策略问询

嘿，这个经典的双鸡蛋问题我太熟了！咱们只有两枚鸡蛋，碎了就没法再用，所以核心目标是让最坏情况下的测试次数尽可能少——毕竟谁也不想运气最差的时候测几十次对吧？

为什么常规思路不行？ #

先排除两个明显不太行的方案：

• 从1层开始逐层试：最坏情况要测100次，效率太低，完全没必要
• 对半分（比如先扔50层）：如果碎了，剩下的一枚得从1层试到49层，最坏要50次，还是很浪费

所以我们需要找一种「不管鸡蛋在哪一层碎，最坏测试次数都固定」的方案，这样能把最大成本控制到最低。

最优方案的核心逻辑 #

假设最坏情况下我们最多需要x次测试，那第一次扔鸡蛋的楼层应该选在第x层：

• 如果碎了：剩下的一枚鸡蛋必须从1层开始逐层往上试，最多试x-1次，加上这次刚好x次
• 如果没碎：第二次扔的楼层应该是x + (x-1)层——因为已经用了1次测试，剩下最多x-1次机会，所以间隔要减1，保证如果这次碎了，剩下的楼层数刚好能用x-2次试完，总次数还是x

以此类推，每次扔鸡蛋的间隔都比上一次少1，直到累加的楼层数超过100层。

计算最优次数x #

我们需要满足等差数列求和：x + (x-1) + (x-2) + ... + 1 ≥ 100，也就是x(x+1)/2 ≥ 100。

算一下：

• 13*14/2=91，不够覆盖100层
• 14*15/2=105，刚好超过100层，所以x=14是最小的满足条件的数

具体测试步骤 #

按照这个逻辑，具体的测试楼层依次是：

• 第1次：14层
  • 碎了：从1层到13层逐层试，最多13次，总次数14次
  • 没碎：第2次去27层（14+13）
• 第2次：27层
  • 碎了：从15层到26层逐层试，最多12次，总次数14次
  • 没碎：第3次去39层（27+12）
• 第3次：39层
  • 碎了：从28层到38层逐层试，最多11次，总次数14次
  • 没碎：第4次去50层（39+11）
• 第4次：50层
• 第5次：60层（50+10）
• 第6次：69层（60+9）
• 第7次：77层（69+8）
• 第8次：84层（77+7）
• 第9次：90层（84+6）
• 第10次：95层（90+5）
• 第11次：99层（95+4）
  • 碎了：从96层到98层逐层试，最多3次，总次数14次
  • 没碎：第12次去100层
• 第12次：100层（如果到这一步还没碎，那100层就是安全最高层）

不管鸡蛋在哪个楼层碎掉，最坏情况下都只需要14次测试，这就是最优的方案了。

内容的提问来源于stack exchange，提问作者Dio