返回题库

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 截止）。

英文解析

Let the total number of drops in the worst case be tt. Adopt the "decreasing step size" strategy:

Drop the first ball from floor tt; if it does not break, drop the second ball from floor t+(t−1)t+(t-1); if it still does not break, increase the step by (t−2)(t-2), and so on.

If a ball breaks at some point, only one ball remains, requiring a linear floor-by-floor test between the last safe floor and the current floor, adding at most some number of drops such that the total does not exceed tt.

To cover 100 floors, we need
1+2+⋯+t=t(t+1)2≥100.1+2+\cdots+t=\frac{t(t+1)}{2}\ge 100.
The minimum satisfying value is t=14t=14 (14⋅15/2=10514\cdot 15/2=105).

Therefore, the minimum number of drops required is 14\boxed{14}, with the strategy being the above described step-by-step decreasing increments: dropping from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102... (up to 100).