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

算法趣题 : 检测玻璃瓶的强度

2013年10月03日 ⁄ 综合 ⁄ 共 353字 ⁄ 字号 评论关闭

Description

对玻璃瓶做强度测试,设地面高度为0,从0 向上有n 个高度,记为1,2,…,n,其中
任何两个高度之间的距离都相等。如果一个玻璃瓶从高度i 落到地上没有摔破,但从高度i+1
落到地上摔破了,那么就将玻璃瓶的强度记为i

Question :

1) 当玻璃瓶的数量足够多时,需要测试多少次??【Hint:二分测试,肯定O(logn)的】

2) 当玻璃瓶的数量为 K (K>=1) 时,需要测试多少次呢?

Solution:

1)的解决方案非常清晰,用二分检测就可以了;

但我们可以附加一个问题: 二分检测最多会摔坏多少个瓶子呢? 很自然,最多摔坏 logn个瓶子.

那么,给出2)的解答时,我们有个隐含的假设: K <logn ;否则,直接二分检测就可以了.

2) solution : 【HInt: 2个瓶子时效率是sqrt(n)!

 

 

 

抱歉!评论已关闭.