一点一点前进...

0%

鸡蛋从多少层掉下来不破呢?

有一个100层的建筑。如果鸡蛋从第N层或更高掉下来就会碎,低于N层就不会碎。给你两个鸡蛋,找到这个N。要求是使得最坏情况下次数最少。

如何找到答案呢?让第一个鸡蛋去大致试一下楼层,第二个鸡蛋精确的去找到N。比如,第一个鸡蛋从10层扔下去,没碎,但是从15层扔下去碎了,那么N可能是11,12,13,14这四层,第二个鸡蛋必须从最小的开始去找,不然的话,碎了后面就没办法实验了。

我们先尝试一下,假设第一个鸡蛋按照10,20,30这样子扔。第二个鸡蛋从X1,X2,这样子扔,最坏情况下,N是99,那么总共需要19次就能得到结果。看起来,是个不错的结果。

最坏情况下次数最少,还能比19更少了吗?
我们创建这样一种机制:

  1. 完美的负载平衡的系统,不管第一个鸡蛋在哪里碎了,总数是一样的
  2. 第一个鸡蛋没多扔一次,那么第二个鸡蛋就要少扔一次。比如,第一个鸡蛋10层扔完之后,20层扔完都没有破,这一次尝试,第二个鸡蛋最多要扔9次,那么第一个鸡蛋再次尝试的时候,第二个鸡蛋最多就只能扔8次,也就是第一个鸡蛋去尝试29层。
  3. 抽象一些,第一个鸡蛋第一次尝试X层,下一次增长量是X-1层,再然后是X-2层,直到100层。
  4. 解出X的值。X + (X - 1) + (X - 2) + … + 1 =100。可以得到X = 14。

这样能保证最多14次,一定能找到N。

其他这样的最优化问题,一个关键思想就是使得最差情况平衡一些,也就是让最坏情况不要变得这么坏。