第1部分 算法和算法分析

第1章 算法問題求解基礎(chǔ)

算法是計算機(jī)學(xué)科的一個重要分支，它是計算機(jī)科學(xué)的基礎(chǔ)，更是計算機(jī)程序的基石。算法是計算機(jī)求解問題的特殊方法。學(xué)習(xí)算法，一方面需要學(xué)習(xí)求解計算領(lǐng)域中典型問題的各種有效算法，還要學(xué)習(xí)設(shè)計新算法和分析算法性能的方法。本章給出算法的基本概念，介紹使用計算機(jī)求解問題的過程和方法，討論遞歸算法及證明遞歸算法正確性的歸納法。

1.1 算法概述

1.1.1 什么是算法

在學(xué)習(xí)一門計算機(jī)程序設(shè)計語言，如C/C++或Pascal之后，應(yīng)該對算法一詞不再陌生。編寫一個程序，實(shí)際上是在實(shí)現(xiàn)使用計算機(jī)求解某個問題的方法。在計算機(jī)科學(xué)中，算法一詞用于描述一個可用計算機(jī)實(shí)現(xiàn)的問題求解（problem-solving）方法。

什么是算法？籠統(tǒng)地說，算法（algorithm）是求解一類問題的任意一種特殊的方法。較嚴(yán)格的說法是，一個算法是對特定問題求解步驟的一種描述，它是指令的有限序列。此外，算法具有下列5個特征。

（1）輸入（input）：算法有零個或多個輸入量；

（2）輸出（output）：算法至少產(chǎn)生一個輸出量；

（3）確定性（definiteness）：算法的每一條指令都有確切的定義，沒有二義性；

（4）能行性（effectiveness）：算法的每一條指令必須足夠基本，它們可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)；

（5）有窮性（finiteness）：算法必須總能在執(zhí)行有限步之后終止。

所有算法都必須具有以上5個特征。算法的輸入是一個算法在開始前所需的最初的量，這些輸入取自特定的值域。算法可以沒有輸入，但算法至少應(yīng)產(chǎn)生一個輸出，否則算法便失去了它存在的意義。算法是一個指令序列。一方面，每條指令的作用必須是明確、無歧義的。在算法中不允許出現(xiàn)諸如“計算5+3或計算7-3”這樣的指令。另一方面，算法的每條指令必須是能行的。對一個計算機(jī)算法而言，能行性要求一條算法指令應(yīng)當(dāng)最終能夠由執(zhí)行有限條計算機(jī)指令來實(shí)現(xiàn)。例如，一般的整數(shù)算術(shù)運(yùn)算是能行的，但如果1÷3的值需由無窮的十進(jìn)制展開的實(shí)數(shù)表示，就不是能行的。因此，概括地說，算法是由一系列明確定義的基本指令序列所描述的，求解特定問題的過程。它能夠?qū)戏ǖ妮斎耄谟邢迺r間內(nèi)產(chǎn)生所要求的輸出。如果取消有窮性限制，則只能稱為計算過程（computational procedure）。

描述一個算法有多種方法，可以用自然語言、流程圖、偽代碼和程序設(shè)計語言來描述。當(dāng)一個算法使用計算機(jī)程序設(shè)計語言描述時，就是程序（program）。算法必須可終止。計算機(jī)程序并沒有這一限制，例如，一個操作系統(tǒng)是一個程序，卻不是一個算法，一旦運(yùn)行，只要計算機(jī)不關(guān)機(jī)，操作系統(tǒng)程序就不會終止運(yùn)行。所以，操作系統(tǒng)程序是使用計算機(jī)語言描述的一個計算過程。

算法概念并不是計算機(jī)誕生以后才有的新概念。計算兩個整數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法是由古希臘歐幾里得（約公元前330—275年）在他的《幾何原本》（Euclid’s Elements）中提出的，它是算法研究最重要的早期成果。直到1950年左右，算法一詞還經(jīng)常與歐幾里得算法（Euclid’s algorithm）聯(lián)系在一起。中國的珠算口訣可視為典型的算法，它將復(fù)雜的計算（如除法）描述為一系列的算珠撥動操作。

歐幾里得算法又稱輾轉(zhuǎn)相除法，用于計算兩個整數(shù)m和n（0≤m＜n的最大公約數(shù)，記為gcd(m, n)。其計算過程是重復(fù)應(yīng)用下列等式，直到n mod m=0。

gcd(m, n)=gcd(n mod m, m)，對于m＞0 （1-1）

式中，n mod m表示n除以m之后的余數(shù)。因為gcd(0, n)=n，n的最后取值也就是m和n的最大公約數(shù)。例如，gcd(24, 60)=gcd(12, 24)=gcd(0, 12)=12。

歐幾里得算法使用了遞歸，其C/C++語言描述見程序1-1。歐幾里得算法的迭代形式描述見程序1-2。請注意數(shù)學(xué)上的運(yùn)算符mod與C/C++語言的“%”運(yùn)算符的區(qū)別。

【程序1-1】 歐幾里得遞歸算法

void Swap(int&a,int&b)
{
    int c=a;a=b;b=c;
}
int RGcd(int m,int n)
{
    if(m==0) return n;
    return RGcd(n%m,m);
}
int Gcd(int m,int n)
{
    if (m>n) Swap(m,n);
    return RGcd(m,n);
}

【程序1-2】 歐幾里得迭代算法

int Gcd(int m,int n)
{
     if (m==0)return n; if (n==0)return m;
     if (m>n) Swap(m,n);
     while(m>0){
          int c=n%m;n=m;m=c;
     }
     return n;
}

