有一个100层的建筑。如果鸡蛋从第N层或更高掉下来就会碎,低于N层就不会碎。给你两个鸡蛋,找到这个N。要求是使得最坏情况下次数最少。
如何找到答案呢?让第一个鸡蛋去大致试一下楼层,第二个鸡蛋精确的去找到N。比如,第一个鸡蛋从10层扔下去,没碎,但是从15层扔下去碎了,那么N可能是11,12,13,14这四层,第二个鸡蛋必须从最小的开始去找,不然的话,碎了后面就没办法实验了。
我们先尝试一下,假设第一个鸡蛋按照10,20,30这样子扔。第二个鸡蛋从X1,X2,这样子扔,最坏情况下,N是99,那么总共需要19次就能得到结果。看起来,是个不错的结果。
最坏情况下次数最少,还能比19更少了吗?
我们创建这样一种机制:
- 完美的负载平衡的系统,不管第一个鸡蛋在哪里碎了,总数是一样的
- 第一个鸡蛋没多扔一次,那么第二个鸡蛋就要少扔一次。比如,第一个鸡蛋10层扔完之后,20层扔完都没有破,这一次尝试,第二个鸡蛋最多要扔9次,那么第一个鸡蛋再次尝试的时候,第二个鸡蛋最多就只能扔8次,也就是第一个鸡蛋去尝试29层。
- 抽象一些,第一个鸡蛋第一次尝试X层,下一次增长量是X-1层,再然后是X-2层,直到100层。
- 解出X的值。X + (X - 1) + (X - 2) + … + 1 =100。可以得到X = 14。
这样能保证最多14次,一定能找到N。
其他这样的最优化问题,一个关键思想就是使得最差情况平衡一些,也就是让最坏情况不要变得这么坏。