Ｉｎｓｔｒｕｃｔｉｏｎｓ問題算法分析

摘要：ACM/ICPC（ACM International Collegiate Programming Contest）是ACM國際大學生程序設計競賽的簡稱，這是世界計算機領域的一項權威賽事。該文就是針對ACM國際大學生程序設計中的一道題目的解法進行算法分析，道題目的名字叫做“Instructions”。通過對原問題進行理解，通過暴力方法，動態遞推法，對原問題進行算法分析和實現，然后對算法進行測試和總結，從而滿足題目的要求。

關鍵詞：Instructions；算法； 暴力方法；動態遞推法

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)22-686-02

Algorithm Analysis of the Problem \"Instructions\"

MA Biao-biao

(College of Mathematical Sciences， Anhui University，Hefei 230601，China)

Abstract: ACM/ICPC is the abbreviation of ACM International Collegiate Programming Contest. This is authoritative match in the field of computer. This article aims to analyze the algorithm of a problem ofACM/ICPC. The name of this problem is \"Instructions\". Through a detailed understanding， violent means and the method of dynamic recurrence， we analyze， realize and test the original algorithm such that our algorithm meet the requirement of the problem.

Key words: Instructions; algorithm; forcible method; the method of dynamical recurrence

1 問題提出

1.1 題意分析

題目的大意是這樣的，一臺老的探測機器人，它的任務是對一塊土地進行探測，包括了四條指令，分別為“Forward”，“ Turn Left”，“ Turn Right”，“Scan”當輸入指令為“Forward”時則機器人向它所面向的方向前進一格；當輸入指令為“Turn Left”時，則機器人在原地向左轉向；當輸入指令為“Turn Right”時，則機器人在原地向右轉向；當輸入指令為“Scan”時，則機器人探測它所面向的方向的前一塊區域。

現在有一臺新的機器人代替老的機器人要完成相同的任務，但是它只有兩條指令，為“Move”，“Scan”，移動指令可以讓機器人朝它所在位置的任何一個方向移動任何的距離，探測指令則可以讓機器人探測它四周的任何一塊區域。問題是當新的機器人代替老機器人時，如何讓轉換它們之間的命令。

題目的輸出要求是找出舊的指令轉換成新的指令后，新指令最少有多少條。并且機器人要求站在同一起點，探測位置和順序都不能變。

題意如圖1所示：

■

圖1

圖中，數字表示老的機器人走過的路線，紅色的*表示探測的區域，紅色的數字表示探測的順序，可以看出，老的機器人如果要完成上面的命令，要執行8條指令，分別為ForwardForwardTurn LeftForwardScanTurnRight ScanForward，如果是新的機器人完成，則只關心起點位置和探測位置及探測順序，要完成上面的任務有許多種走法，我們要做的就是找出使得新的指令最少的那種方法，根據圖1，我們不難看出，當新機器人在圖中#位置進行探測時，所需要的指令都是4條，分別為Move Forward 2 Move Left 1 Scan ForwardScan Right 。探測的區域最多有1000組，并且有10次輸入。

1.2 問題模型

根據上面的問題分析，我們可以總結出該問題的問題模型：有最多1000組數據，按順序記錄了探測點的位置，我們假設則每個位置可以直接探測的站位為探測點的上、下、左、右。根據描述，我們可以記錄各個站位的坐標，然后把每個站位到后一站位（包括探測過程）所需要的步驟相加，則最后得出到各個站位，探測完成所需要的總步數的所有可能。如圖2所示。

2 算法分析

2.1 暴力方法

按照圖2的方法，對每一個掃描點都要進行4種比較，并且記錄，隨著掃描點的增加，記錄的數組越來越大，并且計算量巨大，一個掃描點為4，兩個掃描點就為16，則N個掃描點為4N種情況，而最多的有1000個掃描點如果對每個掃描點都用這種方法計算的話，程序的響應時間必定很長。所以這種方法是不可行的。

2.2 動態規劃法

前面介紹的方法，經過我們分析，效率太低，我們必須尋找其他更好的辦法來解決這道問題，由上面方法所產生的問題我們該如何解決呢？是否可以找出一個不把所有情況的列出的方法呢，下面就采用一種動態遞推的方法解決問題，如圖3所示。

從圖3可以看出，每個掃描點還是4種情況，但是當對當前掃描點進行推算時，都要和以前推算出的數值進行比較，如果比以前的數值大，則舍棄，如果比以前的數值小則把數值更新，換成小的，依次類推，當推到最后一個掃描點時，得到的數值一共有4個，即從4個方向所有最小的數值的累加。然后再比較這四個中的數值哪個最小，便得出了題目的答案。

2.2.1 算法設計

由上面的分析，我們可以寫出大體的算法：

Int top，left，right，down; //定義上下左右四種情況的數值累加

Int Number;//掃描點的個數

Input(n);//輸入數值為老語句數量

Input(char Lan);//輸入老語句

Process(int n){//記錄過程

If(Forward) go Forward;//前進一步

If(Turn Left) Turn Left;//轉向

If(Turn Right) Turn Right ;//轉向

If(Scan) note the row and columnand

Number++;//記錄行列并切Number++

}

Solution(){//解決過程

For(int i=0;i

Top(i){top=top(i-1)+top; left=left(i-1)+top; //累加前一位置到當前位置

right=right(i-1)+top; down=down(i-1)+top}//數值 為Top

Left(i){ top=top(i-1)+top; left=left(i-1)+top; //累加前一位置到當前位置

right=right(i-1)+top; down=down(i-1)+top }//數值 為Left

Right(i){ top=top(i-1)+top; left=left(i-1)+top; //累加前一位置到當前置

right=right(i-1)+top; down=down(i-1)+top }//數值 為Right

Down(i){ top=top(i-1)+top; left=left(i-1)+top; //累加前一位置到當前位置

right=right(i-1)+top; down=down(i-1)+top }//數值 為Down

}}

Sqsort(top，left，right，down){

Return min(top，left，right，down);} //選出數值最小的

StepNumber=min(top，left，right，down); //結果

Output(StepNumber);//輸出

3 算法比較和總結

根據上面的算法，寫出代碼。下面是是根據算法對程序的測試過程：

看輸入是否符合題目要求。檢查代碼的中間過程是否出現異常。

查看輸出是否符合題目要求。本題特別要注意：前個一個Case是要和后一個Case有空行的，最后一個Case是沒有空行的，并且，機器人可以重復對同一個區域進行檢查，所以不能排除前個一個掃描點和后一個掃描點的重合計算。

參考文獻：

[1] Cormen T H.， Leiserson C E.， Rivest R L.， et al. Introduction to Algorithms[M].2版.北京:高等教育出版社，2002.

[2] 譚浩強.C程序設計[M].2版.北京:清華大學出版社，1999.

[3] 鄭莉，董淵. C++語言程序設計[M].2版.北京:清華大學出版社，2001.

[4] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京:清華大學出版社，1997.

[5] 白宇.余數問題的兩種算法分析[J].電腦與電信，2007(5):27-28.