上述程序必定會結(jié)束，因為每循環(huán)一次，m的新值就會變小，但絕對不會成為負(fù)數(shù)，當(dāng)m=0時程序終止。

最大公約數(shù)問題還可以有其他算法。程序1-3的連續(xù)整數(shù)檢測算法的依據(jù)直接來自最大公約數(shù)的定義：m和n的最大公約數(shù)是能夠同時整除它們的最大正整數(shù)。顯然，一個公約數(shù)不會大于兩數(shù)中的較小者，因此，可以先令t=min{m, n}，然后檢查t能否分別整除m和n，若能，則t就是最大公約數(shù)，否則令t減1后繼續(xù)檢測。程序1-3必定會終止。如果m和n的最大公約數(shù)是1，則當(dāng)t=1時，程序終止。

【程序1-3】 Gcd的連續(xù)整數(shù)檢測算法

int Gcd(int m,int n)
{
     if (m==0)return n;if (n==0)return m;
     int t=m>n?n:m;
     while (m%t || n%t) t--;
     return t;
}

從上面的討論可知，一個問題可以設(shè)計不同的算法來求解，針對同一個問題的算法也許基于完全不同的解題思路。求兩個整數(shù)的最大公約數(shù)可以采用歐幾里得算法，也可以采用連續(xù)整數(shù)檢測算法，兩種算法的解題速度會有顯著差異。此外，同一個算法可采用不同的形式來表示。例如，歐幾里得算法可以寫成遞歸形式，也可以寫成迭代形式。

1.1.2 為什么學(xué)習(xí)算法

算法是計算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才。對于計算機(jī)專業(yè)的學(xué)生來說，學(xué)習(xí)算法的理由是非常充分的。因為你必須知道來自不同計算領(lǐng)域的重要算法，你也必須學(xué)會設(shè)計新的算法、確認(rèn)其正確性并分析其效率。隨著計算機(jī)應(yīng)用的日益普及，各個應(yīng)用領(lǐng)域的研究和技術(shù)人員都在使用計算機(jī)求解他們各自專業(yè)領(lǐng)域的問題，他們需要設(shè)計算法，編寫程序，開發(fā)應(yīng)用軟件，所以學(xué)習(xí)算法對于越來越多的人來說變得十分必要。

著名的美國計算機(jī)科學(xué)家克努特（D.E.Knuth）說過：“一個受過良好的計算機(jī)科學(xué)知識訓(xùn)練的人知道如何處理算法，即構(gòu)造算法、操縱算法、理解算法和分析算法。算法知識遠(yuǎn)不只是為了編寫好的計算程序，它是一種具有一般意義的智能工具，必定有助于對其他學(xué)科的理解，不論化學(xué)、語言學(xué)或者音樂等。”

哈雷爾（David Harel）在他的《算法學(xué)——計算的靈魂》一書中說：“算法不僅是計算機(jī)學(xué)科的一個分支，它更是計算機(jī)科學(xué)的核心，而且可以毫不夸張地說，它和絕大多數(shù)科學(xué)、商業(yè)和技術(shù)都是相關(guān)的。”

1.2 問題求解方法

軟件開發(fā)的過程是使用計算機(jī)求解問題的過程。使用計算機(jī)解題的核心任務(wù)是設(shè)計算法。算法并非就是問題的解，它是準(zhǔn)確定義的，用來獲得問題解的計算過程的描述。算法是問題的程序化解決方案。顯然，算法能夠求解的問題種類是有局限性的，它們不可能求解現(xiàn)實(shí)世界中的所有問題。本書討論的問題都是指能用算法求解的問題。

1.2.1 問題和問題求解

什么是問題（problem）？只要目前的情況與人們所希望的目標(biāo)不一致，就會產(chǎn)生問題。例如，排序問題是：任意給定一組記錄，排序的目的是使得該組記錄按關(guān)鍵字值非減（或非增）次序排列。

問題求解（problem solving）是尋找一種方法來實(shí)現(xiàn)目標(biāo)。問題求解是一種藝術(shù)，沒有一種通用的方法能夠求解所有問題。有時，人們不得不一次又一次地嘗試可能的求解方法，直到找到一種正確的求解途徑。一般說來，問題求解中存在著猜測和碰運(yùn)氣的成分。然而，當(dāng)我們積累了問題求解的經(jīng)驗，這種對問題解法的猜測就不再是完全盲目的，而是形成某些問題求解的技術(shù)和策略。問題求解過程（problem solving process）是人們通過使用問題領(lǐng)域知識來理解和定義問題，并憑借自身的經(jīng)驗和知識去選擇和使用適當(dāng)?shù)膯栴}求解策略、技術(shù)和工具，將一個問題描述轉(zhuǎn)換成問題解的過程。

現(xiàn)在，很多問題可以用計算機(jī)求解，計算機(jī)的應(yīng)用已滲透到人類活動的方方面面。有些問題，如四色問題，如果沒有計算機(jī)，至今恐怕難以求解。計算機(jī)求解問題的過程就是一個計算機(jī)軟件的開發(fā)過程，被稱為軟件生命周期（software life cycle）。

計算機(jī)求解問題的關(guān)鍵之一是尋找一種問題求解策略（problem solving strategy），得到求解問題的算法，從而得到問題的解。例如，求解前面提到的排序問題是指設(shè)計一種排序算法，能夠把任意給定的一組記錄排成有序的記錄序列。

1.2.2 問題求解過程

匈牙利數(shù)學(xué)家喬治·波利亞（George Polya）在1957年出版的《How to solve it》一書中概括了如何求解數(shù)學(xué)問題的技術(shù)。這種問題求解的四步法對于大多數(shù)其他科學(xué)也是適用的，同樣也可用于求解計算機(jī)應(yīng)用問題。

