>> 设计一种方法使运气最差的情况下确定刚好摔得破球的楼层数 我无法看出什么情况下运气最差？ 因为我总可以从第一层开始往下仍球。然后一层一层往上加，直到球摔碎了为止。所以，我只需要一个球。 我的理解什么地方不对？ 还是问题应该为：设计一个最佳方法（尽可能少爬楼）确定楼层数？ |
楼主的意思, 是设计出一个方案, 使得在运气最差的情况下爬楼的次数最少, 是吗? 以第4个为例子.(6个球, 1000层). 先拿第一个球在第500层扔, 如果碎了, 那么下到250层;如果没碎, 上到750层。 假设在250层扔第二个球，如果碎了, 那么下到125层;如果没碎, 上到375层。 以此规律继续下去，总之每次扔球无论碎与没碎，都淘汰掉一半的楼层。 这样扔掉第五个球的时候，还应该剩下32层无法决定，（比如：500->250->125->63->32, 其它情况类似). 这32层不一定从第几层开始，也许是第1层到第32蹭，也许是第64层到第96层，但总层数是32。 这时候拿出第六个球，从这32层里最底下一层开始，一层层地扔，直到找到刚好摔破的那一层。 这个方法在运气最差的情况下，一共要爬5+32=37层楼。 |
我认为此题不宜单纯的使用二叉树方法，因为球的数量有限。摔坏了就没有了。而楼层为100层。 我觉得高中版应该可以这样：（保证找到某个特定的楼层） 为了充分利用2个球，需要从第10层开始，这样可以尽可能的少跑路。因为一共100层，100=102 去10楼仍球，如果碎了，那么第二个球只能从一楼开始一层一层往上加。 如果不碎，还剩90层，去间隔9层楼（90距离81更近一些），也就是去，19层楼。。。。。 如果不碎，还剩81层，去28楼（9x9=81）。。。。 如果不碎，还剩72，去36楼（8x8=64)..... 。。。。 也就是说下一次间隔的楼层是剩下楼层数的平方根。这样可以保证跑的次数最少 本贴由[新用户]最后编辑于：2007-3-27 18:3:20 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |