提出最短一天以达到目标的算法
Algorithm to come up with shortest day to reach a goal
我遇到了这个问题，但不太确定如何处理它。
我在想也许最好的方法是向东走 1 公里，然后向西走 2 公里，然后轻松走 3 公里...等等，直到我们到达出口。
我们站在一条左右走向的隧道中间。在距离我们未知的 K 公里处，是出口。我们不知道出口是在东边还是西边。也不知道到出口的距离K
我们想在尽可能短的时间内步行前往。假设我们每天可以步行 50 公里。给出一个算法，确保我们在 O(K) 天内到达出口。证明你的算法是正确的。用一个例子解释你的算法。
你走在正确的轨道上。你需要在向东和向西之间摆动，但不是将振幅增加一倍，而是每次增加一倍。
- 向西走1公里。
- Return回原位，向东2公里
- Return到家，向西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)).
我遇到了这个问题，但不太确定如何处理它。
我在想也许最好的方法是向东走 1 公里，然后向西走 2 公里，然后轻松走 3 公里...等等，直到我们到达出口。
我们站在一条左右走向的隧道中间。在距离我们未知的 K 公里处，是出口。我们不知道出口是在东边还是西边。也不知道到出口的距离K
我们想在尽可能短的时间内步行前往。假设我们每天可以步行 50 公里。给出一个算法，确保我们在 O(K) 天内到达出口。证明你的算法是正确的。用一个例子解释你的算法。
你走在正确的轨道上。你需要在向东和向西之间摆动，但不是将振幅增加一倍，而是每次增加一倍。
- 向西走1公里。
- Return回原位，向东2公里
- Return到家，向西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)).