素材牛VIP会员
好多公司经常面的一道智力题,加分的
 青***8  分类:Html5  人气:1412  回帖:13  发布于6年前 收藏

一幢 200 层的大楼,给你两个鸡蛋。如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,都不碎。这两只鸡蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎?

 标签:html5javascript

讨论这个帖子(13)垃圾回帖将一律封号处理……

Lv5 码农
隔***陈 学生 6年前#1

这道题应该是考察至少需要抛几次来判断鸡蛋最高从多少层掉下去不会碎吧。

要减少最大尝试次数,最常规的思路就是使每种投掷情况看上去更“平均”。
这里我们假设最少需要抛掷的次数为n,那么我第一次抛掷的楼层会选择第n层,因为一旦滴一个鸡蛋在第n层摔落时碎了,则第二个鸡蛋我们需要从第1层到第n-1层逐一尝试来寻找,这样最大的尝试次数是在第n-1层投掷时才知道鸡蛋在这一层会不会碎,也就是需要n次实验。

如果在第n层没碎,则我们需要再向上选择楼层抛第一个鸡蛋,由于之前已经抛过一次,那么这次我们只能选择n+n-1层来抛,这样才能保证如果在n+n-1层出现蛋碎的情况下,从n+1层实验到n+n-1层所尝试的次数加上前2次的总和为n。

此处省略。

如果之前的尝试都没有成功,而我们离n次的限制还剩余1次了,这一次就必须只能存在一个可选楼层上,这也应该是最高一层。

如此看来,可以得到一个公式,

$$ n + (n - 1) + (n - 2) + ... + 1 >= 200 $$

进行公式的简化

$$ n ^ 2 + n - 400 >= 0 $$

求这个公式的最小整数解为 20 。
所以,最少需要抛掷 20 次。

Lv5 码农
sh***ao 职业无 6年前#2

2的n次方 我猜的

Lv7 码师
亡***师 JS工程师 6年前#3

有两个鸡蛋,鸡蛋不碎可以无限扔,可以从偶数层开始扔

Lv6 码匠
追***忆 UI设计师 6年前#4

难道不是第200层吗...=_=

Lv6 码匠
dg***26 软件测试工程师 6年前#5

相隔14层测试,
失败后第二个鸡蛋从之前的成功点向上测试
最多14+13次测试出来

Lv2 入门
青***f 页面重构设计 6年前#6

可以拿一个鸡蛋从第一层开始一层一层向高层试,O(n)的解法。也可以拿两个鸡蛋同时从1层3层试,3层扔下的鸡蛋没破就把1层的鸡蛋拿到5层,破了就把1层的鸡蛋拿到2层,循环下去,O(n/2)的解法。

Lv4 码徒
be***ar 产品经理 6年前#7

我只想说, 为什么不用二分法呢? 有人追评我再来解释.

到第8步, 后有同样有4种情况. 所以最多9步.判断出最高楼层.

Lv2 入门
高***售 JAVA开发工程师 6年前#8

一层层丢过去,哪层碎了就是哪层咯

Lv1 新人
多***悟 学生 6年前#9

假设第一个鸡蛋投出去的楼层分别为

如果第一个鸡蛋在ai楼层碎掉,那么下面第二个鸡蛋在保证必须检测出楼层的情况下必须扔出

所以在若第一个鸡蛋在ai层碎掉时,苏需要扔出的总次数为

最坏的情况(次数最多)可能出现在以下情况中

可以看出{a{i}} 为递减数列,取max时有a1=i.
max>=200,解出a1=20 .
所以扔的楼层分别为20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5
次数为20.

Lv4 码徒
风***j 技术总监 6年前#10

吃到肚子里,然后跳楼。。。

上一页12下一页
 文明上网,理性发言!   😉 阿里云幸运券,戳我领取