1.2　算法與程序設計

所謂算法，是指為解決某個特定問題而采取的確定且有限的步驟。

對于一個問題，如果可以通過一個計算機程序，在有限的存儲空間內運行有限的時間而得到正確的結果，則稱這個問題是算法可解的。但是算法不等于程序，也不等于計算方法。當然，程序也可以作為一種描述，但通常還需考慮很多與方法和分析無關的細節問題，這是因為在編寫程序時要受到計算機系統環境的限制。通常程序的編制不可能優于算法的設計。

1.2.1　算法的基本特征

作為一個算法，一般具有以下幾個特征。

（1）可行性

針對實際問題設計的算法，人們總是希望得到滿意的結果。但一個算法又總是在某個特定的計算工具上執行的，因此，算法在執行過程中往往受到計算工具的限制，使執行結果產生偏差。例如，在進行數值計算時，如果某計算工具具有7位有效數字，則在計算

X=10¹²，Y=1，Z=-10¹²

3個量的和時，如果采用不同的運算順序，就會得到不同的結果，即：

X+Y+Z=10¹²+1+（-10¹²）=0

X+Z+Y=10¹²+（-10¹²）+1=1

而在數學上，X+Y+Z與X+Z+Y是完全等價的。因此，算法與計算公式是有差別的。在設計一個算法時，必須要考慮它的可行性，否則是不會得到滿意結果的。

（2）確定性

算法的確實性，是指算法的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。這一性質也反映了算法與數學公式的明顯差別。在解決實際問題時，可能會出現這樣的情況：針對某種特殊問題，數學公式是正確的，但按此數學公式設計的計算過程可能會使計算機系統無所適從。這是因為，根據數學公式設計的計算過程只考慮了正常使用的情況，而當出現異常情況時計算機就不能適應了。

（3）有窮性

算法的有窮性，是指算法必須能在有限的時間內完成，即算法必須能在執行有限個步驟之后終止。數學中的無窮級數，在實際計算時只能取有限項，即計算無窮級數數值的過程只能是有窮的。因此一個數的無窮級數表示只是一個計算公式，而根據精度要求確定的計算過程才是有窮的算法。

算法的有窮性還應包括合理的執行時間的含義。因為，如果一個算法需要執行千萬年，顯然就失去了實用價值。

（4）輸入

一個算法可以有零個或多個輸入。由于在計算機上實現的算法是用來處理數據對象的，因此在大多數情況下這些數據對象需要通過輸入來得到。

（5）輸出

一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。

一個算法是否有效，還取決于為算法所提供的情報是否足夠。通常，算法中的各種運算總是施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態，這是算法執行的起點或依據。因此，一個算法的執行結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。當輸入不夠或是輸入錯誤時，算法本身也就無法執行或導致執行出錯。一般來講，當算法擁有足夠的情報時，此算法才是有效的，而當提供的情報不夠時，算法可能失效。

綜上所述，所謂算法，是一組嚴謹的定義運算順序的規則，并且每一個規則都是有效的，且是確定的，此順序將在有限的次數下終止。

1.2.2　算法的基本要素

一個算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是算法的控制結構。

（1）算法中對數據對象的運算和操作

每個算法實際上是按解題要求從環境能夠進行的所有操作中選擇合適的操作所組成的一組指令序列。因此計算機算法就是計算機能處理的操作所組成的指令序列。

通常，計算機可以執行的基本操作是以指令的形式描述的。一個計算機系統所能執行的所有指令集合稱為該計算機系統的指令系統。計算機程序就是按解題要求從計算機指令系統中選擇合適的指令所組成的指令序列。在一般的計算機系統中，基本的運算和操作有以下4種。

①算術運算：主要包括加、減、乘、除等運算。

②邏輯運算：主要包括“與”“或”“非”等運算。

③關系運算：主要包括“大于”“小于”“等于”“不等于”等運算。

④數據傳輸：主要包括賦值、輸入、輸出等操作。

（2）算法的控制結構

一個算法的功能不僅僅取決于所選用的操作，還與各操作之間的執行順序有關。算法中各操作之間的執行順序稱為算法的控制結構。