問題求解的四步法簡述如下。

（1）理解問題（understand the problem）

毫無疑問，為了求解問題必須首先理解問題。如果不理解問題，當(dāng)然就不可能求解它。此外，對問題的透徹理解有助于求解問題。這一步很重要，它看似簡單，其實(shí)并不容易。在這一步，我們必須明確定義所要求解的問題，并用適當(dāng)?shù)姆绞奖硎締栴}。對于簡單問題，不妨直接用自然語言描述問題，如排序問題。

（2）設(shè)計方案（devise a plan）

求解問題時，首先考慮從何處著手，考慮以前有沒有遇到類似的問題，是否解決過規(guī)模較小的同類問題。此外，還應(yīng)選擇該問題的一些特殊例子進(jìn)行分析。在此基礎(chǔ)上，考慮選擇何種問題求解策略和技術(shù)進(jìn)行求解，以得到求解問題的算法。

（3）實(shí)現(xiàn)方案（carry out the plan）

實(shí)現(xiàn)求解問題的算法，并使用問題實(shí)例進(jìn)行測試、驗證。

（4）回顧復(fù)查（look back）

檢查該求解方法是否確實(shí)求解了問題或達(dá)到了目的。評估算法，考慮該解法是否可簡化、改進(jìn)和推廣。

對于上一小節(jié)討論的求最大公約數(shù)問題，理解起來并不困難，但為了求解問題，則需要相關(guān)的數(shù)學(xué)知識。最簡單的求解方案可以直接從最大公約數(shù)的定義出發(fā)得到，這就是程序1-3的連續(xù)整數(shù)檢測算法。歐幾里得算法建立在已經(jīng)證明式（1-1）成立的基礎(chǔ)上。對于這兩種求解算法，可以使用m和n的若干值進(jìn)行測試，驗證算法的正確性。通過比較，發(fā)現(xiàn)對于求最大公約數(shù)問題，連續(xù)整數(shù)檢測算法和歐幾里得算法的時間效率差別很大。遞歸的歐幾里得算法又可改寫成迭代形式，迭代算法的效率一般高于其對應(yīng)的遞歸算法。

1.2.3 系統(tǒng)生命周期

一個計算機(jī)程序的開發(fā)過程就是使用計算機(jī)求解問題的過程。軟件工程（software engineering ）將軟件開發(fā)和維護(hù)過程分成若干階段，稱為系統(tǒng)生命周期（system life cycle）或軟件生命周期。系統(tǒng)生命周期法要求每個階段完成相對獨(dú)立的任務(wù)；各階段都有相應(yīng)的方法和技術(shù)；每個階段都有明確的目標(biāo)，要有完整的文檔資料。這種做法便于各種軟件人員分工協(xié)作，從而降低軟件開發(fā)和維護(hù)的困難程度，保證軟件質(zhì)量，提高開發(fā)大型軟件的成功率和生產(chǎn)率。

通常把軟件生命周期劃分為分析（analysis）、設(shè)計（design）、編碼（coding or programming）、測試（testing）和維護(hù)（maintenance）等5個階段。前4個階段屬于開發(fā)期，最后一個階段處于運(yùn)行期。

軟件開發(fā)過程的前兩個階段“分析”和“設(shè)計”非常重要。“分析”是弄清楚需要“做什么（what）”，而“設(shè)計”是解決“如何做（how）”。

在問題求解的分析階段，我們試圖理解問題，弄清楚為了求解它必須做什么，而不是怎樣做。在分析階段，必須理解問題的需求。需求常常被分為功能需求和非功能需求兩類。功能需求描述求解問題的程序必須具有的功能和特性，非功能需求是軟件必須滿足的約束等。例如，對一個整數(shù)序列進(jìn)行排序的問題，其功能需求是將一個任意整數(shù)序列排列成非減有序序列，而非功能需求也許是代碼和數(shù)據(jù)使用的內(nèi)存空間不能超過20MB，運(yùn)行時間不超過5min等。這些需求應(yīng)當(dāng)被充分審查和討論，并明確定義，形成需求規(guī)范（requirement specification）。問題定義必須明確，無二義性，且具有一致性。

設(shè)計階段確定如何求解問題，包括選擇何種問題求解策略和技術(shù)，如算法設(shè)計策略。在軟件開發(fā)中，常采用逐步求精的方法，并用偽代碼和流程圖來設(shè)計和描述算法。

編碼實(shí)現(xiàn)階段的任務(wù)是編寫程序，運(yùn)行程序，并使用測試用例測試程序，驗證程序的正確性。

1.3 算法設(shè)計與分析

1.3.1 算法問題求解過程

算法問題的求解過程在本質(zhì)上與一般問題的求解過程是一致的。具體求解步驟如圖1-1所示。求解一個算法問題，需要先理解問題。通過仔細(xì)閱讀對問題的描述，充分理解所求解的問題。為了完全理解問題，可以列舉該問題的一些小例子，考慮某些特殊情況。

算法一般分兩類：精確算法和啟發(fā)式算法。一個精確算法（exact algorithm）總能保證求得問題的解。而一個啟發(fā)式算法（heuristic algorithm）通過使用某種規(guī)則、簡化或智能猜測來減少問題求解時間。它們也許比精確算法更有效，但其求解問題所需的時間常常因?qū)嵗悺Ｋ鼈円膊荒鼙ＷC求得的解必定是問題的最優(yōu)解，甚至不一定是問題的可行解（feasible solution）。一般來講，啟發(fā)式算法往往缺少理論依據(jù)。對于最優(yōu)化問題，一個算法如果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximation algorithm）。近似算法求得的應(yīng)當(dāng)是問題的可行解，但可能不是最優(yōu)解。如果在算法中需做出某些隨機(jī)選擇，則稱為隨機(jī)算法（randomized algorithm）。隨機(jī)算法執(zhí)行的隨機(jī)選擇一般依賴于隨機(jī)數(shù)發(fā)生器所產(chǎn)生的隨機(jī)數(shù)。

