美文网首页
你还在用二分法求2个鸡蛋100层楼的问题吗?

你还在用二分法求2个鸡蛋100层楼的问题吗?

作者: 前端极客技术 | 来源:发表于2019-07-11 08:38 被阅读0次

题目

2个鸡蛋,100层楼,如何用最少的试验次数得到在鸡蛋落下不碎的最高层数?这一据说曾被谷歌纳入校园招聘题库的经典面试题,想必许多人都曾遇到过,又有多少人与我一样,不加思索就直接回答用二分法查找的?

但是,二分法真的是最优试验方法吗?接下来我们来分析几种解法。

首先我们先认真看一下完整的题目(之前做过这道题的同学可以跳过这一步):

原题:两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼扔下来就摔碎,也有可能从100层楼上扔下来也没事。有座100层的楼,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋,在最坏情况下,如何用最少的试验次数得到鸡蛋落下不会被摔碎的最高层数?

解法

最笨的方法:遍历查找

把其中的一个鸡蛋,从第1层开始往下扔。如果第一层没碎,换到第2层扔;如果第2层没碎,换到第3层扔...假设第50层没碎,第51层碎了,说明鸡蛋落下不会摔碎的最高层数为第50层。

这个方法在最坏情况下,需要扔99次。

二分法

采用二分查找的方法:

把第一个鸡蛋从一半楼层(50层)扔下。

如果鸡蛋碎了,则第二个鸡蛋就从第1层开始扔,一层一层增长,直到49层。

如果第一枚鸡蛋在50层没有被摔碎,则继续使用二分法,从剩余的楼层的一半(75层)开始往下扔...

two_egg_one_hundred_floor_1.png

在最坏情况下,这种二分法需要进行50次试验0。

平方根法

如何让第一个鸡蛋和第二个鸡蛋的尝试次数尽可能均衡?我们做一个平方根运算,100的平方根为10。

因此我们第一个鸡蛋每10层扔一次,第一次从第10层扔,没碎的话再加10层,即从20层扔....一直扔到100层。

第二个鸡蛋从第一个鸡蛋碎掉的n层往下9层,即n-9层开始一层一层往上试。

two_egg_one_hundred_floor_2.png

这种方法最好的情况为:第一个鸡蛋在第10层碎掉,尝试次数 1 + 9 = 10 次。

最坏的情况为:第一个鸡蛋在第100层碎掉,尝试次数为 10 + 9 = 19 次。

这样子看来平方根的方法算是比较好的方法,那么还有更好的方法吗?

反向思考

我们反向思考一下这个题目:假设题目存在最优解,这个最优解的最坏情况尝试x次,那么我们第一次扔要选择在第几层?

假设第一次扔在x+1层:如果第一个鸡蛋碎了,那么第二个鸡蛋就只能从第1层开始一层一层扔,一直扔到第x层。这样总共尝试了x+1次,与最优解的尝试x次相悖。

假设第一次在x-1层:如果第一个鸡蛋碎了,那么第2个鸡蛋就要从第1层开始扔,一直到x-2层,共尝试了x-2+1=x-1次,虽然没有超出假设次数,但似乎有些过于保守。

假设第一次扔在第x层:

如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-1层。这样,我们总共尝试了x-1+1 = x次,刚刚好没有超出假设次数。

恰恰是从第x层开始扔,选择高一层或第一层都不合适。

如果第一个鸡蛋没碎,问题就变成了:在100-x层楼往下扔,要求尝试次数不超过x-1次。

那么第二次的尝试次数的上限变为x-1次,所以第2次试验的楼层跨度为x-1层,真实层数为x+x-1层。

two_egg_one_hundred_floor_3.png

以此类推我们可以列出楼层的方程式: x + (x - 1) + (x - 2) + ... + 1 = 100

接下来就是求解方程式,我们将这种方法称为解方程法:

解方程法

x + (x - 1) + (x - 2) + ... + 1 = 100 => (x + 1) * x / 2 = 100

向上取整得到x=14

即最优解的最坏尝试次数为14次,第1个鸡蛋开始扔的层数也为14层。

第一个鸡蛋没碎的情况下,所尝试的楼层为:14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

假设鸡蛋不会被摔碎的最高楼层为55层,那么第一个鸡蛋尝试的楼层为14,27,39,50,60,在第60层碎了;

第二个鸡蛋从51层开始, 51,52,53,54,55,56,第56层碎了,则尝试次数为5 + 6 = 11 < 14

这道面试题的解法到此到一段落,现在你还会认为二分法是这道题的最优解吗?

其实这道题还可以衍生下面的问题:
总共有M层楼,N个鸡蛋,要找到鸡蛋不被摔碎的最高楼层,需要尝试几次?

这个问题就不在这里展开讨论了,大家可以自行尝试求解。

相关文章

  • 你还在用二分法求2个鸡蛋100层楼的问题吗?

    题目 2个鸡蛋,100层楼,如何用最少的试验次数得到在鸡蛋落下不碎的最高层数?这一据说曾被谷歌纳入校园招聘题库的经...

  • swift解决双蛋问题

    双蛋问题: 有t层楼,n个鸡蛋,鸡蛋从某层楼以上掉下肯定会摔碎,从该层楼以下掉下肯定不会摔碎。现在求最少扔几次能够...

  • 9.8 题目收集

    求二叉树的宽度 给2个鸡蛋,100层楼,求确认最高多少层扔下鸡蛋不碎的最少测试次数 多项式相差的表达式 基础知识:...

  • 谷歌“扔鸡蛋问题”

    问题: 假设有2个鸡蛋和100层楼,将鸡蛋从第n层扔下,鸡蛋没有碎,将鸡蛋从n+1层扔下,鸡蛋碎了,那么n层就...

  • 有趣的扔鸡蛋问题

    题目:扔鸡蛋问题 有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎...

  • 漫画:有趣的扔鸡蛋问题

    本文转载自程序员小灰 ————— 第二天 ————— 题目:扔鸡蛋问题 有2个鸡蛋,从100层楼上往下扔,以此...

  • 鸡蛋的热量,鸡蛋热量高吗?鸡蛋能减肥?看完你就明白了2018-1

    鸡蛋的热量,鸡蛋热量高吗?鸡蛋能减肥?看完你就明白了。鸡蛋的热量每100克大约是144大卡,热量不算高。鸡蛋营...

  • 进步有什么好?

    每次看到抖音里的广告说“你还在用传统的抹布吗?”“你还在用以前的拖把吗?”“你还在用钢丝球吗”“你还在用老衣架吗”...

  • 数据结构-二分法求幂-C

    二分法求幂 数据结构中二分法运用到求幂提高计算效率方式,算法精简这里做个简单解释及代码 原理自析 如求2^32: ...

  • 动态规划,dfs

    鸡蛋掉落问题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的,如...

网友评论

      本文标题:你还在用二分法求2个鸡蛋100层楼的问题吗?

      本文链接:https://www.haomeiwen.com/subject/vjglkctx.html