算法(第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).