1.2　算法及其描述

在程序設計中，也經常涉及算法。瑞士著名計算機科學家Niklaus Wirth提出了程序定義的著名公式：程序=數據結構+算法。這個公式說明了程序與算法的關系，也足以說明算法在程序設計中的重要性。下面從算法的概念和描述方法兩個方面討論算法問題。

1.2.1　算法的概念

在日常生活中，做任何事情都是按照一定規則一步一步地進行的，例如，新生開學典禮就是按預設步驟一步一步進行，直到結束。這些預設步驟就是新生開學典禮的算法。

通常認為，算法就是對特定問題求解步驟的一種描述。算法應具備以下5個特點：

①有窮性。算法必須保證執行有窮步之后結束，不能無止境地執行下去。

②確定性。算法必須保證每一步必須具有確切的含義，不能有二義性。

③有效性。算法必須保證每一步操作都是可執行的。

④要有數據輸入。算法中操作的對象是數據，因此，算法應該提供數據輸入。

⑤要有結果輸出。算法是用來解決一個給定的問題，因此，算法應該提供結果輸出。

1.2.2　算法的描述方法

算法就是對特定問題求解步驟的一種描述。為了描述一個算法，可以用不同的方法。通常的方法包括自然語言、傳統流程圖、結構化流程圖、偽代碼等。

1.自然語言

自然語言就是人們日常使用的語言，可以是漢語、英語，或其他語言。

自然語言描述的算法通俗易懂，便于用戶間交流。但文字冗長，含義往往不太嚴格，需要根據上下文才能判斷其正確含義，容易出現歧義性。一般用來描述較簡單的算法。

例如，求sum=1+2+…+n。算法用自然語言描述如下：

算法設計

第一步：置初值，累加和sum置0，累加項i置1。

第二步：輸入待求和數的個數n。

第三步：求累加和，重復執行下面操作，直到i>n。

●　累加項：sum+i=>sum

●　求下一項：i+1=>i

第四步：輸出sum的值。

2.流程圖

流程圖就是借助一組專用的圖框和線條來描述算法，用圖框表示各種操作，用線條表示操作的執行順序。它的特點是直觀形象，易于理解。美國國家標準學會（ANSI）規定了一組常用的流程圖符號（見圖1-1），已被世界各國所采用。

①起止框：扁圓形，表示流程圖的開始或結束。

②處理框：矩形，表示各種處理功能，其內注明處理名稱或簡要功能。

③輸入/輸出框：平行四邊形，表示數據的輸入或輸出。

④連接點：表示兩部分流程圖的連接處。

⑤判斷框：菱形，表示判斷，注明判斷條件，只有一個入口，可以有多個選擇出口。

⑥流程線：箭頭，表示操作執行順序。

⑦注釋框：對流程圖中的某些框作補充說明，幫助閱讀流程圖。

例如，求sum=1+2+…+n。算法用流程圖描述如圖1-2所示。

3.偽代碼

流程圖描述算法直觀形象，易于理解。但畫起來比較費事，在設計一個算法時，可能需要反復修改，對流程圖的修改比較麻煩。流程圖適合描述一個算法，但在設計算法過程中使用不太理想（因為需要反復修改）。為了設計算法時方便，常使用一種稱為偽代碼（Pesudo Code）的工具。

偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。它如同一篇文章，自上而下地寫下來，每一行（或幾行）表示一個基本操作，不需使用圖形符號。因此，書寫方便，格式緊湊，容易理解，也便于向程序過渡。

例如，求sum=1+2+…+n。算法用類C語言的偽代碼描述如下：

算法設計

上面介紹了幾種常用的描述算法的方法，每種方法都有自己的特點，在程序設計中，讀者可以根據需要和習慣任意選用。筆者認為，基于“自然語言+偽代碼”相結合的思想是一種較好的算法描述方法，這種方法的基本思想是：算法的大框架采用自然語言描述，在重要步驟（核心步驟）中嵌入偽代碼。

例如，求sum=1+2+…+n。基于“自然語言+偽代碼”相結合的思想，其算法描述如下：

算法設計

第一步：輸入待求和數的個數n。

第二步：置初值，將累加器sum置0，累加項i置1。

第三步：求累加和，用C語言的類while結構描述如下。

第四步：輸出sum的值。