1.2 算法和算法的表示

1.2.1 算法的概念

1.算法的基本概念

什么是算法？當代著名計算機科學家D.E.Knuth在他撰寫的《THE ART OF COMPUTER PROGRAMMING》一書中寫到："一個算法，就是一個有窮規則的集合，其中之規則規定了一個解決某一特定類型的問題的運算序列。"簡單地說，任何解決問題的過程都是由一定的步驟組成的，把解決問題確定的方法和有限的步驟稱作為算法。

需要說明的是，不是只有計算問題才有算法。例如，加工一張寫字臺，其加工順序是：桌腿 桌面 抽屜 組裝，這就是加工這張寫字臺的算法。當然，如果是按"抽屜 桌面 桌腿 組裝"這樣的順序加工，那就是加工這張寫字臺有另一種算法，這其中沒有計算問題。通常計算機算法分為兩大類：數值運算算法和非數值運算算法。數值運算是指對問題求數值解，例如對微分方程求解、對函數的定積分求解、對高次方程求解等，都屬于數值運算范圍。非數值運算包括非常廣泛的領域，例如資料檢索、事務管理、數據處理等。數值運算有確定的數學模型，一般都有比較成熟的算法。許多常用算法通常還會被編寫成通用程序并匯編成各種程序庫的形式，用戶需要時可直接調用。例如數學程序庫、數學軟件包等。而非數值運算的種類繁多，要求不一，很難提供統一規范的算法。在一些關于算法分析的著作中，一般也只是對典型算法作詳細討論，其它更多的非數值運算是需要用戶設計其算法的。

下面通過三個簡單的問題說明設計算法的思維方法。

例1-1：有黑和藍兩個墨水瓶，但卻錯把黑墨水裝在了藍墨水瓶子里，而藍墨水錯裝在了黑墨水瓶子里，要求將其互換。

算法分析：這是一個非數值運算問題。因為兩個瓶子的墨水不能直接交換，所以，解決這一問題的關鍵是需要引入第三個墨水瓶。設第三個墨水瓶為白色，其交換步驟如下：

① 將黑瓶中的藍墨水裝入白瓶中；② 將藍瓶中的黑墨水裝入黑瓶中；③ 將白瓶中的藍墨水裝入藍瓶中； ④ 交換結束。

例1-2：計算函數M(x)的值。函數M(x)為：

算法分析：本題是一個數值運算問題。其中M代表要計算的函數值，有兩個不同的表達式，根據x的取值決定采用哪一個算式。根據計算機具有邏輯判斷的基本功能，用計算機解題的算法如下：

① 將a、b、c和x的值輸入到計算機；

② 判斷x≤a?如果條件成立，執行第③步，否則執行第④步；

③ 按表達式bx+a2計算出結果存放到M中，然后執行第⑤步；

④ 按表達式a(c-x)+c3計算出結果存放到M中，然后執行第⑤步；

⑤ 輸出M的值；

⑥ 算法結束。

例1-3：給定兩個正整數m和n（m≥n），求它們的最大公約數。
　　算法分析：這也是一個數值運算問題，它有成熟的算法，我國數學家秦九韶在《算書九章》一書中曾記載了這個算法。求最大公約數的問題一般用輾轉相除法（也稱歐幾里德算法）求解。
　　例如：設m 35，n 15，余數用r表示。它們的最大公約數的求法如下：
　　35/15商2 余數為5 以n作m，以r作n,繼續相除；
　　15/5商3 余數為0 當余數為零時，所得n即為兩數的最大公約數。
　　所以35和15兩數的最大公約數為5。
　　用這種方法求兩數的最大公約數，其算法可以描述如下：
　?、?將兩個正整數存放到變量m和n中；
　?、?求余數：計算m除以n，將所得余數存放到變量r中；
　　③ 判斷余數是否為0：若余數為0則執行第⑤步，否則執行第④步；
　　④ 更新被除數和余數：將n的值存放到m中，將r的值存放到n中，并轉向第②步繼續循環執行；
　?、葺敵鰊的當前值，算法結束。
　　如此循環，直到得到結果。
　　由上述三個簡單的例子可以看出，一個算法由若干操作步驟構成，并且這些操作是按一定的控制結構所規定的次序執行。如例1-1中的四個操作步驟是順序執行的，稱之為順序結構。而在例1-2中，則不是按操作步驟順序執行，也不是所有步驟都執行。如第三步和第四步的兩個操作就不能同時被執行，它們需要根據條件判斷決定執行哪個操作，這種結構稱之為分支結構。在例1-3中不僅包含了判斷，而且需要重復執行。如第二步到第五步之間的步驟就需要根據條件判斷是否重復執行，并且一直延續到條件"余數為0"為止，這種具有重復執行功能的結構稱之為循環結構。

2.算法的兩要素

由上述三個例子可以看出，任何簡單或復雜的算法都是由基本功能操作和控制結構這兩個要素組成。不論計算機的種類如何之多，但它們最基本的功能操作是一致的。計算機的基本功能操作包括以下四個方面：

(1) 邏輯運算：與、或、非；

(2) 算術運算：加、減、乘、除；

(3) 數據比較：大于、小于、等于、不等于、大于等于、小于等于；

(4) 數據傳送：輸入、輸出、賦值。

算法的控制結構決定了算法的執行順序。如以上例題所示，算法的基本控制結構通常包括順序結構、分支結構和循環結構。不論是簡單的還是復雜的算法，都是由這三種基本控制結構組合而成的。

算法是對程序控制結構的描述，而數據結構是對程序中數據的描述。因為算法的處理對象必然是問題中所涉及到的相關數據，所以不能離開數據結構去抽象地分析程序的算法，也不能脫離算法去孤立地研究程序的數據結構，而只能從算法和數據結構的統一上去認識程序。但是，在計算機的高級語言中，數據結構是通過數據類型表現的，本書在第三章、第七章、第十章和第十一章中，將通過對C語言數據類型的詳細描述說明數據結構在程序設計中的作用。這里我們只討論算法的問題。

需要強調的是，設計算法與演繹數學有明顯區別，演繹數學是以公理系統為基礎，通過有限次推演完成對問題的求解。每次推演都是對問題的進一步求解，如此不斷推演，直到能將問題的解完全描述出來為止。而設計算法則是充分利用解題環境所提供的基本操作，對輸入數據進行逐步加工、變換和處理，從而達到解決問題的目的。