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

F老师有一个朋友，是个妹子，叫小T，有天找到F老师问一个问题：

有一种机器人只支持4条指令：

left —— 向左一步走

right —— 向右一步走

mark —— 在自己位置做标记

jmark :LABEL —— 检查自己位置是否有标记，如有，则跳转到LABEL标号处。

如果在一维整数数轴上，随机空降两个机器人，并且固化了相同的由这四条指令构成的程序，那么，如何编写这个程序，使得两个机器人能够相遇？

F老师进行了深入的思考以后，觉得这两个机器人永远不可能相遇——

假设让两个机器人都向左移动并做标记，机器人Q在看见机器人P的标记时，每追一步，机器人P也向前一步。

因此，机器人Q永远无法追上机器人P。

F老师正准备回答小T，顺便跟妹子炫耀一下自己学过的“阿喀琉斯永远追不上乌龟”的“芝诺悖论之追龟辩”，突然，大脑中一道灵光闪过——

如果机器人P看见机器人Q的标记时，加速追赶呢？

虽然机器人没有加速追赶的指令，但如果让前面的机器人减速走呢？

F老师想到了爷爷讲过的故事——

在淮海战役中，解放军某部奉命追击国民党军黄维兵团。黄维兵团虽然拥有汽车，每天可行进100公里，但由于行军路上每前进20公里，遇到游击队骚扰被吓得后退10公里，很快就被每天步行50公里的解放军追上包围，并且战败集体当了俘虏。

所以，我们可以让前面的机器人每走2步回退一步，后面的机器人发现前面机器人踪迹时全速前进！

F老师写下下面的程序：

:START
  left     //向左一步走
  mark    //做标记
  left    //再向左一步走
  jmark: START  //如果发现有标记，说明发现了追击目标，保持全速前进
  right  //未发现目标则向右一步走

看起来不错。

F老师正在偷偷开心，准备享受妹子崇拜的目光，小T发现了问题：

F老师，不对呀，右边的机器人只走两步回退一步，找不到追击目标就不走了，程序无法继续！

F老师惊出一身冷汗。

小T笑一笑：

我来！

小T写下了这样的程序：

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

这样，被追击者执行以下循环：

1. 走两步
2. 回退一步
3. 做标记

由于被追击的机器人不可能发现追击者的标记，它会一直执行这个循环。

而追击者的执行顺序是：

1. 走两步
2. 回退一步
3. 做标记

如此循环若干次，直到马超发现了曹操——

追击者发现了被追击者。

执行顺序是：

走两步，发现标记，走两步，发现标记，走两步………………

很快，解放军就追上了黄维兵团。

机器人Q就追上了机器人P。

小T蔻尔一笑，仿佛在嘲笑：

F老师，你的人设崩塌了，技术大拿的画皮之下原来也是油腻中年男！

F老师痛定思痛，决定把这道题做改造：

1. 如果机器人运行的轨道是环形的，环的周长步数为X，这种算法最坏情况下，两个机器人需要多少个周期才能相遇？
2. 开放问题：我们把问题扩展到二维平面，并为机器人增加两条指令：up (向上走)，down (向下走)，在两个机器人无法通信的前提下，有没有办法让两个机器人相遇？
3. 问题2中，如果假设每个机器人的X坐标与Y坐标的差，绝对值小于2，有没有办法写一个程序让两个机器人相遇？