| 序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
|---|
John丢失了他的引以为傲的奶牛Bessie，他需要找到她！
幸运的是，农场只有一条长途径，而John知道Bessie一定在这条路上的某个地方。 如果我们将路径视为数轴，那么John现在位于x，Bessie目前位于y（John并不知道）。 显然如果John只知道Bessie所在的地方，他可以直接走到她身边，经过 | x - y | 距离。 不幸的是，外面黑暗，John看不到任何东西。 他能找到Bessie的唯一方法是来回走动，直到他最终达到她的位置。
为了找出在他的搜索中来回走走的最佳策略，John咨询计算机科学研究文献，意外发现，这个确切的问题不仅仅是计算机科学家过去的研究，实际上还有个名字叫 “丢失的奶牛问题”（这其实是真的！）。
John找到Bessie的建议解决方案是移动到位置x + 1，然后反向，并移动到位置x-2，然后到位置x + 4，依此类推，在“zig zag “模式下，每一步走完后，他离起始位置距离为上一步的两倍。 正如他在研究解决失去的牛问题的算法时所读的那样，这种方法能保证，最差情况下他走过的距离为| x-y |的9倍（这也是真的）。
John好奇地验证这个结果。 给定x和y，根据上述”zig zag”搜索策略，请计算当他找到Bessie时，他经过的总距离。