在理解問題之后，算法設(shè)計者需要選擇是否采取精確解法。有一些問題的確無法求得精確解，例如求平方根、求定積分和求解非線性方程。另一些問題雖然存在精確算法，但這些算法的求解時間慢得讓人無法接受。例如，設(shè)計一個導(dǎo)致贏局的人機(jī)對弈程序并不困難，可以采用窮舉算法。對于任何一種棋類，盡管其可能的棋局?jǐn)?shù)目可謂天文數(shù)字，但總是有限的。我們總能設(shè)計一個算法對任意給定的一種棋局，判斷這一棋局是否可能導(dǎo)致贏局，并由此決定下一步應(yīng)走哪一著棋。采用這種以窮舉方式逐一檢查棋局的算法，每一步?jīng)Q策都將異常費(fèi)時，即使在當(dāng)代速度最快的計算機(jī)上運(yùn)行也是不實(shí)際的。

啟發(fā)式算法并不總能導(dǎo)致理想的解，但常常能在合理的時間內(nèi)得到令人滿意的結(jié)果。

此外，雖然有些算法并不要求精心組織輸入數(shù)據(jù)，但另一些算法的確依賴于精心設(shè)計的數(shù)據(jù)結(jié)構(gòu)。對問題實(shí)例的數(shù)據(jù)進(jìn)行恰當(dāng)組織和重構(gòu)，有助于設(shè)計和實(shí)現(xiàn)高效的算法。數(shù)據(jù)結(jié)構(gòu)對于算法的設(shè)計常常至關(guān)重要。對于具有一定“數(shù)據(jù)結(jié)構(gòu)”知識的讀者，應(yīng)不難理解這一點(diǎn)。

1.3.2 如何設(shè)計算法

使用計算機(jī)的問題求解策略主要指算法設(shè)計策略（algorithm design strategy）。一般來說，算法的設(shè)計是一項創(chuàng)造性活動，不可能完全自動化，但學(xué)習(xí)一些基本的算法設(shè)計策略是非常有用的。對于所求解的問題，只要符合某種算法設(shè)計策略的前提，便可以利用它設(shè)計出精致而有效的算法。算法設(shè)計技術(shù)（也稱“策略”）是使用算法解題的一般性方法，可用于解決不同計算領(lǐng)域的多種問題。如果所求問題符合某種算法設(shè)計策略處理的問題特性，就可使用該算法設(shè)計策略設(shè)計算法、求解問題。例如，讀者熟知的排序問題符合分治策略求解的問題特征，可以用分治法求解。然而，由于在使用分治策略解題時的思路不同，會得到不同的排序算法。在第4章中將看到，合并排序和快速排序都可視為由分治法產(chǎn)生的排序算法，但兩者是不同的算法。

1.3.3 如何表示算法

算法所表示的計算過程需要以某種方式描述出來。算法可以使用自然語言描述，但自然語言不夠嚴(yán)謹(jǐn)。在計算機(jī)應(yīng)用的早期，算法主要用流程圖描述。實(shí)踐證明，流程圖通常只適于描述簡單算法，對于復(fù)雜算法，流程圖也會十分復(fù)雜，難以建圖和理解。偽代碼是自然語言和程序設(shè)計語言的混合結(jié)構(gòu)。它所描述的算法通常比自然語言精確，又比實(shí)際程序設(shè)計語言簡潔。但對于偽代碼，并沒有形成一致的語法規(guī)則，需要事先約定。使用一種實(shí)際的程序設(shè)計語言描述算法，雖然有時會多一些細(xì)節(jié)，但有助于算法的精確描述。此外，用C++語言描述的算法本身就是很好的C/C++程序范例，對學(xué)生掌握算法思想和進(jìn)行程序設(shè)計都是有益的。

在本書中，我們使用C/C++語言描述算法。C/C++語言類型豐富、語句精練，既能描述算法所處理的數(shù)據(jù)結(jié)構(gòu)，又能描述算法過程。同時，用C/C++語言描述算法可使算法結(jié)構(gòu)簡潔明了，可讀性好。

1.3.4 如何確認(rèn)算法

如果一個算法對于所有合法的輸入，都能在有限時間內(nèi)輸出預(yù)期的結(jié)果，那么此算法是正確的。確認(rèn)一個算法是否正確的活動稱為算法確認(rèn)（algorithm validation）。算法確認(rèn)的目的在于確認(rèn)一個算法能否正確無誤地工作。使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明（algorithm proof）。對于有些算法，正確性證明十分簡單，但對于另一些算法，卻可能十分困難。

證明算法正確性常用的方法是數(shù)學(xué)歸納法。對于程序1-1的求最大公約數(shù)的遞歸算法RGcd，可用數(shù)學(xué)歸納法證明如下：

設(shè)m和n是整數(shù)，0≤m＜n。若m=0，則因為gcd(0, n)=n，故程序RGcd在m=0時返回n是正確的。歸納法假定，當(dāng)0≤m＜n＜k時，函數(shù)RGcd(m, n)能在有限時間正確返回m和n的最大公約數(shù)，那么，當(dāng)0＜m＜n=k時，考察函數(shù)RGcd(m, n)，它將具有RGcd(n%m, m)的值。這是因為0≤n%m＜m且gcd(m, n)=gcd(n mod m, m)（數(shù)論定理），故該值正是m和n的最大公約數(shù)，證畢。

