算法练习(78): 扔两个鸡蛋(1.4.25)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 扔两个鸡蛋

题目

1.4.25 扔两个鸡蛋。和上一题相同的问题，但现在假设你只有两个鸡蛋，而你的成本模型则是扔鸡蛋的次数。设计一种策略，最多扔 2√(N) 次鸡蛋即可判断出 F 的值，然后想办法把这个成本降低到 ~c√(F) 次。这和查找命中（鸡蛋完好无损）比未命中（鸡蛋被摔碎）的成本小得多的情形类似。

---

1.4.25 Throwing two eggs from a building. Consider the previous question, but now suppose you only have two eggs, and your cost model is the number of throws. Devise a strategy to determine F such that the number of throws is at most 2 N, then find a way to reduce the cost to ~c F. This is analogous to a situation where search hits (egg intact) are much cheaper than misses (egg broken).

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。