1.1 什么是算法
1.1 什么是算法
雖然對于這個(gè)概念沒有一個(gè)大家公認(rèn)的定義，但我們對它的含義還是有基本共識(shí)的：
算法（algorithm）是一系列解決問題的明確指令，也就是說，對于符合一定規(guī)范的輸入，能夠在有限時(shí)間內(nèi)獲得要求的輸出。
這個(gè)定義可以用一幅簡單的圖（圖1.1）來說明。
圖1.1 算法的概念
定義中使用了“指令”這個(gè)詞，這意味著有人或物能夠理解和執(zhí)行所給出的命令，我們將這種人或物稱為computer。請記住，在電子計(jì)算機(jī)發(fā)明以前，computer是指那些從事數(shù)學(xué)計(jì)算的人。現(xiàn)在，computer當(dāng)然是特指那些做每件事情都越發(fā)不可或缺的、無所不在的電子設(shè)備。但要注意的是，雖然絕大多數(shù)算法最終要靠計(jì)算機(jī)來執(zhí)行，但算法概念本身并不依賴于這樣的假設(shè)。
為了闡明算法的概念，本節(jié)將以三種方法為例來解決同一個(gè)問題，即計(jì)算兩個(gè)整數(shù)的最大公約數(shù)。這些例子會(huì)幫助我們闡明以下要點(diǎn)。
● 算法的每一個(gè)步驟都必須沒有歧義，不能有半點(diǎn)兒含糊。
● 必須認(rèn)真確定算法所處理的輸入的值域。
● 同一算法可以用幾種不同的形式來描述。
● 同一問題，可能存在幾種不同的算法。
● 針對同一問題的算法可能基于完全不同的解題思路，而且解題速度也會(huì)有顯著不同。
還記得最大公約數(shù)的定義嗎？兩個(gè)不全為0的非負(fù)整數(shù)m和n的最大公約數(shù)記為gcd（m, n），代表能夠整除（即余數(shù)為0）m和n的最大正整數(shù)。古希臘數(shù)學(xué)家、亞歷山大港的歐幾里得（公元前3世紀(jì)）所著的《幾何原本》，以系統(tǒng)論述幾何學(xué)而著稱，在其中的一卷里，他簡要描述了一個(gè)最大公約數(shù)算法。用現(xiàn)代數(shù)學(xué)的術(shù)語來表述，歐幾里得算法（Euclid's algorithm）采用的方法是重復(fù)應(yīng)用下列等式，直到m mod n等于0。
gcd（m, n）=gcd（n, m mod n） （m mod n表示m除以n之后的余數(shù)）
因?yàn)間cd（m, 0）=m（為什么？），m最后的取值也就是m和n的初值的最大公約數(shù)。
舉例來說，gcd（60, 24）可以這樣計(jì)算：
gcd（60, 24）=gcd（24, 12）=gcd（12, 0）=12
如果你對這個(gè)算法還沒有足夠的認(rèn)識(shí)，可以做本節(jié)習(xí)題第6題，試著求一些較大數(shù)的最大公約數(shù)。
下面是該算法的一個(gè)更加結(jié)構(gòu)化的描述：
用于計(jì)算gcd（m, n）的歐幾里得算法
第一步：如果n=0，返回m的值作為結(jié)果，同時(shí)過程結(jié)束；否則，進(jìn)入第二步。
第二步：m除以n，將余數(shù)賦給r。
第三步：將n的值賦給m，將r的值賦給n，返回第一步。
我們也可以使用偽代碼來描述這個(gè)算法：
算法 Euclid（m, n）
我們怎么知道歐幾里得算法最終一定會(huì)結(jié)束呢？通過觀察，我們發(fā)現(xiàn)，每經(jīng)過一次循環(huán)，參加運(yùn)算的兩個(gè)算子中的后一個(gè)都會(huì)變得更小，而且絕對不會(huì)變成負(fù)數(shù)。確實(shí)，下一次循環(huán)時(shí)，n的新值是m mod n，這個(gè)值總是比n小。所以，第二個(gè)算子的值最終會(huì)變成0，此時(shí)，這個(gè)算法也就結(jié)束了。
就像其他許多問題一樣，最大公約數(shù)問題也有多種算法。讓我們看看解這個(gè)問題的另外兩種方法。第一個(gè)方法只基于最大公約數(shù)的定義：m和n的最大公約數(shù)就是能夠同時(shí)整除它們的最大正整數(shù)。顯然，這樣一個(gè)公約數(shù)不會(huì)大于兩數(shù)中的較小者，因此，我們先有：t=min{m, n}。我們現(xiàn)在可以開始檢查t是否能夠整除m和n：如果能，t就是最大公約數(shù)；如果不能，我們就將t減1，然后繼續(xù)嘗試（我們?nèi)绾未_定該算法最終一定會(huì)結(jié)束呢？）。例如，對于60和24這兩個(gè)數(shù)來說，該算法會(huì)先嘗試24，然后是23，這樣一直嘗試到12，算法就結(jié)束了。
用于計(jì)算gcd（m, n）的連續(xù)整數(shù)檢測算法
第一步：將min{m, n}的值賦給t。
第二步：m除以t。如果余數(shù)為0，進(jìn)入第三步；否則，進(jìn)入第四步。
第三步：n除以t。如果余數(shù)為0，返回t的值作為結(jié)果；否則，進(jìn)入第四步。
第四步：把t的值減1。返回第二步。
注意，和歐幾里得算法不同，按照這個(gè)算法的當(dāng)前形式，當(dāng)它的一個(gè)輸入為0時(shí)，計(jì)算出來的結(jié)果是錯(cuò)誤的。這個(gè)例子說明了為什么必須認(rèn)真、清晰地規(guī)定算法輸入的值域。
求最大公約數(shù)的第三種過程，我們應(yīng)該在中學(xué)時(shí)代就很熟悉了。
中學(xué)時(shí)計(jì)算gcd（m, n）的過程
第一步：找到m的所有質(zhì)因數(shù)。
第二步：找到n的所有質(zhì)因數(shù)。
第三步：從第一步和第二步求得的質(zhì)因數(shù)分解式中找出所有的公因數(shù)（如果p是一個(gè)公因數(shù)，而且在m和n的質(zhì)因數(shù)分解式分別出現(xiàn)過pm和pn次，那么應(yīng)該將p重復(fù)min{pm, pn}次）。
第四步：將第三步中找到的質(zhì)因數(shù)相乘，其結(jié)果作為給定數(shù)字的最大公約數(shù)。
這樣，對于60和24這兩個(gè)數(shù)，我們得到：
60=2×2×3×5
24=2×2×2×3
gcd（60, 24）=2×2×3=12
雖然學(xué)習(xí)這個(gè)方法的那段中學(xué)時(shí)光是令人懷念的，但我們?nèi)匀蛔⒁獾剑谌齻€(gè)過程比歐幾里得算法要復(fù)雜得多，也慢得多（下一章中，我們將會(huì)討論對算法運(yùn)行時(shí)間進(jìn)行求解和比較的方法）。撇開低劣的性能不談，以這種形式表述的中學(xué)求解過程還不能稱為一個(gè)真正意義上的算法。為什么？因?yàn)槠渲星筚|(zhì)因數(shù)的步驟并沒有明確定義：該步驟要求得到一個(gè)質(zhì)因數(shù)的列表，但我們十分懷疑中學(xué)里是否曾教過如何求這樣一個(gè)列表。必須承認(rèn)，這并不是雞蛋里挑骨頭。除非解決了這個(gè)問題，否則我們不能下結(jié)論說，能夠?qū)懸粋€(gè)實(shí)現(xiàn)這個(gè)過程的程序。順便說一句，第三步也沒有定義清楚。當(dāng)然，它的不明確性要比求質(zhì)因數(shù)的步驟更容易糾正一些。想想我們是如何求兩個(gè)有序列表的公共元素的。
所以，我們要介紹一個(gè)簡單的算法，用來產(chǎn)生一個(gè)不大于給定整數(shù)n的連續(xù)質(zhì)數(shù)序列。它很可能是古希臘人發(fā)明的，稱為“埃拉托色尼篩選法”（sieve of Eratosthenes）。該算法一開始初始化一個(gè)2～n的連續(xù)整數(shù)序列，作為候選質(zhì)數(shù)。然后，在算法的第一個(gè)循環(huán)中，它將類似4和6這樣的2的倍數(shù)從序列中消去。然后，它指向列表中的下一個(gè)數(shù)字3，又將其倍數(shù)消去（我們這里的做法過于直接，增加了不必要的開銷。因?yàn)橛幸恍?shù)字，拿6來說吧，被消去了不止一次）。不必處理數(shù)字4，因?yàn)?本身和它的倍數(shù)都是2的倍數(shù)，它們已經(jīng)在前面的步驟中被消去了。第三步處理序列中剩下的下一個(gè)元素5。該算法以這個(gè)方式不斷做下去，直到序列中已經(jīng)沒有可消的元素為止。序列中剩下的整數(shù)就是我們要求的質(zhì)數(shù)。
作為一個(gè)例子，我們嘗試用這個(gè)算法找出n不大于25的質(zhì)數(shù)序列。
對于這個(gè)例子來說，更多步驟已經(jīng)多余了，因?yàn)樗鼈冎粫?huì)消去在算法的前面循環(huán)中已經(jīng)消去的數(shù)字。序列中剩下的數(shù)字就是小于等于25的連續(xù)質(zhì)數(shù)。
其倍數(shù)仍未消去的最大數(shù)p應(yīng)該滿足什么條件呢？在回答這個(gè)問題之前，我們先要注意到：如果當(dāng)前步驟中，我們正在消去p的倍數(shù)，那么第一個(gè)值得考慮的倍數(shù)是p×p，因?yàn)槠渌〉谋稊?shù)2p，…，（p–1）p已經(jīng)在先前的步驟中從序列里消去了。了解這個(gè)事實(shí)可以幫助我們避免多次消去相同的數(shù)字。顯然，p×p不會(huì)大于n，p也不會(huì)大于(4)，稱為“向下取整函數(shù)”）。在下面這段偽代碼中，我們假設(shè)有一個(gè)函數(shù)可以計(jì)算
算法 Sieve（n）
這樣就能夠?qū)ⅰ鞍＠猩岷Y選法”應(yīng)用在中學(xué)時(shí)的求解過程中了，我們得到了一個(gè)計(jì)算兩個(gè)正整數(shù)的最大公約數(shù)的正規(guī)算法。注意，還必須關(guān)注其中一個(gè)輸入?yún)?shù)為1或者兩個(gè)都為1的情況：因?yàn)閲?yán)格來講，數(shù)學(xué)家并不認(rèn)為1是一個(gè)質(zhì)數(shù)，所以這個(gè)方法是無法處理這種輸入的。
在結(jié)束本節(jié)之前，還需要做一些說明。雖然我們這里舉的例子有一些數(shù)學(xué)味道，但當(dāng)今所使用的大多數(shù)算法（即使是那些已經(jīng)應(yīng)用于計(jì)算機(jī)程序的算法）都不涉及數(shù)學(xué)問題。大家可以看到，無論是工作中還是生活中，算法每天都在幫助我們處理各種事務(wù)。算法在當(dāng)今社會(huì)是無所不在的，它是信息時(shí)代的魔術(shù)引擎，希望這個(gè)事實(shí)能夠使大家下定決心，深入學(xué)習(xí)算法課程。