若要表明算法是不正確的，只需給出能夠?qū)е滤惴ú荒苷_處理的輸入實(shí)例即可。

到目前為止，算法的正確性證明仍是一項很有挑戰(zhàn)性的工作。在大多數(shù)情況下，人們通過程序測試和調(diào)試來排錯。程序測試（program testing）是指對程序模塊或程序總體，輸入事先準(zhǔn)備好的樣本數(shù)據(jù)（稱為測試用例，test case），檢查該程序的輸出，來發(fā)現(xiàn)程序存在的錯誤及判定程序是否滿足其設(shè)計要求的一項積極活動。測試的目的是為了“發(fā)現(xiàn)錯誤”，而不是“證明程序正確”。程序經(jīng)過測試暴露了錯誤，需要進(jìn)一步診斷錯誤的準(zhǔn)確位置，分析錯誤的原因，糾正錯誤。調(diào)試（debugging）是診斷和糾正錯誤的過程。

1.3.5 如何分析算法

算法的分析（algorithm analysis）活動是指對算法的執(zhí)行時間和所需空間的估算。求解同一問題可以編寫不同的算法，通過算法分析，可以比較兩個算法效率的高低。對于算法所需的時間和空間的估算，一般不需要將算法寫成程序在實(shí)際的計算機(jī)上運(yùn)行。當(dāng)然在算法寫成程序后，便可使用樣本數(shù)據(jù)，實(shí)際測量一個程序所消耗的時間和空間，這稱為程序的性能測量（performance measurement）。

1.4 遞歸和歸納

遞歸是一個數(shù)學(xué)概念，也是一種有用的程序設(shè)計方法。在程序設(shè)計中，為了處理重復(fù)性計算，最常用的辦法是組織迭代循環(huán)，除此之外還可以采用遞歸計算的辦法。美國著名計算機(jī)科學(xué)家約翰·麥卡錫極力主張將遞歸引入Algol 60語言，該語言是后來的Pascal、PL/1和C語言的基礎(chǔ)。他本人提出的表處理語言Lisp不僅允許函數(shù)遞歸，數(shù)據(jù)結(jié)構(gòu)也是遞歸的。

遞歸和歸納關(guān)系緊密。歸納法證明是一種數(shù)學(xué)證明方法，可用于證明一個遞歸算法的正確性。在下一章中還將看到，歸納法在算法分析中也很有用。

1.4.1 遞歸

1.遞歸定義

定義一個新事物、新概念或新方法，一般要求在定義中只包含已經(jīng)明確定義或證明的事物、概念或方法。然而遞歸定義卻不然，遞歸（recursive）定義是一種直接或間接引用自身的定義方法。一個合法的遞歸定義包括兩部分：基礎(chǔ)情況（base case）和遞歸部分。基礎(chǔ)情況以直接形式明確列舉新事物的若干簡單對象，遞歸部分給出由簡單（或較簡單）對象定義新對象的條件和方法。所以，只要簡單或相對簡單的對象已知，用它們構(gòu)造的新對象是明確的，無二義性的。

例1-1 斐波那契數(shù)列

說明遞歸定義的一個典型例子是斐波那契（Fibonacci）數(shù)列，它的定義可遞歸表示成：

根據(jù)這一定義，可以得到一個無窮數(shù)列0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …，稱為斐波那契數(shù)列。斐波那契數(shù)列產(chǎn)生于12世紀(jì)，但直到18世紀(jì)才由A.De.Moivre提出了它的非遞歸定義式。從12世紀(jì)到18世紀(jì)期間，人們只能采用斐波那契數(shù)列的遞歸定義來計算。斐波那契數(shù)列的直接計算公式為：

式中，，

2.遞歸算法

當(dāng)一個算法采用遞歸方式定義時便成為遞歸算法。一個遞歸算法是指直接或間接調(diào)用自身的算法。遞歸本質(zhì)上也是一種循環(huán)的算法結(jié)構(gòu)，它把“較復(fù)雜”的計算逐次歸結(jié)為“較簡單”情形的計算，直至歸結(jié)到“最簡單”情形的計算，并最終得到計算結(jié)果為止。

使用遞歸來解決問題，與使用一本大詞典查詢一個單詞的情形是類似的。在詞典中查一個單詞時，首先得到對該單詞的解釋，如果在該單詞的解釋中包含不認(rèn)識的單詞，還需要繼續(xù)查這些不認(rèn)識的單詞的詞義，直到所有相關(guān)單詞都已有明確解釋為止。如果其中至少有一個單詞在詞典中沒有解釋或出現(xiàn)循環(huán)定義，那么這一過程是循環(huán)不確定和錯誤的。

許多問題可以采用遞歸方法來編寫算法。一般來說，遞歸算法結(jié)構(gòu)簡潔而清晰，可以用歸納法證明其正確性，并易于算法分析。

根據(jù)斐波那契數(shù)列的遞歸定義，可以很自然地寫出計算Fn的遞歸算法。為了便于在表達(dá)式中直接引用，可以把它設(shè)計成一個函數(shù)過程，見程序1-4。

【程序1-4】 求Fn

long Fib( long n)
{
      if(n<=1) return n;
      else return Fib(n-2)+Fib(n-1);
}

