墙上的门问题

zhoubug

你面前是一堵朝两个方向无限延伸的墙。墙上有一扇门，但你并不知道门离你有多远，也不知道门位于哪个方向。你只有在走到门门前才能看到它。假设从当前位置到门要走n(事先并不知道n的大小）步，请设计一个算法，使你最多走O(n)步就能遇到门.

解法在网上找到拉，不过不清楚怎么想到的答案，具体的算法设计思路是什么？

zhoubug

贴上网上的一个解答：

定义变量c,置为0.
首先,任意选择一个方向x.
a): 沿着x向前走2^c步.
b): 是否发现门? 若发现了,结束.
c): 若没发现,则向反方向走2^(c+1)-1+2^c步.
d): 是否发现门? 若发现了,结束.
e): ++c,返回a).

复杂度分析:
若2^(k-1) <n <=2^k.
我们考虑最差的情况:如果我们开始选的方向错了,那么,我们最多要走k+1个来回.
每个来回我们走了2^c+2^(c+1)-1+2^c=2^(c+2)-1步 (0 <=c <=k).
于是,总共要走: 2^2+2^3+...+2^(k+2)-(k+1)步.
求和,得到了:4*(2^(k+1)-1)-(k+1).
而4*(2^(k+1)-1)-(k+1) <4*2^(k+1) <16*2^(k-1) <16n.
于是,复杂度可以表示为O(n).

cjaizss

先往一个方向走1m,如果过程中没找到门，再往反方向走3m,如果还没找到门，再反方向走9m，每次走的是刚才的三倍长度