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 //检测到自己的标记,跳转回开始,程序形成循环
这样,被追击者执行以下循环:
由于被追击的机器人不可能发现追击者的标记,它会一直执行这个循环。
而追击者的执行顺序是:
如此循环若干次,直到马超发现了曹操——
追击者发现了被追击者。
执行顺序是:
走两步,发现标记,走两步,发现标记,走两步………………
很快,解放军就追上了黄维兵团。
机器人Q就追上了机器人P。
小T蔻尔一笑,仿佛在嘲笑:
F老师,你的人设崩塌了,技术大拿的画皮之下原来也是油腻中年男!
F老师痛定思痛,决定把这道题做改造: