100层楼扔鸡蛋,找出哪层是鸡蛋碎的临界点

问题

有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点?

方法1:暴力枚举

只需用一个鸡蛋,从第1层开始扔,如果鸡蛋没碎,则再向上1层,直到鸡蛋在第x层砸碎,临界点是第x-1层,复杂度为O(N)。

方法2:二分法

第一个鸡蛋用二分法,直到砸碎,接着用第二个鸡蛋从第1层向上逐层尝试,直到第x层砸碎,临界点是x-1层。举例:第一次从50层扔。如果碎了,说明临界点在1到50层之间,用第二个鸡蛋从1尝试到49,找出临界点。如果第一次在50层没碎,则第二次在75层扔,如果第二次碎了,说明临界点在51到75层之间,用第二个鸡蛋从51尝试到74。依次类推。最坏情况是第一次在50层碎掉,需要尝试1+49=50次。

方法3:分区

100的平方根是10。因此,将100层楼分为10个区域,每个区域10层。第一个鸡蛋尝试每10层扔一次,第一次从10层扔,第二次从20层扔,第三次从30层……一直扔到100层。如果某次鸡蛋碎掉,则用第二个鸡蛋在该区域中从下到上依次尝试。这样的最好情况是在第10层碎掉,尝试次数为 1 + 9 = 10次。最坏的情况是在第100层碎掉,尝试次数为 10 + 9 = 19次。

方法4:最优分区

假设最优的尝试次数的x次,第一次选择第x层扔。
原理:
假设第一次扔在第x+1层:
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x层。
这样一来,我们总共尝试了x+1次,和假设尝试x次相悖。由此可见,第一次扔的楼层必须小于x+1层。

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

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

因此,要想尽量楼层跨度大一些,又要保证不超过假设的尝试次数x,那么第一次扔鸡蛋的最优选择就是第x层。

x + (x-1) + (x-2) + … + 1 = 100,左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次,所以这个多项式共有x项。右边是总的楼层数100。x向上取整,得到 x = 14。因此,最优解在最坏情况的尝试次数是14次,第一次扔鸡蛋的楼层也是14层。最后,让我们把第一个鸡蛋没碎的情况下,所尝试的楼层数完整列举出来:
14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

解题思路

分区

发表评论

电子邮件地址不会被公开。 必填项已用*标注