函數(shù)Fib(n)中又調(diào)用了函數(shù)Fib(n-1)和Fib(n-2)。這種在函數(shù)體內(nèi)調(diào)用自己的做法稱為遞歸調(diào)用，包含遞歸調(diào)用的函數(shù)稱為遞歸函數(shù)（recursive function）。從實(shí)現(xiàn)方法上講，遞歸調(diào)用與調(diào)用其他函數(shù)沒有什么兩樣。設(shè)有一個函數(shù)P，它調(diào)用函數(shù)Q(T x)，P被稱為調(diào)用函數(shù)（calling function），而Q稱為被調(diào)函數(shù)（called function）。在調(diào)用函數(shù)P中，使用Q(a)來引起被調(diào)函數(shù)Q的執(zhí)行，這里a稱為實(shí)在參數(shù)（actual parameter），x稱為形式參數(shù)（formal parameter）。當(dāng)被調(diào)函數(shù)是P本身時，P是遞歸函數(shù)。有時，遞歸調(diào)用還可以是間接的。對于間接遞歸調(diào)用，在這里不做進(jìn)一步討論。編譯程序利用系統(tǒng)棧實(shí)現(xiàn)函數(shù)的遞歸調(diào)用，系統(tǒng)棧是實(shí)現(xiàn)函數(shù)嵌套調(diào)用的基礎(chǔ)。

可以用所謂的遞歸樹（recursive tree）來描述程序1-4的函數(shù)Fib執(zhí)行時的調(diào)用關(guān)系。假定在主函數(shù)main中調(diào)用Fib(4)，讓我們來看Fib(4)的執(zhí)行過程。這一過程可以用圖1-2所示的遞歸樹描述。從圖中可見，F(xiàn)ib(4)需要分別調(diào)用Fib(2)和Fib(3)，F(xiàn)ib(2)又分別調(diào)用Fib(0)和Fib(1)，……。其中，F(xiàn)ib(0)被調(diào)用了兩次，F(xiàn)ib(1)被調(diào)用了三次，F(xiàn)ib(2)被調(diào)用了兩次。可見，許多計算工作是重復(fù)的，當(dāng)然這是費(fèi)時的。

3.遞歸數(shù)據(jù)結(jié)構(gòu)

在數(shù)據(jù)結(jié)構(gòu)中，樹、二叉樹和列表常采用遞歸方式來定義。原則上，線性表、數(shù)組、字符串等也可以進(jìn)行遞歸定義。但是習(xí)慣上，許多數(shù)據(jù)結(jié)構(gòu)并不采用遞歸定義方式，而是直接定義。線性表、字符串和數(shù)組等數(shù)據(jù)結(jié)構(gòu)的直接定義方式更自然、更直截了當(dāng)。使用遞歸方式定義的數(shù)據(jù)結(jié)構(gòu)稱為遞歸數(shù)據(jù)結(jié)構(gòu)（recursive data structure）。

1.4.2 遞歸算法示例

設(shè)計遞歸算法需要使用一種新的思維方式。遞歸概念較難掌握，本節(jié)的例子可以加深對遞歸算法的理解。

例1-2 逆序輸出正整數(shù)的各位數(shù)

設(shè)有正整數(shù)n=12345，現(xiàn)希望以各位數(shù)的逆序形式輸出，即輸出54321。設(shè)k位正整數(shù)為d1d2…dk，為了以逆序形式輸出各位數(shù)dkdk-1…d1，可以分成兩步：

（1）首先輸出末位數(shù)dk；

（2）然后輸出由前k-1位組成的正整數(shù)d1d2…dk-1的逆序形式。

上面的步驟很容易寫成程序1-5的遞歸算法。

【程序1-5】 逆序輸出正整數(shù)的各位數(shù)

#include<iostream.h>
void PrintDigit(unsigned int n)
{ //設(shè)k位正整數(shù)為d1d2Ldk, 按各位數(shù)的逆序dkdk-1Ld1形式輸出
     cout<<n%10; //輸出最后一位數(shù)dk
     if(n>=10) PrintDigit(n/10); //以逆序輸出前k-1位數(shù)
}
void main()
{
     unsigned int n;
     cin>>n;
     PrintDigit(n);
}

例1-3 漢諾塔問題（tower of Hanoi）

假定有三個塔座：X，Y，Z，在塔座X上有n個直徑大小各不相同，按圓盤大小從小到大編號為1，2，…，n的圓盤。現(xiàn)要求將X塔座上n個圓盤移到塔座Y上，并仍按同樣順序疊排，即初始狀態(tài)如圖1-3（a）所示，最終狀態(tài)如圖1-3（d）所示。圓盤移動時必須遵循下列規(guī)則：

（1）每次只能移動一個圓盤；

（2）圓盤可以加到塔座X，Y，Z中任意一個上；

（3）任何時刻都不能將一個較大的圓盤放在較小的圓盤之上。

為了將圓盤全部從塔座X移到塔座Y，并且仍按原順序疊排，一種樸素的想法是：如果能夠?qū)⑺鵛的上面n-1個圓盤移至空閑的塔座Z上，并且這n-1個圓盤要求以原順序疊排。這樣，塔座X上就只剩下一個最大的圓盤，如圖1-3（b）所示。于是，便可以輕而易舉地將最大圓盤放到塔座Y上，如圖1-3（c）所示。余下的問題是如何將n-1個圓盤從塔座Z借助于空閑塔座X移到塔座Y上。相對于原始問題而言，現(xiàn)在要解決的問題的性質(zhì)與原問題相同，但被移動的圓盤數(shù)目少了一個，是相對較小的問題。使用遞歸很容易寫出求解此問題的算法。

假定圓盤從小到大編號為1～n，移動圓盤的算法可以粗略描述如下：

（1）以塔座Y為中介，將前n-1個圓盤從塔座X移到塔座Z上；

