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