现在的位置: 首页 > 综合 > 正文

扔鸡蛋问题

2013年08月26日 ⁄ 综合 ⁄ 共 716字 ⁄ 字号 评论关闭

问题: 有一幢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.

抱歉!评论已关闭.