如何从建筑物中扔出 2 个鸡蛋并用 ~c*sqrt(F) throws 找到 F 层？
How to throw 2 eggs from a building and find the floor F with ~c*sqrt(F) throws?
我正在阅读 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...的部分和）放下第一个鸡蛋。
然后在最后两层之间做线性搜索。
我正在阅读 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...的部分和）放下第一个鸡蛋。 然后在最后两层之间做线性搜索。