1.2 算法和算法的表示

1.2.1 算法的概念

1.算法的基本概念

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

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

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

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

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

① 將黑瓶中的藍(lán)墨水裝入白瓶中；② 將藍(lán)瓶中的黑墨水裝入黑瓶中；③ 將白瓶中的藍(lán)墨水裝入藍(lán)瓶中； ④ 交換結(jié)束。

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

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

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

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

③ 按表達(dá)式bx+a2計算出結(jié)果存放到M中，然后執(zhí)行第⑤步；

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

⑤ 輸出M的值；

⑥ 算法結(jié)束。

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

2.算法的兩要素

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

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

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

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

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

算法的控制結(jié)構(gòu)決定了算法的執(zhí)行順序。如以上例題所示，算法的基本控制結(jié)構(gòu)通常包括順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。不論是簡單的還是復(fù)雜的算法，都是由這三種基本控制結(jié)構(gòu)組合而成的。

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

需要強調(diào)的是，設(shè)計算法與演繹數(shù)學(xué)有明顯區(qū)別，演繹數(shù)學(xué)是以公理系統(tǒng)為基礎(chǔ)，通過有限次推演完成對問題的求解。每次推演都是對問題的進(jìn)一步求解，如此不斷推演，直到能將問題的解完全描述出來為止。而設(shè)計算法則是充分利用解題環(huán)境所提供的基本操作，對輸入數(shù)據(jù)進(jìn)行逐步加工、變換和處理，從而達(dá)到解決問題的目的。