您的位置 > 工作简历网 > 面试问题

谷歌面试题详解:你拿着两个鸡蛋站在100层的大楼上

时间: 2014-12-10   阅读:    发布: www.gongzuojianli.com

  题目:你拿着两个鸡蛋站在100层的大楼上。鸡蛋或许结实到从楼顶掉下也不会摔破,或许很易碎,在一楼摔下就破碎。最少试验多少次可以找出鸡蛋不会被摔碎的最高楼层?

  解答: 在只有一个鸡蛋时,保险起见,我们只能从一楼开始,一层一层地试验,看看鸡蛋有没有被摔烂。这样最精确,但是消耗的时间也最久。如果我们事先就知道这个鸡蛋不被摔碎的最高落下点在30层到75层之间,我们最多也只要尝试45次就能知道结果。现在我们手上有两个鸡蛋,根据上面的分析,一个合理的策略就是用第一个鸡蛋确定出一个较小的楼层范围,然后在这个范围里用第二个鸡蛋从下往上逐层尝试。

  比如说让第一个鸡蛋每隔5层试验一次。当它在某一层被摔烂时,也就意味着确定了一个4层的待测试宽度(为什么是4层呢?假如鸡蛋在5楼的时候没破,10楼的时候破了,那么我们就只需要知道鸡蛋在 6 , 7 , 8 , 9 层的结果)。这时候,用第二颗鸡蛋一层一层地尝试,就能用较少的次数找出鸡蛋刚好摔不烂的高度。

  需要注意的是,如果想留给第二颗鸡蛋较小的测试宽度,就要缩短第一个鸡蛋的测试跨度。相应的,也就增加了尝试次数。为了确定合适的跨度,使得总试验次数之和尽可能小,我们可以采取如下的办法。

  设跨度是L,第一颗鸡蛋的尝试次数就是[ 100/L ],第二颗鸡蛋的尝试次数就是 L - 1,因此尝试次数总和就是 [ 100/L ] + L - 1 。根据这个公式,我们可以列出下面这个表格:

  可以看出,我们只需要选 8 - 13 之间的一个宽度,都能使得总尝试次数是19次。

  但问题是,这已经是最优策略了吗,有没有更好的方法呢?

  有的。上面的方法固定了第一颗鸡蛋的测试跨度,如果我们灵活变动,就能使得总尝试次数变得更少。首先,我们选择从14楼丢下第一颗鸡蛋。如果它破碎了,我们就从1楼开始,逐层丢第二颗鸡蛋,最多试14次便能得到答案。如果它没有破碎,那我们往上走 13 层,在 27 楼第二次丢下第一颗鸡蛋。此时如果鸡蛋碎了,那我们只需要在 15 层到 26 层之间用第二颗鸡蛋进行最多12次试验即可,加上第一颗鸡蛋的两次尝试,仍然是14次。类似的,依次减小测试跨度,如果鸡蛋足够顽强,那我们丢下第一颗鸡蛋的楼层就分别是 14 , 27 , 39 , 50 , 60 , 69 , 77 ,84 , 90 , 95 , 99 以及最后的100层。因为第一颗鸡蛋每多尝试一次,第二颗鸡蛋需要尝试的最大次数就减少一次,因此,总尝试次数的最大可能值一直是不变的,保持在14次。用这种方法,我们只需要不超过14次的尝试就能够找出答案。有没有更优的策略了?感兴趣的读者可以自行思考。

分页: 123

Copyright©2011-2016 工作简历网 All Rights Reserved.

联系我们 网站地图 友情链接 欢迎投稿 闽ICP备11024869号-3