问题: 有一幢100层的楼, 有一种鸡蛋,当从N楼的高度或则大于N楼的高度扔下来后会碎掉,当小于N楼时候没事。 现在给你两个鸡蛋去找到N, 要求在最坏的情况下扔的次数最少, 找到最少的次数?
第一次尝试: 假设我们第一个鸡蛋以10层的单位扔, 当到40层的时候第一个鸡蛋碎了,那么第二鸡蛋从30层一层一层的扔,31, 32, ---, 39。
那么着种扔法最好的情况是N= 1, 扔2次, 第一个鸡蛋从10层扔,碎了,第二鸡蛋从第一层开始扔,碎了,两次。
最坏的情况N= 99, 扔19次, 第一个鸡蛋从(10, 20, 30, 40, ---100)走到100层的时候扔,碎了,他扔了10次,之后第二鸡蛋从91层开始扔,扔到99层碎了, 那么总共扔了19次。
当然这种扔法并不是最坏情况下扔的最少次数。
次数还可以更少。
第二次尝试: 第一次尝试是第一个鸡蛋是10层10层走,这次第一个鸡蛋不是以固定层数走,每次第一个鸡蛋前进一个单位,每次前进的层数都要相应的减少,目的是为了在第一个鸡蛋碎了之后,第二个鸡蛋尝试的层数每次都减少,例如,如果第一个鸡蛋第一次现在在X层,第二次尝试就应该在地X + (X-1)层,如果在2X-1层碎了,那么第二鸡蛋最坏需要尝试X - 2次,加上第一个鸡蛋的两次, 总共X次, 又比如, 第一个鸡蛋仔第三次尝试的时候在X + (X-1) + (X-2)层时碎了,那么第二鸡蛋最坏需要尝试X-3, 加上第一个鸡蛋的3次,总共X次,那么这样能做到不论第一个鸡蛋在哪里碎了,最坏的情况下第一个鸡蛋尝试的次数
+ 第二个鸡蛋尝试的次数是一样的。
那么如何求X, X + (X -1) + (X-2) + + 1 = 100 =>> X(X+ 1)/2 = 100 ==>> X= 14.
这种方法在最坏的情况下得最少次数就是14.