（2）將第n個圓盤移到塔座Y上；

（3）以塔座X為中介，將塔座Z上的n-1個圓盤移到塔座Y上。

注意，（1）和（3）求解的是移動n-1個圓盤的漢諾塔問題，在程序1-6求解漢諾塔問題的模擬程序中，它們分別表現(xiàn)為一次遞歸函數(shù)調(diào)用。

【程序1-6】 漢諾塔問題

#include <iostream.h>
enum tower { A='X', B='Y', C='Z'};
void Move(int n,tower x,tower y)
{ //將第n個圓盤從塔座x移到塔座y的頂部
     cout << "The disk "<<n<<" is moved from "
     << char(x) << " to top of tower " << char(y) << endl;
}
void Hanoi(int n, tower x, tower y, tower z)
{ // 將塔座x上部的n個圓盤移到塔座y上，順序不變。
     if (n) {
          Hanoi(n-1, x, z, y); //將前n-1個圓盤從塔座x移到塔座z，塔座y為中介
          Move(n,x,y); //將第n個圓盤從塔座x移到塔座y
          Hanoi(n-1, z, y, x); //將塔座z上的n-1個圓盤移到塔座y上，塔座x為中介
     }
}
void main()
{
     Hanoi(4,A,B,C); //假定n＝4
}

例1-4 產(chǎn)生各種可能的排列

給定n個自然數(shù){0, 1, …, n-1}的集合，設(shè)計一個算法輸出該集合所有可能的排列（permutation）。例如，集合{0, 1, 2}有6種可能的排列：（0, 1, 2）, (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)。容易看到，n個自然數(shù)的集合有n！個不同的排列。下面以4個自然數(shù)的集合{0, 1, 2, 3}為例，介紹一種求解此問題的簡單遞歸算法。

由4個自然數(shù)組成的排列通過下列方式構(gòu)造：

（1）以0開頭，緊隨其后為{1, 2, 3}的各種排列；

（2）以1開頭，緊隨其后為{0, 2, 3}的各種排列；

（3）以2開頭，緊隨其后為{0, 1, 3}的各種排列；

（4）以3開始，緊隨其后為{0, 1, 2}的各種排列。

語句（1）中“緊隨其后為{1, 2, 3}的各種排列”實(shí)質(zhì)上是求解比原始問題少一個數(shù)的排列生成問題。相對原問題而言，這是一個同類子問題，但規(guī)模小一些。這也意味著可用遞歸算法求解這一問題。程序1-7描述這一算法，可用Perm(a, 0, n)調(diào)用之。

【程序1-7】 排列產(chǎn)生算法

template <class T>
void Perm(T a[], int k, int n)
{
     if (k==n-1){ //輸出一種排列
           for (int i=0; i<n; i++)
                 cout << a[i]<< " "; cout << endl;
     }
     else //產(chǎn)生{a[k],…,a[n-1]}各種排列
           for (int i=k; i<n; i++) {
                  T t=a[k]; a[k]=a[i]; a[i]=t;
                  Perm(a, k+1, n); //產(chǎn)生{a[k+1],…,a[n-1]}各種排列
                  t=a[k]; a[k]=a[i]; a[i]=t;
           }
}

1.4.3 歸納證明

證明一個定理不成立的最好方法是舉一個反例。那么，如何證明一個程序是正確的？程序的正確性證明是一個非常困難的問題，一個完整的程序正確性證明過程常常比編寫程序費(fèi)時得多。兩種最常見的證明方法是歸納法和反證法。下面我們采用非形式證明（informal proof）方式討論算法的正確性問題。

先來看歸納法。對于無限對象集上的命題，歸納法往往是唯一可行的證明方法。遞歸數(shù)據(jù)結(jié)構(gòu)的特性和遞歸算法問題常使用歸納法證明。在多數(shù)情況下，歸納法在自然數(shù)或正整數(shù)集合上進(jìn)行，當(dāng)歸納法應(yīng)用于遞歸定義的數(shù)據(jù)結(jié)構(gòu)（如樹和表）時，稱為結(jié)構(gòu)歸納法（structural induction）。下面將看到，遞歸函數(shù)和歸納證明二者在結(jié)構(gòu)上非常類似，這對于運(yùn)用歸納法證明復(fù)雜的遞歸數(shù)據(jù)結(jié)構(gòu)和算法命題是很有幫助的。

程序1-5和程序1-6分別是逆序打印正整數(shù)和漢諾塔問題的遞歸函數(shù)。對于給定的一些測試用例，它們都能正確工作，但并不意味著它們一定是正確的程序。程序正確性證明是非常有用的，只有證明是正確的程序才能確認(rèn)該程序?qū)λ休斎攵寄艿玫秸_的結(jié)果。

使用歸納法進(jìn)行證明的過程由兩部分組成。

（1）基礎(chǔ)情況（base case）確認(rèn)被證明的結(jié)論在某種（某些）基礎(chǔ)情況下是正確的。

（2）歸納步驟（induction step）這一步又可分成兩個子步：首先進(jìn)行歸納假設(shè)，假定當(dāng)問題實(shí)例的規(guī)模小于某個量k時，結(jié)論成立；然后使用這個假設(shè)證明對問題規(guī)模為k的實(shí)例，結(jié)論也成立。至此，結(jié)論得證。

定理1-1 對于n≥0，程序1-5是正確的。

證明：（歸納法證明）

首先，當(dāng)n是1位數(shù)時，程序顯然是正確的，因為它僅執(zhí)行了語句cout<<n%10;。

