本文主要是介绍算法趣题 : 检测玻璃瓶的强度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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)!】
这篇关于算法趣题 : 检测玻璃瓶的强度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!