知识点
- 扔两个鸡蛋
题目
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).