插播：一道有趣的程序题 (中)

在上一期中，F老师遇到了一个有意思的题目，在小T同学的帮助下得到了答案。

F老师把小T同学送走以后，思考了以下几个推广的问题：

1. 如果机器人运行的轨道是环形的，环的周长步数为X，这种算法最坏情况下，两个机器人需要多少个周期才能相遇？

2. 开放问题：我们把问题扩展到二维平面，并为机器人增加两条指令：up (向上走)，down (向下走)，在两个机器人无法通信的前提下，有没有办法让两个机器人相遇？

3. 问题2中，如果假设每个机器人的X坐标与Y坐标的差，绝对值小于2，有没有办法写一个程序让两个机器人相遇？

我们先看第一个问题。

如图，机器人A和机器人B空降在一个环形离散轨道上，轨道的步数为X，两个机器人的距离为Y。

由于轨道为环形，从另一个方向看，两个机器人之间的距离是(X-Y)。

两个机器人都执行如下的程序：

:START
  left    //向左一步走 
  left    //向左再走一步
jmark :START  //如发现左边追击目标的标记，则跳转到开始，并向左走
  right  //如还没有发现追击目标则回退一步
  mark    //做标记，如果自己是追击目标则留下标记，供追击者检测
jmark :START  //检测到自己的标记，跳转回开始，程序形成循环

执行的结果是，一开始两个机器人以相等的速度(进二退一)，在轨道上互相追逐对方。

如果机器人A发现了机器人B的轨迹，机器人A将全速前进，直到追上B。

——且慢，这里面有个坑！

由于轨道是环形，如果A和B刚好位于环形轨道的两端(也就是Y=X-Y)，A发现B轨迹时，B也发现了A轨迹，两个机器人同时全速前进，这样一来，两个机器人永远无法相遇！

F老师由于治学不严谨，被小T同学嘲笑以后，把题目改了：

机器人A和机器人B空降在周长为X的环形轨道上，运行前文所述的程序，需要满足什么样的条件，机器人A和机器人B才可能相遇？

让我们进行推算：

假设机器人A和B的距离为Y，那么，当经过(Y-1)个周期，A与B各前进了(Y-1)步，此时，A发现了B的踪迹，此时A加速运行，而B执行后退一步，二者的距离变为Y-1，进入A全速追击B的过程。

在A全速追击B的过程中，假定B一直没有发现A留下的踪迹，又过了Y-1个周期，A与B相遇。

在这期间，B走了Y-1步，但由于判定标记的jmark指令在回退一步之前执行，需要保证B走了Y步依然没有发现A的踪迹。

总计在整个追击过程中，A走了3Y-1步，而B走了2Y-1步。由于我们设定的条件是B发现了A的踪迹，才从进二退一的前进方式改为全速前进，也就是说，A追上B时，是没有走完整个环形轨道的。

因此，我们得到了结论：

X > 3Y-1时，A可以追上B。

在下一期中，我们再分析问题2和问题3。