算法的控制結構給出了算法的基本框架，它不僅決定了算法中各操作的執行順序，還直接反映了算法的設計是否符合結構化原則。描述算法的工具通常有傳統流程圖、N-S結構化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環3種基本控制結構組合而成。

1.2.3　算法描述的方法

算法是描述某一問題求解的有限步驟，而且必須有結果輸出。設計一個算法，或者描述一個算法，最終是由程序設計語言來實現的。但算法與程序設計又是有區別的，主要是一個由粗到細的過程。算法是考慮實現某一個問題求解的方法和步驟，是解決問題的框架流程；而程序設計則是根據這一求解的框架流程進行語言細化，實現這一問題求解的具體過程。

一般可以使用下面幾種類型的工具描述算法：

（1）自然語言

自然語言即人們日常進行交流的語言，如英語、漢語等。自然語言用來描述算法，分析算法，作為用戶相互之間進行交流，是一種較好的工具。但是將自然語言描述的算法直接在計算機上進行處理，目前還存在許多困難，包括有諸如語音語義識別等方面的問題。

（2）專用工具

要對某一個算法進行描述，可以借助于有關圖形工具或代碼符號。20世紀50～60年代興起的流程圖幾乎成了程序設計及算法描述的必用工具，是描述算法很好的形式。

人們已經提出了多種描述算法的流程圖。這種方法的特點是用一些圖框表示各種類型的操作：圓角矩形表示起止框，在算法開始和結束的時候使用；菱形表示判斷框；矩形表示處理框；平行四邊形表示輸入/輸出框；帶點不封閉矩形表示注釋框；基本圖形用流程線連接起來，通過流程線反映出它們之間的關系；小圓圈表示連接點，大型系統中流程線和基本圖形連接起來時，通常用小圓圈表示。圖1.2為一般流程圖所用的基本符號圖形。

流程圖這里主要介紹傳統流程圖和N-S流程圖。

傳統流程圖的優點是形象直觀、簡單方便，根據流程線能很直觀地看出程序的走向；缺點是它對流程線的走向沒有任何的限制，導致誰都可以修改流程的走向，使流程隨意轉向，而且它在描述復雜算法時，所占篇幅較多。

N-S流程圖是在1973年，由美國學者I.Nassi和B.Shneiderman提出的一種新的流程圖形式，這種流程圖完全去掉了流程線，算法的每一步都用一個矩形框來描述，把一個個矩形框按執行的次序連接起來就是一個完整的算法描述。這種流程圖用兩位學者的第一個英文字母命名，因此稱為N-S流程圖。在下一小節中將結合結構化程序設計中的三種基本結構來介紹這種流程圖的基本結構。

（3）部分常用的算法

在程序設計時，常常要通過一些特定的算法來求解。現在比較常用的算法有下列幾種：

①迭代法　一般的一元五次或更高次的方程，以及幾乎所有的超越方程、微分方程問題都無法用解析方法通過求根公式來求解，人們只能用數值方法求其近似解。用事先估計的一個根的初始值X₀，通過迭代算式X_K+1=G（X_K）求出另一個近似值X₁，再由X₁求出X₂，從而獲得一個求解的序列{X₀，X₁，X₂，…，X_n，…}來逼近方程f（x）=0的根。這種求解的過程稱為迭代。

②枚舉法　枚舉法的基本思想是首先依據題目部分條件確定答案的大致范圍，然后逐一驗證所有可能的情況，這種算法也稱為窮舉法。

③遞歸法　遞歸是指一個過程直接或間接地調用它自身，遞歸過程必須有一個遞歸終止條件。

如：

④遞推法　算法從遞推初始條件出發，應用遞推公式對問題進行求解。如Fibonacci數列存在遞推關系：

F（1）=1，F（2）=1，F（n）=F（n-1）+F（n-2），（n>2）

若需求第30項的值，則依據公式，從初始條件F（1）=1、F（2）=1出發，可逐步求出F（3）、F（4）……，直到求出F（30）。

除此之外，還有回溯法（一種基本策略）、分治法（問題分解成較小部分，求解再組合）等其他的常見算法，在此不一一闡述。

