扔塑料球问题

问题:

假设一座塔高100层,你手上有两个一模一样的塑料球,你的任务就是测试塑料球最高可以从几楼摔下而保持不坏,请给出你的策略及最少试验次数!

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

(想一想)

 

当看到这道题目的时候,马上想到的是二分法,不过细想一下是行不通的;如果你第一个球在50层摔坏了,那么第二球就必须从第1层老老实实的往上进行实验,假设目标楼层就是50层,那么这种策略就需要实验1次+49次=50次;
这种策略最坏情况需要实验次数为50次;显然不是最好的策略。

 

仔细思考,两个球,应该是第一个球来划分范围,第二个球来确定具体楼层,所以刚刚按50划分还是太大了;而后想到100层平均划分成10份,第一个球就去10楼、20楼、30楼...100楼扔,在哪层摔坏了就用第二个球在那个层对应的区间扔。
假设目标楼层是50层,那么第一球需要扔5次,第二个球从41层扔到49层也就是9层,结果是14次。
假设目标楼层是100层,那么第一个球需要扔10次,第二个球从91层扔到99层,结果是19次。
这种策略最坏情况需要实验次数为19次;比上一个策略好很多啦,但不知道是不是最好策略。

 

再仔细思考发现,上一个策略随着目标楼层的增高,实验次数也随之递增,那么就想到划分的步长随着楼层增高步长越短比较合适!于是就按如下划分:
1-14        (间距14)
15-27      (间距13)
28-39     (间距12)
40-50     (间距11)
51-60     (间距10)
61-69     (间距9)
70-77     (间距8)
78-84     (间距7)
85-90     (间距6)
91-95     (间距5)
96-99     (间距4)
100
将100层楼划分成上面12份,楼层间距从14递减至4,最后是第100层。
第一个球去14楼、27楼、39楼、50楼、60、69、77、84、90、95、99、100扔,在哪层摔坏了就用第二个球在那个层对应的区间扔。
这样划分的好处就是无论目标楼层在哪里,我扔球的实验次数不大于14次!不信你看:
假设目标楼层是50层,第一个球需要扔4次,第二个球从40层扔到49层,结果是14次。
假设目标楼层是99层,第一个球需要扔11次,第二个球从96层扔到98层,结果是14次。
这种策略最坏情况需要实验次数为14次;这应该就是最佳策略了吧!

 

最佳方案:根号下2倍的楼层=初识步长=最坏情况试验次数    (自己算的,未经验证,不知道对不对哈,求大神指教...)

6

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

扔塑料球问题
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close