2.1.1 算法及其表示

雖然用程序設計語言表示算法是程序設計的最終目的，但由于程序設計語言是一種形式化語言，要求嚴格，在初學階段或設計比較復雜的問題時很難直接使用，因此，要了解和掌握幾種直接表示算法的方法。

1.自然語言描述

采用自然語言描述算法，通俗易懂，但不太嚴格，煩瑣冗長，不直觀，不清晰。

【例2.1】 有兩個存儲單元a和b，要求將它們的值互換。

按存儲器的性質，如果將單元a的值直接送到單元b中，那么就會覆蓋b原來的內容，因此，需要借助一個臨時單元c來交換。

具體算法如下。

步驟1：將單元a的值送給單元c。

步驟2：將單元b的值送給單元a。

步驟3：將單元c的值送給單元b。

【例2.2】 求1+2+3+4+…+10。

假設用存儲單元S存放累加和，具體算法如下。

步驟1：把0存入S單元中。

步驟2：把1加到S中（即取S中的內容0加1后得到1，再把1送回S單元中）。

步驟3：把2加到S中。

步驟4：把3加到S中。

……

步驟10：把9加到S中。

步驟11：把10加到S中。

步驟12：把S中的結果輸出。

這樣的算法雖然正確，但不科學，不實用。可以設一個計數器單元n，每重復一次n增1，直到n大于10為止，求和操作可以改為“n+S送S”。修改后的算法如下：

步驟1：將0送到S中。

步驟2：將1送到n中。

步驟3：把n的值加到S中。

步驟4：n增1。

步驟5：若n≤10則轉回步驟3，否則執行步驟6。

步驟6：輸出S的值。

改進后的算法很科學，是適合編程的算法。

由于自然語言描述容易產生歧義，因此，除了很簡單的問題外，一般不用自然語言表示算法。

2.流程圖

流程圖通常采用一些幾何圖形來代表各種類型的操作，在圖形內標明文字或符號來表示操作的內容，并用箭頭來表示操作的順序。圖2.1給出了流程圖中使用的圖形符號及代表的含義。

圖2.2所示為例2.2的流程圖。

用流程圖表示算法，直觀形象，易于理解。但由于流程圖允許使用箭頭隨意跳轉，對表示算法的層次結構非常不利，并且流程圖所占的篇幅較大，作圖工作量也很大。

3.N-S圖

針對流程圖存在的缺點，1973年，美國的計算機科學家I. Nassi和B. Shneiderman提出了結構化程序設計的流程圖，因為他們二人的名字是以N和S開頭的，所以稱為N-S圖。相對于流程圖，N-S圖更能體現結構化程序設計的思想，因此，本書推薦使用N-S圖。

N-S圖去掉了傳統流程圖中的箭頭，全部算法寫在一個大的矩形框內，組成N-S圖的是一系列“方塊”，因此N-S圖又叫盒圖。N-S圖規定了一些圖形元素，用來表示結構化程序設計的3種基本結構——順序結構、選擇結構、循環結構。一個算法可由若干個代表基本結構的圖形元素像搭積木一樣構造而成。

（1）順序結構

順序結構是一系列順序執行的運算和處理。順序結構的N-S圖如圖2.3所示，其中，A和B分別代表一個基本的操作。

（2）選擇結構（判斷結構、分支結構）

選擇結構通常是根據一個條件P是否成立來選擇下一步應該執行哪一種處理。圖2.4所示為選擇結構的N-S圖，其中，T表示條件成立，F表示條件不成立。

（3）循環結構（重復結構）

循環結構根據條件P是否成立來判斷是否重復執行操作A。通常有兩種結構形式，一種是“先判后做”，另一種是“先做后判”。

“先判后做”稱為當型循環：表示當條件P成立時就執行A，然后返回再判斷P是否成立，若成立則再重復執行A，……，重復下去，直到條件P不成立。其N-S圖如圖2.5（a）所示。

“先做后判”稱為直到型循環：表示先執行A，再判斷條件P是否滿足，不滿足則重復執行A，……，直到條件成立。其N-S圖如圖2.5（b）所示。

結構化程序設計的三種基本結構具有以下共同的特點：

● 只有一個入口；

● 只有一個出口；

● 結構內的每一部分都有機會被執行到；

● 結構內不存在“死循環”。

圖2.6所示為求1～10的10個正整數的和的算法描述（見例2.2），圖2.7所示為求10個任意整數中的最大數的算法描述。讀者可以通過這兩個例子仔細體會順序、選擇和循環這三種基本結構的特點。