返回题库

100 层楼 2 球扔落问题

The 100-Story, 2-Ball Problem

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

你有两只完全相同的玻璃球与一栋 100 层楼。你想确定从哪一层起扔下去会碎的临界楼层（最高不碎楼层）。

问：在最坏情况下，至少需要扔多少次才能保证找到该楼层？最优策略是什么？

You have two identical glass balls and a 100-story building. You want to determine the highest floor from which a ball can be dropped without breaking. What is the minimum number of drops you need to guarantee finding this floor in the worst-case scenario, and what is the optimal strategy?

解析

设最坏情况下总扔次数为 tt。采用“递减步长”策略：

第 1 次从第 tt 层扔；若不碎，第 2 次从第 t+(t−1)t+(t-1) 层扔；再不碎则加 (t−2)(t-2)，依此类推。

若某次碎了，则剩下一只球，只需在上一安全楼层与当前楼层之间线性逐层测试，最多还需若干次，使总次数不超过 tt。

要覆盖 100 层，需要

1+2+⋯+t=t(t+1)2≥100.1+2+\cdots+t=\frac{t(t+1)}{2}\ge 100.

最小满足者为 t=14t=14（14⋅15/2=10514\cdot 15/2=105）。

因此最少需要 14\boxed{14} 次，策略即上述从 14、27、39、50、60、69、77、84、90、95、99、102… 这样逐步递减步长投掷（到 100 截止）。