假定函數(shù)PrintDigit對所有位數(shù)小于k（k＞1）的正整數(shù)都能正確運(yùn)行，當(dāng)n的位數(shù)為k位時，此時有n≥10，算法必定先執(zhí)行語句cout<<n%10;然后執(zhí)行語句if(n>=10) PrintDigit(n/10);。由于n/10（符號x表示不大于x的最大整數(shù)，符號x表示不小于x的最小整數(shù)。）是n的前k-1位數(shù)字形成的數(shù)，歸納法假設(shè)函數(shù)調(diào)用PrintDigit(n/10)能夠?qū)⑺_地（并在有限步內(nèi)）按數(shù)字的逆序輸出，那么，現(xiàn)在先執(zhí)行語句輸出個位數(shù)字（n%10），然后由于按逆序輸出前k-1位數(shù)字的做法是能夠正確按逆序輸出全部k位數(shù)字的，所以程序1-5是正確的。本例中，歸納證明使用的量是十進(jìn)制數(shù)的位數(shù)。

上述證明看起來非常類似于對一個遞歸算法的描述。這正是由于遞歸和歸納是密切相關(guān)的，它們有很多相似之處。二者都是由一個或多個基礎(chǔ)情況來終止的。遞歸函數(shù)通過調(diào)用自身得到較小問題的解，并由較小問題的解來形成相對較大的問題的解。同樣，歸納法證明依靠歸納法假設(shè)的事實(shí)來證明結(jié)論。因此，一個遞歸算法比較容易用歸納法證明其正確性。

同樣地，不難運(yùn)用歸納法證明程序1-6漢諾塔程序的正確性，我們將其留做練習(xí)。

在本書的算法證明和分析中，還常運(yùn)用反證法。為了使用反證法證明一個結(jié)論，首先應(yīng)假設(shè)這個結(jié)論是錯誤的，然后找出由這個假設(shè)導(dǎo)致的邏輯上的矛盾。如果引起矛盾的邏輯是正確的，則表明假設(shè)是錯誤的，所以原結(jié)論是正確的。下面舉一個經(jīng)典的例子說明反證法的運(yùn)用。

定理1-2 存在無窮多個素數(shù)。

證明：（反證法證明）

反面假設(shè)：假設(shè)定理不成立，則存在最大素數(shù)，記為P。令P1，P2，…，Pk-1，P是從小到大依次排列的所有素數(shù)。設(shè)N=P1P2…Pk-1P+1，顯然N＞P，根據(jù)假設(shè)N不是素數(shù)。但P1，P2，…，Pk-1，P都不能整除N，都有余數(shù)為1。這就產(chǎn)生矛盾，因為每一個整數(shù)，或者自己是素數(shù)，或者是素數(shù)的乘積。現(xiàn)在N不是任何素數(shù)的乘積，這也意味著不存在最大素數(shù)，定理得證。

本章小結(jié)

本章概述有關(guān)算法、問題、問題求解過程及算法問題求解方法等貫穿本書的一些重要概念和方法。算法可以看做求解問題的一類特殊的方法，它是精確定義的，能在有限時間內(nèi)獲得答案的一個求解過程。對算法的研究主要包括如何設(shè)計算法，如何表示算法，如何確認(rèn)算法的正確性，如何分析一個算法的效率，以及如何測量程序的性能等方面。算法設(shè)計技術(shù)是問題求解的有效策略。算法的效率通過算法分析來確定。遞歸是強(qiáng)有力的算法結(jié)構(gòu)。遞歸和歸納關(guān)聯(lián)緊密。歸納法是證明遞歸算法正確性和進(jìn)行算法分析的強(qiáng)有力工具。

習(xí)題1

1-1 什么是算法？它與計算過程和程序有什么區(qū)別？

1-2 程序證明和程序測試的目的各是什么？

1-3 用歐幾里得算法求31415和14142的最大公約數(shù)。估算一下程序1-2的算法比程序1-3的算法快多少倍？

1-4 證明等式gcd(m, n)=gcd(n mod m, m)，對每對正整數(shù)m和n，m＞0都成立。

1-5 解釋名詞：問題、問題求解、問題求解過程、軟件生命周期。

1-6 簡述匈牙利數(shù)學(xué)家喬治·波利亞在《如何求解》一書中提出的思想，如何體現(xiàn)在算法問題求解過程中。

1-7 算法研究主要有哪些方面？

1-8 請舉出至少一個算法問題的例子，說明因為數(shù)據(jù)組織方式不同，導(dǎo)致解題效率有顯著差異。

1-9 試給出n！的遞歸定義式，并設(shè)計一個遞歸函數(shù)計算n！。

1-10 使用歸納法，證明上題所設(shè)計的計算n！的遞歸函數(shù)正確性。

1-11 請使用歸納法證明漢諾塔函數(shù)的正確性。

1-12 試用歸納法證明程序1-7的排列產(chǎn)生器算法的正確性。

1-13 寫一個遞歸算法和一個迭代算法計算二項式系數(shù)：

Cnm=Cn-1m+Cn-1m-1=n！/m！(n-m)！

1-14 給定一個字符串s和一個字符x，編寫遞歸算法實(shí)現(xiàn)下列功能：

（1）檢查x是否在s中；

（2）計算x在s中出現(xiàn)的次數(shù)；

（3）刪除s中所有x。

1-15 寫一個C++函數(shù)求解下列問題：給定正整數(shù)n，確定n是否是它所有因子之和。

1-16 S是有n個元素的集合，S的冪集是S所有可能的子集組成的集合。例如，S={a, b, c}，則S的冪集={(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}。寫一個C++遞歸函數(shù)，以S為輸入，輸出S的冪集。