1.2.4　程序設計

（1）程序設計

程序設計的過程一般包含以下幾個部分：

①確定數據結構：是指根據任務書提出的要求、指定的輸入數據和輸出結果，確定存放數據的數據結構。

②確定算法：針對存放數據的數據結構來確定解決問題、完成任務的步驟。

③編碼：根據確定的數據結構和算法，使用選定的計算機語言編寫程序代碼，輸入到計算機并保存在磁盤上，簡稱編程。

④調試：目的是驗證代碼的正確性，用各種可能的輸入數據對程序進行測試，消除由于疏忽而引起的語法錯誤或邏輯錯誤；使之對各種合理的數據都能夠得到正確的結果，對不合理的數據能進行適當的處理。

⑤整理并寫出文檔資料。

這就是編寫程序的五個步驟。

（2）結構化程序設計

對于任何一個程序來說，都有自身的結構。就像我們讀文章一樣，我們說文章的結構是順敘的、倒敘的或是插敘的等，結構化的程序設計由三種基本結構組成。

①順序結構　在本書第3章中將要介紹的如賦值語句，輸入、輸出語句都可以構成順序結構。當執行由這些語句構成的程序時，將按這些語句在程序中的先后順序逐條執行，沒有分支，沒有轉移。順序結構可用圖1.3所示的流程圖表示，其中圖（a）是一般的流程圖，圖（b）是N-S流程圖。

②選擇結構　在本書第4章中將要介紹的if語句、switch語句都可以構成選擇結構。當執行到這些語句時，將根據不同的條件去執行不同分支中的語句。當判斷表達式滿足條件時，執行語句1，否則執行語句2。選擇結構用圖1.4所示的流程圖表示，其中圖（a）是一般的流程圖，圖（b）是N-S流程圖。

③循環結構　在本書第5章中將要介紹不同形式的循環結構，它們將根據各自的條件，使同一組語句重復執行多次或一次也不執行。循環結構的流程圖如圖1.5和圖1.6所示，每個圖中圖（a）是一般的流程圖，圖（b）是N-S流程圖。圖1.5是當型循環流程圖。當型循環的特點是：當指定的條件滿足（成立）時，就執行循環體，否則就不執行。圖1.6是直到型循環流程圖。直到型循環的特點是：執行循環體直到指定的條件滿足（成立）時就不再執行循環體。

已經證明，由三種基本結構組成的算法可以解決任何復雜的問題。由三種基本結構所構成的算法稱為結構化算法；由三種基本結構所構成的程序稱為結構化程序。

（3）模塊化程序設計

當計算機在處理較復雜的任務時，程序代碼量非常大，通常會有上萬條語句，需要由許多人來共同完成。這時常常把這個復雜的任務分解為若干個子任務，每個子任務又可分為很多小的子任務，每個小的子任務只完成一項簡單的功能。在程序設計時，用一個個小模塊來實現這些功能，每個程序設計人員分別完成一個或多個小模塊。我們稱這樣的程序設計方法為“模塊化”的方法，由一個個功能模塊構成的程序結構為模塊化結構。

在劃分模塊時需要注意的是模塊與模塊之間的獨立性，盡量使一個模塊能夠完成一個功能，減少與其他模塊之間的耦合性，提高模塊的內聚度，這是模塊化設計的基本思想。

由于把一個大程序分解成若干相對獨立的子程序，每個子程序的代碼一般不超過一頁紙，因此對設計人員來說，編寫程序代碼變得不再困難。這時只需對程序之間的數據傳輸做出統一規范，同一軟件可由一組人員同時進行編寫，分別進行調試，這就大大提高了程序編制的效率。

結構化程序設計的基本原則是，自頂向下、逐步細化、模塊化設計、結構化編碼。軟件編制人員在進行程序設計的時候，首先要從宏觀上去把握，再逐步進行局部的細化。即應當集中考慮主程序的算法，寫出主程序后再動手逐步完成子程序的調用。對于這些子程序也可用調試主程序的同樣方法逐步完成其下一層子程序的調用。