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

她从楼上扔鸡蛋

2017年12月25日 ⁄ 综合 ⁄ 共 570字 ⁄ 字号 评论关闭

题目:栋建筑物高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 ... 的跳跃方式丢,最差情况下应该最小。

抱歉!评论已关闭.