NO IMAGE

趕集網面試題

http://blog.csdn.net/v_july_v/article/details/6447013

題目描述:
    在一條左右水平放置的直線軌道上任選兩個點,放置兩個機器人,請用如下指令系統為機器人設計控制程式,使這兩個機器人能夠在直線軌道上相遇。(注意兩個機器人用你寫的同一個程式來控制)
    指令系統:只包含4條指令,向左、向右、條件判定、無條件跳轉。其中向左(右)指令每次能控制機器人向左(右)移動一步;條件判定指令能對機器人所在的位置進行條件測試,測試結果是如果對方機器人曾經到過這裡就返回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

上面這個分支不一定能提速的。why?因為如果if條件花的時間很少,而move指令發的時間很大(實際很可能是這樣),那麼兩個機器人的速度還是基本是一樣的。

那作如何修改呢?:

start:
if(at the position other robots have not reached)
    move_right
    move_left
    move_right
if(at the position other robots have reached)
    move_right
goto start

——-

這樣改後,A的速度應該比B快了。

      3、然要是說每個指令處理速度都很快,AB豈不是一直以相同的速度右移了?那到底該作何修改呢?請看:

go_step()
{
   向右
   向左
   向右
}
——–
三個時間單位才向右一步

go_2step()
{
   向右
}
——