提出最短一天以达到目标的算法

Question

我遇到了这个问题，但不太确定如何处理它。

我在想，也许最好的方法是向东走 1 公里，然后向西走 2 公里，然后轻松走 3 公里……以此类推，直到我们到达导出。

我们站在一条左右走向的隧道中间。在距离我们未知的 K 公里处，是导出。我们不知道导出是在东边还是西边。也不知道到导出的距离K。

我们想在尽可能短的时间内步行前往。假设我们每天可以步行 50 公里。给出一个算法，确保我们在 O(K) 天内到达导出。证明你的算法是正确的。用一个例子解释你的算法。

Answer 1

您走在正确的轨道上。您需要在向东和向西之间摆动，但不是将振幅增加一倍，而是每次增加一倍。

1. 向西行驶 1 公里。
2. 返回原位，向东行驶2公里。
3. 回到家，向西走4公里。...

这将确保您在 O(K) 天内到达导出。这是因为，如果 K 是 2^p，那么在到达导出之前，您最多可以行驶 O(2^p) 公里。

例如:如果 K = 2^n + 1，最坏的情况可以是:
1
1 + 2
2 + 4
4 + 8
8 + 16
...
2^(n) + 2^(n+1)
2^(n+1) + 2^n + 1
(O(9K))。