路径选择算法

Question

我有个插话的问题要跟你分享。让我们假设你驾驶的是一辆汽车，你偶然发现了一个十字路口，有三种可能的选择方式。你需要汽油，你需要找到一个加油站，但在一个方向上只有一个加油站。任务是找到一个寻找加油站的算法。但是，假设x是加油站和十字路口之间的距离，你驾驶的总距离必须是x的线性函数。

我已经想了好几个小时了，有什么想法吗？

编辑:你不知道x在开始！

Answer 1

朝一个方向行驶1公里，然后返回。然后向另一个方向行驶2公里，然后返回。然后继续4，8，16等，直到你找到加油站。

如果加油站在2^n到2^(n+1)公里之间，你将开车总共不超过

S = 2 * (1+2+4+...+2^(n+3)). 

所以，S < 2 * 2^(n+4) < 32 * 2^n < 32x (因为x > 2^n)。因此，行驶里程将低于32x公里。