极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。
每天晚上九点 B站讲解前端工程化直播,并解答相关问题。

# 100 层楼,两个玻璃球,求最少多少次测出能摔碎玻璃球的楼层

更多描述

给你两个一摸一样的球,这两个球如果从一定的高度掉到地上有可能就会摔碎,当然,如果在这个高度以下往下扔,怎么都不会碎,当然超过这个高度肯定就一定摔碎了。

现在已知这个恰巧摔碎高度范围在一层楼到 100 层楼之间。

如何用最少的试验次数,用这两个玻璃球测试出摔碎的楼高

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 701 (opens new window)

假设最少次数是 x 次 那么第一个我们从哪里扔呢 ?从 x 因为如果碎了 另一个球从 1 到 x 正好就是 x 如果没碎这时候我们第一个球第二次只剩 x-1 次 所以我们从 x+x-1 层扔 碎了从 x+1 到 x + x-2 遍历 后面逻辑一样 减 1 去扔第一个球 没碎下次再减 1 碎了从上一次的没碎的上一层遍历就好了

所以可以一共层数等于 x + (x-1) + (x-2) + ... + 1 = 100

下面我们来解这个这个方程:

(x+1)*x/2 = 100

最终 x 向上取整,得到 x=14

因此,最优解在最坏情况的尝试次数是 14 次,第一次扔鸡蛋的楼层也是 14 层。

最后,让我们把第一个鸡蛋没碎的情况下,所尝试的楼层数完整列举出来:

14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

Last Updated: 11/27/2021, 10:11:48 AM