《算法設計與分析》一一1.2 抽象算法設計

1.2　抽象算法設計

算法設計源于我們面臨一個有待解決的算法問題。為此，我們首先讨論算法問題的嚴格定義，其次讨論算法設計，主要讨論證明算法正确性的基本方法。

1.2.1　算法問題規約

基于ram模型，我們主要讨論這樣的算法：它接受有限的資料作為輸入，進行相應的處理，在有限步内終止，并給出輸出。是以我們可以将算法問題嚴格地定義為精确限定輸入/輸出的“規約”(specification)形式。

定義1.1（算法問題規約）　一個算法問題的規約主要包括兩部分：

●輸入：明确規定了算法接受的所有合法輸入。

●輸出：明确規定了對于每一個合法的輸入值，相應的輸出值應該是什麼。

例如，“求最大公約數問題”這一算法問題我們可以給出其規約如下：

●輸入：任意兩個非負整數a、b。

●輸出：a、b的最大公約數 　≌饫锛偕枳畲蠊 約數這一數學概念的定義是明确的。 　?

針對上述明确定義的算法問題，我們可以設計相應的算法來解決它。這裡給出著名的歐幾裡得算法，又叫“輾轉相除法”，如算法1所示。算法1：euclid(a, b)

1　if b=0 then

2　return a;

3　else

4　return euclid(b, a mod b);1.2.2　算法正确性證明：數學歸納法

有了算法問題的嚴格定義，我們就有了讨論算法正确性的(唯一)标準。要證明算法的正确性，就是要證明對于任意的合法的輸入，算法的輸出總是滿足規約的要求。以歐幾裡得算法為例，我們要證明該算法的正确性就是要證明：對于任意兩個非負整數的輸入，算法輸出的結果一定是輸入的兩個數的最大公約數。

根據上面的讨論，我們發現證明算法正确性的核心挑戰在于：算法可能的輸入有無窮多種，我們需要保證無窮多種輸入對應的輸出都必然是對的。顯然，具體工程實作中常用的測試技術無法證明算法的正确性。無論對多大規模的輸入進行測試，始終有無窮多的輸入是我們無法覆寫到的。衆所周知，測試隻能證明程式是有錯的，而不能證明程式是無錯的。測試隻能盡量減少算法中的錯誤。

要證明一個可數無窮多的集合中的每個元素均滿足某種性質，主要的手段是數學歸納法。在實際使用中，我們經常将數學歸納法分為強、弱兩種形式。

定義1.2（弱數學歸納法）　假設p是一個定義在自然數集合n上的命題 ?∮械那榭鱿攏 我們會定義p是定義在非負整數上的命題，這本質上是一樣的。 ?Ｈ绻：

●p(1)為true。

● ?∈n,p(k)→p(k+1)。

則對所有的自然數n，p(n)為true。

定義1.3（強數學歸納法）　假設p是一個定義在自然數集合n上的命題。如果：

● ?∈n,p(1)∧p(2)∧…∧p(k)→p(k+1)。

以數學歸納法為基本手段，證明算法正确性的關鍵是，将算法面對無窮多種輸入，無窮多種可能的執行情況，按照某種原則變成關于自然數的無窮個命題p(1),p(2),…,p(n),…，然後再基于數學歸納法進行證明。需要指出的是這兩種數學歸納法都可以看作源于更基本的良序原理(well-ordering principle)。強、弱數學歸納法和良序原理這3種形式不同的證明在本質上是等價的，隻不過在不同的場景下，某一種證明方式使用起來更加便捷。關于數學歸納法與良序原理的詳細讨論參見附錄a。

下面以歐幾裡得算法為例，讨論算法的正确性證明。

定理1.4　euclid算法是正确的。

證明：要證明算法的正确性，就要證明：對于任意的非負整數輸入a、b，算法輸出的一定是a、b的最大公約數，記為gcd(a,b)。我們采用數學歸納法，對輸入的第二個參數b進行歸納。為此，我們将要證明的結論轉換成關于非負整數的無窮多個命題：p(0)= ?,算法對輸入a、0給出正确輸出

…

p(k－1)= ?,算法對輸入a、k-1給出正确輸出

p(k)= ?, 算法對輸入a、k給出正确輸出首先對基礎情況p(0)進行證明。根據算法的實作，無論第一個參數a的取值是多少，euclid(a,0)總是傳回a，這一結果符合我們對最大公約數的定義，是以p(0)為true。

歸納假設當第二個輸入參數b≤k－1時，算法總是正确的，即 ?≤k－1,p(b)為true。下面考慮p(k)的情況。根據算法實作，對于輸入(a,k)，算法将傳回euclid(k,a mod k)。根據歸納假設，由于a mod k≤k－1，是以算法總能正确計算b和a mod b的最大公約數。根據最大公約數的性質，有gcd(a,k)=gcd(k,a mod k)。我們将上述相等關系串聯起來，如下面的公式所示：euclid(a,k)　=　根據算法實作euclid(k,a mod k)　=　根據歸納假設gcd(k,a mod k)　=　根據最大公約數性質gcd(a,k)由此，我們就證明了對于任意的a，算法總能正确計算a、k的最大公約數，即證明了p(k)。　

根據數學歸納法，我們證明了對任意非負整數n，命題p(n)為true，即證明了euclid算法是正确的。