设为首页 加入收藏

TOP

程序员――闲话链表追赶问题(二)
2014-11-23 21:58:24 来源: 作者: 【 】 浏览:1
Tags:程序员 闲话 追赶 问题
其中向左(右)指令每次能控制机器人向左(右)移动一步;条件判定指令能对机器人所在的位置进行条件测试,测试结果是如果对方机器人曾经到过这里就返回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

上面这个分支不一定能提

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇程序员――有关虚函数的一个问题 下一篇Muduo网络编程示例之零:前言

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: