100层楼扔球

水母的智商 · 发表于 2007-3-27 13:33:14

100层楼一座，强度一样的玻璃球若干。

高空坠球有可能导致玻璃球破裂且球的破裂仅受高度影响（若10层楼摔得破，11层一定也可以。9层未知是否能摔破。并且在未测试时不能肯定球是否一定会在某一层破裂，即有机会100层也不破）

设计一种方法使运气最差的情况下确定刚好摔得破球的楼层数

1小学版：你有无限多的玻璃球

2初中版：你有6个玻璃球

3高中版：你有2个玻璃球

4大学版：你有6个玻璃球，但是某没事找事的工程师把楼加盖了900层，即现在是一座1000层高楼

（注意：玻璃球破裂后就不能再使用）

新用户 · 发表于 2007-3-27 20:46:47

>> 设计一种方法使运气最差的情况下确定刚好摔得破球的楼层数

我无法看出什么情况下运气最差？

因为我总可以从第一层开始往下仍球。然后一层一层往上加，直到球摔碎了为止。所以，我只需要一个球。

我的理解什么地方不对？

还是问题应该为：设计一个最佳方法（尽可能少爬楼）确定楼层数？

人在天涯 · 发表于 2007-3-28 01:02:34

楼主的意思, 是设计出一个方案, 使得在运气最差的情况下爬楼的次数最少, 是吗?

以第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层楼。

水母的智商 · 发表于 2007-3-28 01:23:21

是这样理解的。球如果没碎可以反复使用，否则只能用一次。高中版是个关键

新用户 · 发表于 2007-3-28 02:01:55

我认为此题不宜单纯的使用二叉树方法，因为球的数量有限。摔坏了就没有了。而楼层为100层。

我觉得高中版应该可以这样：（保证找到某个特定的楼层）

为了充分利用2个球，需要从第10层开始，这样可以尽可能的少跑路。因为一共100层，100=10²

去10楼仍球，如果碎了，那么第二个球只能从一楼开始一层一层往上加。

如果不碎，还剩90层，去间隔9层楼（90距离81更近一些），也就是去，19层楼。。。。。

如果不碎，还剩81层，去28楼（9x9=81）。。。。

如果不碎，还剩72，去36楼（8x8=64).....

。。。。

也就是说下一次间隔的楼层是剩下楼层数的平方根。这样可以保证跑的次数最少

本贴由[新用户]最后编辑于：2007-3-27 18:3:20

水母的智商 · 发表于 2007-3-28 07:29:55

思路是对的，但是不尽如此。想要尽量减少扔球的次数应该[用某种方法]分配上楼的层数

水母的智商 · 发表于 2007-3-28 07:30:28

补充终极版，n层楼x个球

husonghu · 发表于 2007-3-30 22:57:38

husonghu · 发表于 2007-3-30 22:59:16

		自动登录	找回密码
密码			立即注册

动态微博