第1部分 算法和算法分析

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

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

1.1 算法概述

1.1.1 什么是算法

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

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

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

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

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

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

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

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

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

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

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

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

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

歐幾里得算法使用了遞歸，其C/C++語(yǔ)言描述見(jiàn)程序1-1。歐幾里得算法的迭代形式描述見(jiàn)程序1-2。請(qǐng)注意數(shù)學(xué)上的運(yùn)算符mod與C/C++語(yǔ)言的“%”運(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;
}

上述程序必定會(huì)結(jié)束，因?yàn)槊垦h(huán)一次，m的新值就會(huì)變小，但絕對(duì)不會(huì)成為負(fù)數(shù)，當(dāng)m=0時(shí)程序終止。

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

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

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;
}

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

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

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

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

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

1.2 問(wèn)題求解方法

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

1.2.1 問(wèn)題和問(wèn)題求解

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

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

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

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

1.2.2 問(wèn)題求解過(guò)程

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

問(wèn)題求解的四步法簡(jiǎn)述如下。

（1）理解問(wèn)題（understand the problem）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3.1 算法問(wèn)題求解過(guò)程

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

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

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

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

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

1.3.2 如何設(shè)計(jì)算法

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

1.3.3 如何表示算法

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

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

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

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

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

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

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

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

1.3.5 如何分析算法

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

1.4 遞歸和歸納

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

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

1.4.1 遞歸

1.遞歸定義

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

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

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

根據(jù)這一定義，可以得到一個(gè)無(wú)窮數(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ù)列的遞歸定義來(lái)計(jì)算。斐波那契數(shù)列的直接計(jì)算公式為：

式中，，

2.遞歸算法

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

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

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

根據(jù)斐波那契數(shù)列的遞歸定義，可以很自然地寫出計(jì)算Fn的遞歸算法。為了便于在表達(dá)式中直接引用，可以把它設(shè)計(jì)成一個(gè)函數(shù)過(guò)程，見(jiàn)程序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ù)沒(méi)有什么兩樣。設(shè)有一個(gè)函數(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)來(lái)引起被調(diào)函數(shù)Q的執(zhí)行，這里a稱為實(shí)在參數(shù)（actual parameter），x稱為形式參數(shù)（formal parameter）。當(dāng)被調(diào)函數(shù)是P本身時(shí)，P是遞歸函數(shù)。有時(shí)，遞歸調(diào)用還可以是間接的。對(duì)于間接遞歸調(diào)用，在這里不做進(jìn)一步討論。編譯程序利用系統(tǒng)棧實(shí)現(xiàn)函數(shù)的遞歸調(diào)用，系統(tǒng)棧是實(shí)現(xiàn)函數(shù)嵌套調(diào)用的基礎(chǔ)。

可以用所謂的遞歸樹(shù)（recursive tree）來(lái)描述程序1-4的函數(shù)Fib執(zhí)行時(shí)的調(diào)用關(guān)系。假定在主函數(shù)main中調(diào)用Fib(4)，讓我們來(lái)看Fib(4)的執(zhí)行過(guò)程。這一過(guò)程可以用圖1-2所示的遞歸樹(shù)描述。從圖中可見(jiàn)，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)用了兩次。可見(jiàn)，許多計(jì)算工作是重復(fù)的，當(dāng)然這是費(fèi)時(shí)的。

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

在數(shù)據(jù)結(jié)構(gòu)中，樹(shù)、二叉樹(shù)和列表常采用遞歸方式來(lái)定義。原則上，線性表、數(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è)計(jì)遞歸算法需要使用一種新的思維方式。遞歸概念較難掌握，本節(jié)的例子可以加深對(duì)遞歸算法的理解。

例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 漢諾塔問(wèn)題（tower of Hanoi）

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

（1）每次只能移動(dòng)一個(gè)圓盤；

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

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

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

假定圓盤從小到大編號(hào)為1～n，移動(dòng)圓盤的算法可以粗略描述如下：

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

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

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

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

【程序1-6】 漢諾塔問(wèn)題

#include <iostream.h>
enum tower { A='X', B='Y', C='Z'};
void Move(int n,tower x,tower y)
{ //將第n個(gè)圓盤從塔座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個(gè)圓盤移到塔座y上，順序不變。
     if (n) {
          Hanoi(n-1, x, z, y); //將前n-1個(gè)圓盤從塔座x移到塔座z，塔座y為中介
          Move(n,x,y); //將第n個(gè)圓盤從塔座x移到塔座y
          Hanoi(n-1, z, y, x); //將塔座z上的n-1個(gè)圓盤移到塔座y上，塔座x為中介
     }
}
void main()
{
     Hanoi(4,A,B,C); //假定n＝4
}

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

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

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

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

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

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

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

語(yǔ)句（1）中“緊隨其后為{1, 2, 3}的各種排列”實(shí)質(zhì)上是求解比原始問(wèn)題少一個(gè)數(shù)的排列生成問(wèn)題。相對(duì)原問(wèn)題而言，這是一個(gè)同類子問(wèn)題，但規(guī)模小一些。這也意味著可用遞歸算法求解這一問(wèn)題。程序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 歸納證明

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

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

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

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

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

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

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

證明：（歸納法證明）

首先，當(dāng)n是1位數(shù)時(shí)，程序顯然是正確的，因?yàn)樗鼉H執(zhí)行了語(yǔ)句cout<<n%10;。

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

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

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

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

定理1-2 存在無(wú)窮多個(gè)素?cái)?shù)。

證明：（反證法證明）

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

本章小結(jié)

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

習(xí)題1

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

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

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

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

1-5 解釋名詞：?jiǎn)栴}、問(wèn)題求解、問(wèn)題求解過(guò)程、軟件生命周期。

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

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

1-8 請(qǐng)舉出至少一個(gè)算法問(wèn)題的例子，說(shuō)明因?yàn)閿?shù)據(jù)組織方式不同，導(dǎo)致解題效率有顯著差異。

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

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

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

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

1-13 寫一個(gè)遞歸算法和一個(gè)迭代算法計(jì)算二項(xiàng)式系數(shù)：

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

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

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

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

（3）刪除s中所有x。

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

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