我正在阅读 Robert Sedgewick 的算法书第 4 版，他有以下任务:
Suppose that you have an N-story building and 2 eggs. Suppose also that an egg is broken if it is thrown off floor F or higher, and unbroken otherwise. Your cost model is the number of throws. Devise a strategy to determine F such that the number of throws ~c √ F for some constant c.
任务的第一部分是在 2 √ N 步中找到 F，这是一个解决方案:
第 1 部分的解决方案:
- 要达到 2 * sqrt(N)，请将鸡蛋放在 sqrt(N)、2 * sqrt(N)、3 * sqrt(N)、...、sqrt(N) * sqrt(N) 层。 (为了简单起见，我们在这里假设 sqrt(N) 是一个整数。)
- 假设鸡蛋在 k * sqrt(N) 层破裂。
- 对于第二个鸡蛋，您应该在区间 (k-1) * sqrt(N) 到 k * sqrt(N) 中执行线性搜索。
- 总共你将能够在最多 2 * sqrt(N) 次试验中找到 F 层。
他还为 ~c √ F 部分(第 2 部分)提供了提示:
Hint for Part 2: 1 + 2 + 3 + ... k ~ 1/2 k^2.
那么在 ~c √ F 步内完成的算法是什么？
最佳答案
从第 1、3、6 层...(1、2、3...的部分和)放下第一个鸡蛋。 然后在最后两层之间进行线性搜索。
关于algorithm - 如何从建筑物中扔出 2 个鸡蛋并用 ~c*sqrt(F) throws 找到 F 层？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29965430/