其中向左(右)指令每次能控制机器人向左(右)移动一步;条件判定指令能对机器人所在的位置进行条件测试,测试结果是如果对方机器人曾经到过这里就返回true,否则返回false;无条件跳转,类似汇编里面的跳转,可以跳转到任何地方。
分析:我尽量以最清晰的方式来说明这个问题(大部分内容来自ivan,big等人的讨论):
1、首先题目要求很简单,就是要你想办法让A最终能赶上B,A在后,B在前,都向右移动,如果它们的速度永远一致,那A是永远无法追赶上B的。但题目给出了一个条件判断指令,即如果A或B某个机器人向前移动时,若是某个机器人经过的点是第二个机器人曾经经过的点,那么程序返回true。对的,就是抓住这一点,A到达曾经B经过的点后,发现此后的路是B此前经过的,那么A开始提速两倍,B一直保持原来的一倍速度不变,那样的话,A势必会在|AB|/move_right个单位时间内,追上B。ok,简单伪代码如下:
start:
if(at the position other robots have not reached)
move_right
if(at the position other robots have reached)
move_right
move_right
goto start
再简单解释下上面的伪代码(@big):
A------------B
| |
在A到达B点前,两者都只有第一条if为真,即以相同的速度向右移动,在A到达B后,A只满足第二个if,即以两倍的速度向右移动,B依然只满足第一个if,则速度保持不变,经过|AB|/move_right个单位时间,A就可以追上B。
2、有个细节又出现了,正如ivan所说,
if(at the position other robots have reached)
move_right
move_right
上面这个分支不一定能提