Google 面试题 - 玻璃球

题目

给你两个一模一样的玻璃球. 这两个球如果从一定高度掉到地上就会摔碎, 当然, 如果在这个高度以下往下扔, 怎么都不会碎, 超过这个高度肯定就一次摔碎.
现在已知这个恰巧摔碎的高度范围在 1 楼到 100 层之间, 如何用最少的试验次数, 用这两个玻璃球测试出玻璃球恰好摔碎的楼高

一般策略

逐一法

第 1 颗球: 从 1 楼开始, 逐一往上加, 直到摔碎为止, 则找到位置

二分法

第 1 颗球, 从 50 楼(1/2 的位置)开始, 如果未碎, 接着 75 楼, 如碎了
第 2 颗球, 从 51 楼开始, 逐一法到碎为止, 则找到位置.

粗选细选

第 1 颗球, 从 10 楼开始, 逐 10 往上加, 直到摔碎为止. 比如, 玻璃球在 50 楼碎了
第 2 颗球, 从 41 楼开始, 逐一法到碎为止, 则找到位置

分析

基本逻辑

1. 如果只有一个球, 用逐一法是唯一可解决问题的方案.
2. 如果有无限多的球, 用二分法是最优解(在没有任何额外提醒的情况下, 二分法一定是最优的)

双球的策略分析

从基本逻辑思考, 1 颗球必须用于逐一法, 1 颗球用于二分法. 有个困难点是在只有 2 颗球的情况下如何进行二分法.

可以通过如下方式

左边:二分/逐一混合算法, 是在第 1 颗球成功的情况下, 由于第 1 颗球还可以继续使用, 使用混合算法
右边: 逐一法, 第 1 颗一旦失败, 后面就只能用逐一法进行)
以左右两边的次数一致的原则, 进行二分法.

逐一递推

1. 2 : 2
2. 4 : 3
3. 7 : 4
4. 11 : 5
5. 16 : 6
6. 22 : 7
7. 29 : 8
8. 37 : 9
9. 46 : 10
10. 56 : 11
11. 65 : 12
12. 77 : 13
13. 90 : 14

最佳答案

第 1 颗从第 15(14+1)楼开始, 运气最差的情况下, 试验 14 次, 可获得准确楼层.