算法趣题 : 检测玻璃瓶的强度"/>
算法趣题 : 检测玻璃瓶的强度
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)!】
更多推荐
算法趣题 : 检测玻璃瓶的强度
发布评论