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

2022-07-28 08:58:27 浏览数 (1)

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老师写下下面的程序:

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

看起来不错。

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

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

F老师惊出一身冷汗。

小T笑一笑:

我来!

小T写下了这样的程序:

代码语言:javascript复制
: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,有没有办法写一个程序让两个机器人相遇?

0 人点赞