好多公司经常面的一道智力题,加分的
高洛峰
高洛峰 2016-10-25 09:09:41
0
1
991

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

高洛峰
高洛峰

拥有18年软件开发和IT教学经验。曾任多家上市公司技术总监、架构师、项目经理、高级软件工程师等职务。 网络人气名人讲师,...

reply all(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


进行公式的简化

n2+n−400>=0


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


Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template