题目:栋建筑物高100层。若从第N层或更高的楼层扔下来,鸡蛋就会破掉。若从第N层以下的楼层扔下来则不会破掉。给你2个鸡蛋,请找出N,并要求最差情况下扔鸡蛋的次数为最少。
首先,在只有一个鸡蛋的情况下,要精确的找出N,只能从第一层慢慢往上扔,没有其他方法。
有两个鸡蛋,则使用第一个鸡蛋缩小范围,第二个鸡蛋找出精确的N值。
题目要求最差的情况下扔鸡蛋的次数最少,即扔第一个鸡蛋的次数F,与扔第二个鸡蛋的次数S的和F+S在最差的情况下最小。
缩小范围有两种方式:1. 按照固定的间隔缩小;2. 按照变长间隔缩小。
第一种方式即求:当100/interval +
interval 最小时的s的值,F+S = 100/interval
+
interval ;
第二种方式:如果按照变长间隔缩小范围,则为了保证扔鸡蛋的次数在最差的情况下最小,需要将间隔按照从大到小的顺序排序,然后按照此种缩小范围的方式扔鸡蛋,不然阔以很明显地找出一种方法比他优(最差情况下):
左边比右边要多丢几次,依此类推,要按照从最大间隔到最小间隔的缩小范围方式。
显然,这些间隔之和需要>=100,最大间隔应该尽量小,1+2+3+...14>100(不能有相同的,相同的会增加最差情况下的丢鸡蛋次数), 1+2+3+...+13<100,所以按照14 13 12 11 ... 的跳跃方式丢,最差情况下应该最小。