數(shù)據(jù)結(jié)構(gòu)與算法大全復(fù)習(xí)資料

何謂數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。它用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過(guò)這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。數(shù)據(jù)結(jié)構(gòu)主要研究什么？數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。什么是數(shù)據(jù)結(jié)構(gòu)？什么是邏輯結(jié)構(gòu)和物理結(jié)構(gòu)？數(shù)據(jù)是指由有限的符號(hào)（比如，"0"和"1"，具有其自己的結(jié)構(gòu)、操作、和相應(yīng)的語(yǔ)義）組成的元素的集合。結(jié)構(gòu)是元素之間的關(guān)系的集合。通常來(lái)說(shuō)，一個(gè)數(shù)據(jù)結(jié)構(gòu)DS可以表示為一個(gè)二元組：DS=(D,S),//i.e.,data-structure=(data-part,logic-structure-part)這里D是數(shù)據(jù)元素的集合（或者是“結(jié)點(diǎn)”，可能還含有“數(shù)據(jù)項(xiàng)”或“數(shù)據(jù)域”），S是定義在D（或其他集合）上的關(guān)系的集合，S={R|R:D×D×...}，稱之為元素的邏輯結(jié)構(gòu)。邏輯結(jié)構(gòu)有四種基本類型：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹狀結(jié)構(gòu)和網(wǎng)絡(luò)結(jié)構(gòu)。表和樹是最常用的兩種高效數(shù)據(jù)結(jié)構(gòu)，許多高效的算法可以用這兩種數(shù)據(jù)結(jié)構(gòu)來(lái)設(shè)計(jì)實(shí)現(xiàn)。表是線性結(jié)構(gòu)的（全序關(guān)系），樹(偏序或?qū)哟侮P(guān)系)和圖（局部有序(weak/localorders)）是非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)的存儲(chǔ)鏡像(image)。數(shù)據(jù)結(jié)構(gòu)DS的物理結(jié)構(gòu)P對(duì)應(yīng)于從DS的數(shù)據(jù)元素到存儲(chǔ)區(qū)M（維護(hù)著邏輯結(jié)構(gòu)S）的一個(gè)映射：P:(D,S)-->M存儲(chǔ)器模型：一個(gè)存儲(chǔ)器M是一系列固定大小的存儲(chǔ)單元，每個(gè)單元U有一個(gè)唯一的地址A(U)，該地址被連續(xù)地編碼。每個(gè)單元U有一個(gè)唯一的后繼單元U'=succ(U)。P的四種基本映射模型：順序（sequential）、鏈接（linked）、索引（indexed）和散列（hashing）映射。因此，我們至少可以得到4×4種可能的物理數(shù)據(jù)結(jié)構(gòu)：

sequential(sets)

linkedlists

indexedtrees

hashgraphs

（并不是所有的可能組合都合理）數(shù)據(jù)結(jié)構(gòu)DS上的操作：所有的定義在DS上的操作在改變數(shù)據(jù)元素（節(jié)點(diǎn)）或節(jié)點(diǎn)的域時(shí)必須保持DS的邏輯和物理結(jié)構(gòu)。DS上的基本操作：任何其他對(duì)DS的高級(jí)操作都可以用這些基本操作來(lái)實(shí)現(xiàn)。最好將DS和他的所有基本操作看作一個(gè)整體——稱之為模塊。我們可以進(jìn)一步將該模塊抽象為數(shù)據(jù)類型（其中DS的存儲(chǔ)結(jié)構(gòu)被表示為私有成員，基本操作被表示為公共方法），稱之為ADT。作為ADT，堆棧和隊(duì)列都是一種特殊的表，他們擁有表的操作的子集。對(duì)于DATs的高級(jí)操作可以被設(shè)計(jì)為（不封裝的）算法，利用基本操作對(duì)DS進(jìn)行處理。好的和壞的DS：如果一個(gè)DS可以通過(guò)某種“線性規(guī)則”被轉(zhuǎn)化為線性的DS（例如線性表），則稱它為好的DS。好的DS通常對(duì)應(yīng)于好的（高效的）算法。這是由計(jì)算機(jī)的計(jì)算能力決定的，因?yàn)橛?jì)算機(jī)本質(zhì)上只能存取邏輯連續(xù)的內(nèi)存單元，因此如何沒(méi)有線性化的結(jié)構(gòu)邏輯上是不可計(jì)算的。比如對(duì)一個(gè)圖進(jìn)行操作，要訪問(wèn)圖的所有結(jié)點(diǎn)，則必須按照某種順序來(lái)依次訪問(wèn)所有節(jié)點(diǎn)（要形成一個(gè)偏序），必須通過(guò)某種方式將圖固有的非線性結(jié)構(gòu)轉(zhuǎn)化為線性結(jié)構(gòu)才能對(duì)圖進(jìn)行操作。樹是好的DS——它有非常簡(jiǎn)單而高效的線性化規(guī)則，因此可以利用樹設(shè)計(jì)出許多非常高效的算法。樹的實(shí)現(xiàn)和使用都很簡(jiǎn)單，但可以解決大量特殊的復(fù)雜問(wèn)題，因此樹是實(shí)際編程中最重要和最有用的一種數(shù)據(jù)結(jié)構(gòu)。樹的結(jié)構(gòu)本質(zhì)上有遞歸的性質(zhì)——每一個(gè)葉節(jié)點(diǎn)可以被一棵子樹所替代，反之亦然。實(shí)際上，每一種遞歸的結(jié)構(gòu)都可以被轉(zhuǎn)化為（或等價(jià)于）樹形結(jié)構(gòu)。計(jì)算機(jī)中數(shù)據(jù)的描述方式我們知道，數(shù)據(jù)可以用不同的形式進(jìn)行描述或存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)器中。最常見的數(shù)據(jù)描述方法有：公式化描述、鏈接描述、間接尋址和模擬指針。公式化描述借助數(shù)學(xué)公式來(lái)確定元素表中的每個(gè)元素分別存儲(chǔ)在何處，也就通過(guò)公式計(jì)算元素的存儲(chǔ)器地址。最簡(jiǎn)單的情形就是把所有元素依次連續(xù)存儲(chǔ)在一片連續(xù)的存儲(chǔ)空間中，這就是通常所說(shuō)的連續(xù)線性表，即數(shù)組。復(fù)雜一點(diǎn)的情形是利用復(fù)雜的函數(shù)關(guān)系根據(jù)元素的某些特征來(lái)計(jì)算元素在內(nèi)存中的位置，這種技術(shù)稱為散列技術(shù)(Hash，經(jīng)常音譯為哈希技術(shù))。在鏈接描述中，元素表中的每個(gè)元素可以存儲(chǔ)在存儲(chǔ)器的不同區(qū)域中，每個(gè)元素都包含一個(gè)指向下一個(gè)元素的指針。這就是通常所說(shuō)的鏈表。這種描述方法的好處是，知道了第一個(gè)元素的位置，就可以依次找到第n個(gè)元素的位置，而且在其中插入元素非常方便，缺點(diǎn)是查找某個(gè)元素要遍歷所有在該元素之前的元素，實(shí)際應(yīng)用中經(jīng)常和公式化描述結(jié)合起來(lái)使用。在間接尋址方式中，元素表中的每個(gè)元素也可以存儲(chǔ)在存儲(chǔ)器的不同區(qū)域中，不同的是，此時(shí)必須保存一張表，該表的第i項(xiàng)指向元素表中的第i個(gè)元素，所以這張表是一個(gè)用來(lái)存儲(chǔ)元素地址的表。指針數(shù)組（元素為指針的數(shù)組）就是這種描述法的應(yīng)用。這種描述方法是公式化描述和鏈接描述的一種折衷方案，同時(shí)具有兩種描述方法的優(yōu)點(diǎn)，但是需要額外的內(nèi)存開銷。模擬指針?lè)浅ｎ愃朴阪溄用枋?，區(qū)別在于它用整數(shù)代替了指針，整數(shù)所扮演的角色與指針?biāo)缪莸慕巧耆嗤ＤM指針的描述方式是鏈接描述和公式化描述的結(jié)合，元素被存儲(chǔ)在不同的區(qū)域中，每個(gè)元素包含一個(gè)指示下一個(gè)元素位置的整數(shù)，可以通過(guò)某種公式由該整數(shù)計(jì)算出下一個(gè)元素的存儲(chǔ)器地址。線性表的游標(biāo)實(shí)現(xiàn)就是模擬指針描述法。

算法Algorithm算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中，無(wú)論是形成解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；確切性：算法的每一步驟必須有確切的定義；輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件；輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。

DidyouknowAlgorithm一詞的由來(lái)Algorithm(算法)一詞本身就十分有趣。初看起來(lái)，這個(gè)詞好像是某人打算要寫“Logarithm”(對(duì)數(shù))一詞但卻把頭四個(gè)字母寫的前后顛倒了。這個(gè)詞一直到1957年之前在Webster'sNewWorldDictionary(《韋氏新世界詞典》)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術(shù))，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程。在中世紀(jì)時(shí)，珠算家用算盤進(jìn)行計(jì)算，而算術(shù)家用算術(shù)進(jìn)行計(jì)算。中世紀(jì)之后，對(duì)這個(gè)詞的起源已經(jīng)拿不準(zhǔn)了，早期的語(yǔ)言學(xué)家試圖推斷它的來(lái)歷，認(rèn)為它是從把a(bǔ)lgiros(費(fèi)力的)+arithmos(數(shù)字)組合起來(lái)派生而成的，但另一些人則不同意這種說(shuō)法，認(rèn)為這個(gè)詞是從“喀斯迪爾國(guó)王Algor”派生而來(lái)的。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實(shí)起源：它來(lái)源于著名的PersianTextbook(《波斯教科書》)的作者的名字AbuJa'farMohammedibnM?saal-Khowarizm（約公元前825年）——從字面上看，這個(gè)名字的意思是“Ja'far的父親，Mohammed和M?sa的兒子，Khowarizm的本地人”。Khowarizm是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm寫了著名的書Kitabaljabrw'al-muqabala(《復(fù)原和化簡(jiǎn)的規(guī)則》)；另一個(gè)詞，“algebra”(代數(shù))，是從他的書的標(biāo)題引出來(lái)的，盡管這本書實(shí)際上根本不是講代數(shù)的。逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語(yǔ)字典所說(shuō)明的，這個(gè)詞是由于同arithmetic(算術(shù))相混淆而形成的錯(cuò)拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學(xué)詞典VollstandigesMathematischesLexicon(《數(shù)學(xué)大全辭典》)，給出了Algorithmus(算法)一詞的如下定義：“在這個(gè)名稱之下，組合了四種類型的算術(shù)計(jì)算的概念，即加法、乘法、減法、除法”。拉頂短語(yǔ)algorithmusinfinitesimalis(無(wú)限小方法)，在當(dāng)時(shí)就用來(lái)表示Leibnitz(萊布尼茲)所發(fā)明的以無(wú)限小量進(jìn)行計(jì)算的微積分方法。1950年左右，algorithm一詞經(jīng)常地同歐幾里德算法(Euclid'salgorithm)聯(lián)系在一起。這個(gè)算法就是在歐幾里德的《幾何原本》(Euclid'sElements,第VII卷，命題i和ii)中所闡述的求兩個(gè)數(shù)的最大公約數(shù)的過(guò)程(即輾轉(zhuǎn)相除法)。

偽代碼的使用UsageofPseudocode偽代碼(Pseudocode)是一種算法描述語(yǔ)言。使用為代碼的目的是為了使被描述的算法可以容易地以任何一種編程語(yǔ)言(Pascal,C,Java,etc)實(shí)現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰，代碼簡(jiǎn)單，可讀性好，并且類似自然語(yǔ)言。下面介紹一種類Pascal語(yǔ)言的偽代碼的語(yǔ)法規(guī)則。偽代碼的語(yǔ)法規(guī)則在偽代碼中，每一條指令占一行(repeatSuntilC"，需要的時(shí)間等于計(jì)算條件表達(dá)式C需要的時(shí)間與執(zhí)行循環(huán)S體需要的時(shí)間之和乘以循環(huán)的次數(shù)。與規(guī)則5不同，這里的循環(huán)次數(shù)是隱含的。例如，b_search函數(shù)中的while循環(huán)語(yǔ)句。按規(guī)則(1)-(4)，計(jì)算條件表達(dá)式"(notfound)and(U≥=L)"與執(zhí)行循環(huán)體I:=(U+L)div2;ifc=A[I]thenfound:=true

else

if

c>A[I]thenL:=I+1

elseU:=I-1;只需要θ(1)時(shí)間，而循環(huán)次數(shù)為logm，所以，執(zhí)行此while語(yǔ)句只需要θ(logm)時(shí)間。在許多情況下，運(yùn)用規(guī)則(5)和(6)常常須要借助具體算法的內(nèi)涵來(lái)確定循環(huán)的次數(shù)，才不致使時(shí)間的估計(jì)過(guò)于保守。這里舉一個(gè)例子?？疾斐绦蚨危篠ize:=m;1i:=1;1whilei<ndo

begin

i:=i+1;

S1;θ(n)

if

Size>0

then1

begin

在1到Size的范圍內(nèi)任選一個(gè)數(shù)賦值給t;θ(1)

Size:=Size-t;2

forj:=l

to

t

do

S2θ(n)

end;

end;

程序在各行右端頂格處標(biāo)注著執(zhí)行相應(yīng)各行所需要的時(shí)間。如果不對(duì)算法的內(nèi)涵作較深入的考察，只看到1≤t≤Size≤m，就草率地估計(jì)while的內(nèi)循環(huán)for的循環(huán)次數(shù)為Ο(m)，那么，程序在最壞情況下的時(shí)間復(fù)雜性將被估計(jì)為Ο(n2+m·n2)。反之，如果對(duì)算法的內(nèi)涵認(rèn)真地分析，結(jié)果將兩樣。事實(shí)上，在while的循環(huán)體內(nèi)t是動(dòng)態(tài)的,size也是動(dòng)態(tài)的，它們都取決while的循環(huán)參數(shù)i，即t=t(i)記為ti；size=size(i)記為sizei，i=l,2,…,n-1。對(duì)于各個(gè)i，1≤i≤n-1，ti與m的關(guān)系是隱含的，這給準(zhǔn)確地計(jì)算for循環(huán)的循環(huán)體S2被執(zhí)行的次數(shù)帶來(lái)困難。上面的估計(jì)比較保守的原因在于我們把S2的執(zhí)行次數(shù)的統(tǒng)計(jì)過(guò)于局部化。如果不局限于for循環(huán)，而是在整個(gè)程序段上統(tǒng)計(jì)S2被執(zhí)行的總次數(shù)，那么，這個(gè)總次數(shù)等于，又根據(jù)算法中ti的取法及sizei+1=sizei-ti，i=1,2,…,n-1有sizen=size1-。最后利用size1=m和sizen=0得到=m。于是在整個(gè)程序段上，S2被執(zhí)行的總次數(shù)為m，所需要的時(shí)間為θ(mn)。執(zhí)行其他語(yǔ)句所需要的時(shí)間直接運(yùn)用規(guī)則(l)-(6)容易計(jì)算。累加起來(lái)，整個(gè)程序段在最壞情況下時(shí)間復(fù)雜性漸近階為θ(n2+mn)。這個(gè)結(jié)果顯然比前面粗糙的估計(jì)準(zhǔn)確。規(guī)則(7)對(duì)于goto語(yǔ)句。在Pascal中為了便于表達(dá)從循環(huán)體的中途跳轉(zhuǎn)到循環(huán)體的結(jié)束或跳轉(zhuǎn)到循環(huán)語(yǔ)句的后面語(yǔ)句，引入goto語(yǔ)句。如果我們的程序按照這一初衷使用goto語(yǔ)句，那么，在時(shí)間復(fù)雜性分析時(shí)可以假設(shè)它不需要任何額外的時(shí)間。因?yàn)檫@樣做既不會(huì)低估也不會(huì)高估程序在最壞情況下的運(yùn)行時(shí)間的階。如果有的程序?yàn)E用了goto語(yǔ)句，即控制轉(zhuǎn)移到前面的語(yǔ)句，那么情況將變得復(fù)雜起來(lái)。當(dāng)這種轉(zhuǎn)移造成某種循環(huán)時(shí)，只要與別的循環(huán)不交叉，保持循環(huán)的內(nèi)外嵌套，則可以比照規(guī)則(1)-(6)進(jìn)行分析。當(dāng)由于使用goto語(yǔ)句而使程序結(jié)構(gòu)混亂時(shí)，建議改寫程序然后再做分析。規(guī)則(8)對(duì)于過(guò)程調(diào)用和函數(shù)調(diào)用語(yǔ)句，它們需要的時(shí)間包括兩部分，一部分用于實(shí)現(xiàn)控制轉(zhuǎn)移，另一部分用于執(zhí)行過(guò)程(或函數(shù))本身，這時(shí)可以根據(jù)過(guò)程(或函數(shù))調(diào)用的層次，由里向外運(yùn)用規(guī)則(l)-(7)進(jìn)行分析，一層一層地剝，直到計(jì)算出最外層的運(yùn)行時(shí)間便是所求。如果過(guò)程(或函數(shù))出現(xiàn)直接或間接的遞歸調(diào)用，則上述由里向外逐層剝的分析行不通。這時(shí)我們可以對(duì)其中的各個(gè)遞歸過(guò)程(或函數(shù))，所需要的時(shí)間假設(shè)為一個(gè)相應(yīng)規(guī)模的待定函數(shù)。然后一一根據(jù)過(guò)程(或函數(shù))的內(nèi)涵建立起這些待定函數(shù)之間的遞歸關(guān)系得到遞歸方程。最后用求遞歸方程解的漸進(jìn)階的方法確定最壞情況下的復(fù)雜性的漸進(jìn)階。遞歸方程的種類很多，求它們的解的漸近階的方法也很多，我們將在下一段比較系統(tǒng)地給予介紹。本段只舉一個(gè)簡(jiǎn)單遞歸過(guò)程(或函數(shù))的例子來(lái)說(shuō)明如何建立相應(yīng)的遞歸方程，同時(shí)不加推導(dǎo)地給出它們?cè)谧顗那闆r下的時(shí)間復(fù)雜性的漸近階。例：再次考察函數(shù)b_search，這里將它改寫成一個(gè)遞歸函數(shù)。為了簡(jiǎn)明，我們已經(jīng)運(yùn)用前面的規(guī)則(l)-(6)，統(tǒng)計(jì)出執(zhí)行各行語(yǔ)句所需要的時(shí)間，并標(biāo)注在相應(yīng)行的右端：Functionb_search(C,L,U:integer):integer;單位時(shí)間數(shù)varindex,element:integer;

begin

if(U<L)then

1

b_search:=0;

1

else

begin

index:=(L+U)div2;

3

element:=A[index];

2

ifelement=Cthen

1

b_search:=index

1

elseifelement>Cthen

b_search:=b_search(C,L,index-1)

3+T(m/2)

else

b_search:=b_search(C,index+1,U);

3+T(m/2)

end;

end;

其中T(m)是當(dāng)問(wèn)題的規(guī)模U-L+1=m時(shí)b_search在最壞情況下(這時(shí)，數(shù)組A[L..U]中沒(méi)有給定的C)的時(shí)間復(fù)雜性。根據(jù)規(guī)則(l)-(8)，我們有：或化簡(jiǎn)為這是一個(gè)關(guān)于T(m)的遞歸方程。用下一段將介紹的迭代法，容易解得：T(m)=11logm+l3=θ(logm)在結(jié)束這一段之前，我們要提一下關(guān)于算法在最壞情況下的空間復(fù)雜性分析。我們照樣可以給出與分析時(shí)間復(fù)雜性類似的規(guī)則。這里不贅述。然而應(yīng)該指出，在出現(xiàn)過(guò)程(或函數(shù))遞歸調(diào)用時(shí)要考慮到其中隱含的存儲(chǔ)空間的額外開銷。因?yàn)楝F(xiàn)有的實(shí)現(xiàn)過(guò)程(或函數(shù))遞歸調(diào)用的編程技術(shù)需要一個(gè)隱含的、額外(即不出現(xiàn)在程序的說(shuō)明中)的棧來(lái)支持。過(guò)程(或函數(shù))的遞歸調(diào)用每深人一層就把本層的現(xiàn)場(chǎng)局部信息及調(diào)用的返回地址存放在棧頂備用，直到調(diào)用的最里層。因此遞歸調(diào)用一個(gè)過(guò)程(或函數(shù))所需要的額外存儲(chǔ)空間的大小即棧的規(guī)模與遞歸調(diào)用的深度成正比，其比例因子等于每深入一層需要保存的數(shù)據(jù)量。比如本段前面所舉的遞歸函數(shù)b_search，在最壞情況下，遞歸調(diào)用的深度為logm，因而在最壞情況下調(diào)用它所需要的額外存儲(chǔ)空間為θ(logm)。遞歸方程解的漸近階的求法上一章所介紹的遞歸算法在最壞情況下的時(shí)間復(fù)雜性漸近階的分析，都轉(zhuǎn)化為求相應(yīng)的一個(gè)遞歸方程的解的漸近階。因此，求遞歸方程的解的漸近階是對(duì)遞歸算法進(jìn)行分析的關(guān)鍵步驟。遞歸方程的形式多種多樣，求其解的漸近階的方法也多種多樣。這里只介紹比較實(shí)用的五種方法。代入法這個(gè)方法的基本步驟是先推測(cè)遞歸方程的顯式解，然后用數(shù)學(xué)歸納法證明這一推測(cè)的正確性。那么，顯式解的漸近階即為所求。迭代法

這個(gè)方法的基本步驟是通過(guò)反復(fù)迭代，將遞歸方程的右端變換成一個(gè)級(jí)數(shù)，然后求級(jí)數(shù)的和，再估計(jì)和的漸近階；或者，不求級(jí)數(shù)的和而直接估計(jì)級(jí)數(shù)的漸近階，從而達(dá)到對(duì)遞歸方程解的漸近階的估計(jì)。套用公式法這個(gè)方法針對(duì)形如：T(n)=aT(n/b)+f(n)的遞歸方程，給出三種情況下方程解的漸近階的三個(gè)相應(yīng)估計(jì)公式供套用。差分方程法

有些遞歸方程可以看成一個(gè)差分方程，因而可以用解差分方程(初值問(wèn)題)的方法來(lái)解遞歸方程。然后對(duì)得到的解作漸近階的估計(jì)。母函數(shù)法這是一個(gè)有廣泛適用性的方法。它不僅可以用來(lái)求解線性常系數(shù)高階齊次和非齊次的遞歸方程，而且可以用來(lái)求解線性變系數(shù)高階齊次和非齊次的遞歸方程，甚至可以用來(lái)求解非線性遞歸方程。方法的基本思想是設(shè)定遞歸方程解的母函數(shù)，努力建立一個(gè)關(guān)于母函數(shù)的可解方程，將其解出，然后返回遞歸方程的解。本章將逐一地介紹上述五種井法，并分別舉例加以說(shuō)明。本來(lái)，遞歸方程都帶有初始條件，為了簡(jiǎn)明起見，我們?cè)谙旅娴挠懻撝新匀ミ@些初始條件。遞歸方程組解的漸進(jìn)階的求法——代入法用這個(gè)辦法既可估計(jì)上界也可估計(jì)下界。如前面所指出，方法的關(guān)鍵步驟在于預(yù)先對(duì)解答作出推測(cè)，然后用數(shù)學(xué)歸納法證明推測(cè)的正確性。例如，我們要估計(jì)T(n)的上界，T(n)滿足遞歸方程：其中是地板(floors)函數(shù)的記號(hào)，表示不大于n的最大整數(shù)。我們推測(cè)T(n)=O(nlogn)，即推測(cè)存在正的常數(shù)C和自然數(shù)n0，使得當(dāng)n≥n0時(shí)有：T(n)≤Cnlogn(6.2)事實(shí)上，取n0=22=4，并取那么，當(dāng)n0≤n≤2n0時(shí)，(6.2)成立。今歸納假設(shè)當(dāng)2k-1n0≤n≤2kn0，k≥1時(shí)，(1.1.16)成立。那么，當(dāng)2kn0≤n≤2k+1n0時(shí)，我們有：即(6.2)仍然成立，于是對(duì)所有n≥n0，(6.2)成立?？梢娢覀兊耐茰y(cè)是正確的。因而得出結(jié)論：遞歸方程(6.1)的解的漸近階為O(nlogn)。這個(gè)方法的局限性在于它只適合容易推測(cè)出答案的遞歸方程或善于進(jìn)行推測(cè)的高手。推測(cè)遞歸方程的正確解，沒(méi)有一般的方法，得靠經(jīng)驗(yàn)的積累和洞察力。我們?cè)谶@里提三點(diǎn)建議：(1)如果一個(gè)遞歸方程類似于你從前見過(guò)的已知其解的方程，那么推測(cè)它有類似的解是合理的。作為例子，考慮遞歸方程：右邊項(xiàng)的變?cè)屑恿艘粋€(gè)數(shù)17，使得方程看起來(lái)難于推測(cè)。但是它在形式上與(6.1)很類似。實(shí)際上，當(dāng)n充分大時(shí)與相差無(wú)幾。因此可以推測(cè)(6.3)與(6.1)有類似的上界T(n)=O(nlogn)。進(jìn)一步，數(shù)學(xué)歸納將證明此推測(cè)是正確的。(2)從較寬松的界開始推測(cè)，逐步逼近精確界。比如對(duì)于遞歸方程(6.1)，要估計(jì)其解的漸近下界。由于明顯地有T(n)≥n，我們可以從推測(cè)T(n)=Ω(n)開始，發(fā)現(xiàn)太松后，把推測(cè)的階往上提，就可以得到T(n)=Ω(nlogn)的精確估計(jì)。(3)作變?cè)奶鎿Q有時(shí)會(huì)使一個(gè)末知其解的遞歸方程變成類似于你曾見過(guò)的已知其解的方程，從而使得只要將變換后的方程的正確解的變?cè)髂孀儞Q，便可得到所需要的解。例如考慮遞歸方程：看起來(lái)很復(fù)雜，因?yàn)橛叶俗冊(cè)袔Ц?hào)。但是，如果作變?cè)鎿Qm=logn，即令n=2m，將其代入(6.4)，則(6.4)變成：把m限制在正偶數(shù)集上，則(6.5)又可改寫為：T(2m)=2T(2m/2)+m若令S(m)=T(2m)，則S(m)滿足的遞歸方程：S(m)=2S(m/2)+m，與(6.1)類似，因而有：S(m)=O(m1ogm)，進(jìn)而得到T(n)=T(2m)=S(m)=O(m1ogm)=O(lognloglogn)(6.6)上面的論證只能表明：當(dāng)(充分大的)n是2的正偶次冪或換句話說(shuō)是4的正整數(shù)次冪時(shí)(6.6)才成立。進(jìn)一步的分析表明(6.6)對(duì)所有充分大的正整數(shù)n都成立，從而，遞歸方程(6.4)解的漸近階得到估計(jì)。在使用代入法時(shí)，有三點(diǎn)要提醒：(1)記號(hào)O不能濫用。比如，在估計(jì)(6.1)解的上界時(shí)，有人可能會(huì)推測(cè)T(n)=O(n)，即對(duì)于充分大的n，有T(n)≤Cn，其中C是確定的正的常數(shù)。他進(jìn)一步運(yùn)用數(shù)學(xué)歸納法，推出：從而認(rèn)為推測(cè)T(n)=O(n)是正確的。實(shí)際上，這個(gè)推測(cè)是錯(cuò)誤的，原因是他濫用了記號(hào)O，錯(cuò)誤地把(C+l)n與Cn等同起來(lái)。(2)當(dāng)對(duì)遞歸方程解的漸近階的推測(cè)無(wú)可非議，但用數(shù)學(xué)歸納法去論證又通不過(guò)時(shí)，不妨在原有推測(cè)的基礎(chǔ)上減去一個(gè)低階項(xiàng)再試試。作為一個(gè)例子，考慮遞歸方程其中是天花板(floors)函數(shù)的記號(hào)。我們推測(cè)解的漸近上界為O(n)。我們要設(shè)法證明對(duì)于適當(dāng)選擇的正常數(shù)C和自然數(shù)n0，當(dāng)n≥n0時(shí)有T(n)≤Cn。把我們的推測(cè)代入遞歸方程，得到：我們不能由此推斷T(n)≤Cn，歸納法碰到障礙。原因在于(6.8)的右端比Cn多出一個(gè)低階常量。為了抵消這一低階量，我們可在原推測(cè)中減去一個(gè)待定的低階量b，即修改原來(lái)的推測(cè)為T(n)≤Cn-b。現(xiàn)在將它代人(6.7)，得到：只要b≥1，新的推測(cè)在歸納法中將得到通過(guò)。(3)因?yàn)槲覀円烙?jì)的是遞歸方程解的漸近階，所以不必要求所作的推測(cè)對(duì)遞歸方程的初始條件（如T(0)、T(1)）成立，而只要對(duì)T(n)成立，其中n充分大。比如，我們推測(cè)(6.1)的解T(n)≤Cnlogn，而且已被證明是正確的，但是當(dāng)n=l時(shí)，這個(gè)推測(cè)卻不成立，因?yàn)?Cnlogn)|n=1=0而T(l)>0。遞歸方程組解的漸進(jìn)階的求法——迭代法用這個(gè)方法估計(jì)遞歸方程解的漸近階不要求推測(cè)解的漸近表達(dá)式，但要求較多的代數(shù)運(yùn)算。方法的思想是迭代地展開遞歸方程的右端，使之成為一個(gè)非遞歸的和式，然后通過(guò)對(duì)和式的估計(jì)來(lái)達(dá)到對(duì)方程左端即方程的解的估計(jì)。作為一個(gè)例子，考慮遞歸方程：接連迭代二次可將右端項(xiàng)展開為：由于對(duì)地板函數(shù)有恒等式：(6.10)式可化簡(jiǎn)為：這仍然是一個(gè)遞歸方程，右端項(xiàng)還應(yīng)該繼續(xù)展開。容易看出，迭代i次后，將有（6.11）而且當(dāng)時(shí)，(6.11)不再是遞歸方程。這時(shí)：(6.13)又因?yàn)閇a]≤a，由(6.13)可得：而由(6.12)，知i≤log4n，從而，代人(6.14)得：即方程(6.9)的解

T(n)=O(n)。從這個(gè)例子可見迭代法導(dǎo)致繁雜的代數(shù)運(yùn)算。但認(rèn)真觀察一下，要點(diǎn)在于確定達(dá)到初始條件的迭代次數(shù)和抓住每次迭代產(chǎn)生出來(lái)的"自由項(xiàng)"(與T無(wú)關(guān)的項(xiàng))遵循的規(guī)律。順便指出，迭代法的前幾步迭代的結(jié)果常常能啟發(fā)我們給出遞歸方程解的漸近階的正確推測(cè)。這時(shí)若換用代入法，將可免去上述繁雜的代數(shù)運(yùn)算。圖6-1與方程(6.15)相應(yīng)的遞歸樹為了使迭代法的步驟直觀簡(jiǎn)明、圖表化，我們引入遞歸樹?？恐f歸樹，人們可以很快地得到遞歸方程解的漸近階。它對(duì)描述分治算法的遞歸方程特別有效。我們以遞歸方程T(n)=2T(n/2)+n2(6.15)為例加以說(shuō)明。圖6-1展示出(6.15)在迭代過(guò)程中遞歸樹的演變。為了方便，我們假設(shè)n恰好是2的冪。在這里，遞歸樹是一棵二叉樹，因?yàn)?6.15)右端的遞歸項(xiàng)2T(n/2)可看成T(n/2)+T(n/2)。圖6-1(a)表示T(n)集中在遞歸樹的根處，(b)表示T(n)已按(6.15)展開。也就是將組成它的自由項(xiàng)n2留在原處，而將2個(gè)遞歸項(xiàng)T(n/2)分別攤給它的2個(gè)兒子結(jié)點(diǎn)。(c)表示迭代被執(zhí)行一次。圖6-1(d)展示出迭代的最終結(jié)果。圖6-1中的每一棵遞歸樹的所有結(jié)點(diǎn)的值之和都等于T(n)。特別，已不含遞歸項(xiàng)的遞歸樹(d)中所有結(jié)點(diǎn)的值之和亦然。我們的目的是估計(jì)這個(gè)和T(n)。我們看到有一個(gè)表格化的辦法：先按橫向求出每層結(jié)點(diǎn)的值之和，并記錄在各相應(yīng)層右端頂格處，然后從根到葉逐層地將頂格處的結(jié)果加起來(lái)便是我們要求的結(jié)果。照此，我們得到(6.15)解的漸近階為θ(n2)。再舉一個(gè)例子。遞歸方程：T(n)=T(n/3)+T(2n/3)+n(6.16)的迭代過(guò)程相應(yīng)的遞歸樹如圖6-2所示。其中，為了簡(jiǎn)明，再一次略去地板函數(shù)和天花板函數(shù)。圖6-2迭代法解(6.16)的遞歸樹當(dāng)我們累計(jì)遞歸樹各層的值時(shí)，得到每一層的和都等于n，從根到葉的最長(zhǎng)路徑是設(shè)最長(zhǎng)路徑的長(zhǎng)度為k，則應(yīng)該有，得，于是即T(n)=O(nlogn)。以上兩個(gè)例子表明，借助于遞歸樹，迭代法變得十分簡(jiǎn)單易行。遞歸方程組解的漸進(jìn)階的求法——套用公式法這個(gè)方法為估計(jì)形如：T(n)=aT(n/b)+f(n)(6.17)的遞歸方程解的漸近階提供三個(gè)可套用的公式。(6.17)中的a≥1和b≥1是常數(shù)，f(n)是一個(gè)確定的正函數(shù)。(6.17)是一類分治法的時(shí)間復(fù)雜性所滿足的遞歸關(guān)系，即一個(gè)規(guī)模為n的問(wèn)題被分成規(guī)模均為n/b的a個(gè)子間題，遞歸地求解這a個(gè)子問(wèn)題，然后通過(guò)對(duì)這a個(gè)子間題的解的綜合，得到原問(wèn)題的解。如果用T(n)表示規(guī)模為n的原問(wèn)題的復(fù)雜性，用f(n)表示把原問(wèn)題分成a個(gè)子問(wèn)題和將a個(gè)子問(wèn)題的解綜合為原問(wèn)題的解所需要的時(shí)間，我們便有方程(6.17)。這個(gè)方法依據(jù)的是如下的定理：設(shè)a≥1和b≥1是常數(shù)f(n)是定義在非負(fù)整數(shù)上的一個(gè)確定的非負(fù)函數(shù)。又設(shè)T(n)也是定義在非負(fù)整數(shù)上的一個(gè)非負(fù)函數(shù)，且滿足遞歸方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三類情況下，我們有T(n)的漸近估計(jì)式：若對(duì)于某常數(shù)ε>0，有

，

則

；若

，

則

；若對(duì)其常數(shù)ε>0，有

且對(duì)于某常數(shù)c>1和所有充分大的正整數(shù)n有af(n/b)≤cf(n)，則T(n)=θ(f(n))。這里省略定理的證明。在應(yīng)用這個(gè)定理到一些實(shí)例之前，讓我們先指出定理的直觀含義，以幫助讀者理解這個(gè)定理。讀者可能已經(jīng)注意到，這里涉及的三類情況，都是拿f(n)與作比較。定理直觀地告訴我們，遞歸方程解的漸近階由這兩個(gè)函數(shù)中的較大者決定。在第一類情況下，函數(shù)較大，則T(n)=θ()；在第三類情況下，函數(shù)f(n)較大，則T(n)=θ(f(n))；在第二類情況下，兩個(gè)函數(shù)一樣大，則T(n)=θ()，即以n的對(duì)數(shù)作為因子乘上f(n)與T(n)的同階。此外，定理中的一些細(xì)節(jié)不能忽視。在第一類情況下f(n)不僅必須比小，而且必須是多項(xiàng)式地比小，即f(n)必須漸近地小于與的積，ε是一個(gè)正的常數(shù)；在第三類情況下f(n)不僅必須比大，而且必須是多項(xiàng)式地比大，還要滿足附加的“正規(guī)性”條件：af(n/b)≤cf(n)。這個(gè)附加的“正規(guī)性”條件的直觀含義是a個(gè)子間題的再分解和再綜合所需要的時(shí)間最多與原問(wèn)題的分解和綜合所需要的時(shí)間同階。我們?cè)谝话闱闆r下將碰到的以多項(xiàng)式為界的函數(shù)基本上都滿足這個(gè)正規(guī)性條件。還有一點(diǎn)很重要，即要認(rèn)識(shí)到上述三類情況并沒(méi)有覆蓋所有可能的f(n)。在第一類情況和第二類情況之間有一個(gè)間隙：f(n)小于但不是多項(xiàng)式地小于；類似地，在第二類情況和第三類情況之間也有一個(gè)間隙：f(n)大于但不是多項(xiàng)式地大于。如果函數(shù)f(n)落在這兩個(gè)間隙之一中，或者雖有，但正規(guī)性條件不滿足，那么，本定理無(wú)能為力。下面是幾個(gè)應(yīng)用例子。例1考慮T(n)=9T(n/3)+n0對(duì)照(6.17)，我們有a=9，b=3，f(n)=n，，取，便有，可套用第一類情況的公式，得T(n)=θ(n2)。例2考慮T(n)=T(2n/3)+1對(duì)照(6.17)，我們有a=1，b=3/2，f(n)=1，，可套用第二類情況的公式，得T(n)=θ(logn)。例3考慮T(n)=3T(n/4)+nlogn對(duì)照(6.17)，我們有a=3，b=4，f(n)=nlogn，，只要取，便有。進(jìn)一步，檢查正規(guī)性條件：只要取c=3/4，便有af(n/b)≤cf(n)，即正規(guī)性條件也滿足?？商子玫谌惽闆r的公式，得T(n)=θ(f(n))=θ(nlogn)。最后舉一個(gè)本方法對(duì)之無(wú)能為力的例子?？紤]T(n)=2T(n/2)+nlogn對(duì)照(6.17)，我們有a=2，b=2，f(n)=nlogn，，雖然f(n)漸近地大于，但f(n)并不是多項(xiàng)式地大于，因?yàn)閷?duì)于任意的正常數(shù)ε，，即f(n)在第二類情況與第三類情況的間隙里，本方法對(duì)它無(wú)能為力。

遞歸方程組解的漸進(jìn)階的求法——差分方程法這里只考慮形如：T(n)=c1T(n-1)+c2T(n-2)+…+ckT(n-k)+f(n)，n≥k(6.18)的遞歸方程。其中ci(i=l，2，…，k)為實(shí)常數(shù)，且ck≠0。它可改寫為一個(gè)線性常系數(shù)k階非齊次的差分方程：T(n)-c1T(n-1)-c2T(n-2)-…-ckT(n-k)=f(n)，n≥k(6.19)(6.19)與線性常系數(shù)k階非齊次常微分方程的結(jié)構(gòu)十分相似，因而解法類同。限于篇幅，這里直接給出(6.19)的解法，略去其正確性的證明。第一步，求(6.19)所對(duì)應(yīng)的齊次方程：T(n)-c1T(n-1)-c2T(n-2)-…-ckT(n-k)=0(6.20)的基本解系：寫出(6.20)的特征方程：C(t)=tk-c1tk-1-c2tk-2-…-ck=0(6.21)若t=r是(6.21)的m重實(shí)根，則得(6.20)的m個(gè)基礎(chǔ)解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一對(duì)l重的共扼復(fù)根，則得(6.20)的2l個(gè)基礎(chǔ)解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k個(gè)的基礎(chǔ)解。而且，這k個(gè)基礎(chǔ)解構(gòu)成了(6.20)的基礎(chǔ)解系。即(6.20)的任意一個(gè)解都可以表示成這k個(gè)基礎(chǔ)解的線性組合。第二步，求(6.19)的一個(gè)特解。理論上，(6.19)的特解可以用Lagrange常數(shù)變易法得到。但其中要用到(6.20)的通解的顯式表達(dá)，即(6.20)的基礎(chǔ)解系的線性組合，十分麻煩。因此在實(shí)際中，常常采用試探法，也就是根據(jù)f(n)的特點(diǎn)推測(cè)特解的形式，留下若干可調(diào)的常數(shù)，將推測(cè)解代人(6.19)后確定。由于(6.19)的特殊性，可以利用迭加原理，將f(n)線性分解為若干個(gè)單項(xiàng)之和并求出各單項(xiàng)相應(yīng)的特解，然后迭加便得到f(n)相應(yīng)的特解。這使得試探法更為有效。為了方便，這里對(duì)三種特殊形式的f(n)，給出(6.19)的相應(yīng)特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常數(shù)。表6-1方程(6.19)的常用特解形式f(n)的形式條

件方程(6.19)的特解的形式anC(a)≠0a是C(t)的m重根nsC(1)≠01是C(t)的m重根nsanC(a)≠0a是C(t)的m重根第三步，寫出(6.19)即(6.18)的通解(6.22)其中{Ti(n)，i=0,1,2,…,n}是(6.20)的基礎(chǔ)解系，g(n)是(6.19)的一個(gè)特解。然后由(6.18)的初始條件T(i)=Ti，i=1,2,…,k-1來(lái)確定(6.22)中的待定的組合常數(shù){ai}，即依靠線性方程組或解出{ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。第四步，估計(jì)(6.22)的漸近階，即為所要求。下面用兩個(gè)例子加以說(shuō)明。例l考慮遞歸方程它的相應(yīng)特征方程為：C(t)=t2-t-1=0解之得兩個(gè)單根和。相應(yīng)的(6.20)的基礎(chǔ)解系為{r0n，r1n}。相應(yīng)的(6.19)的一個(gè)特解為F*(n)=-8，因而相應(yīng)的(6.19)的通解為：F(n)=a0r0n+a1r1n-8令其滿足初始條件，得二階線性方程組：或或解之得，，從而于是。例2考慮遞歸方程T(n)=4T(n-1)-4T(n-2)+2nn(6.23)和初始條件T(0)=0，T(1)=4/3。它對(duì)應(yīng)的特征方程(6.21)為C(t)=t2-4t+4=0有一個(gè)兩重根r=2。故相應(yīng)的(6.20)的基礎(chǔ)解系為{2n，2nn}。由于f(n)=2nn，利用表6-1，相應(yīng)的(6.19)的一個(gè)特解為T*(n)=n2(p0+p1n)2n，代人(6.23)，定出p0=1/2，p1=1/6。因此相應(yīng)的(6.19)的通解為：T(n)=a02n+a1n2n+n2(1/2+n/6)2n，令其滿足初始條件得a0=a1=0，從而T(n)=n2(1/2+n/6)2n于是T(n)=θ(n32n)。遞歸方程組解的漸進(jìn)階的求法——母函數(shù)法關(guān)于T(n)的遞歸方程的解的母函數(shù)通常設(shè)為：(6.24)當(dāng)(6.24)右端由于T(n)增長(zhǎng)太快而僅在x=0處收斂時(shí)可另設(shè)(6.25)如果我們可以利用遞歸方程建立A(x)的一個(gè)定解方程并將其解出，那么，把A(x)展開成冪級(jí)數(shù)，則xn或xn/n!項(xiàng)的系數(shù)便是所求的遞歸方程的解。其漸近階可接著進(jìn)行估計(jì)。下面舉兩個(gè)例子加以說(shuō)明。例1考慮線性變系數(shù)二階齊次遞歸方程(n-1)T(n)=(n-2)T(n-1)+2T(n-2)，n≥2(6.26)和初始條件T(0)=0，T(1)=1。根據(jù)初始條件及(6.26)，可計(jì)算T(2)=0，T(3)=T(1)=1。設(shè){T(n)}的母函數(shù)為：由于T(0)=T(2)=0，T(1)=1，有：令B(x)=A(x)/x，即：那么：利用(6.26)并代入T(3)=1，得即兩邊同時(shí)沿[0,x]積分，并注意到B(0)=1，有：把B(x)展開成冪級(jí)數(shù)，得從而最后得例2考慮線性變系數(shù)一階非齊次遞歸方程D(n)=nD(n-1)+(-1)n

n≥1(6.27)及初始條件D(0)=1很明顯D(n)隨n的增大而急劇增長(zhǎng)。如果仍采用(6.24)形式的函數(shù)，則(6.24)的右端可能僅在x=0處收斂，所以這里的母函數(shù)設(shè)為：用xn/n!乘以(6.27)的兩端，然后從1到∞求和得：化簡(jiǎn)并用母函數(shù)表達(dá)，有：A(x)-1=xA(x)+e-x-1或(1-x)A(x)=e-x從而A(x)=e-x/(1-x)展成冪級(jí)數(shù)，則：故算法設(shè)計(jì)策略這里介紹了一般的算法設(shè)計(jì)策略，闡述各方法的理論基礎(chǔ)、主要思想及其適用范圍。同時(shí)針對(duì)一些具體問(wèn)題來(lái)講述如何用這些一般的理論以及各種抽象數(shù)據(jù)類型對(duì)問(wèn)題進(jìn)行抽象描述，并用最有效的方式設(shè)計(jì)出解決問(wèn)題的高效算法。它們將生動(dòng)地再現(xiàn)計(jì)算機(jī)程序設(shè)計(jì)方法學(xué)的理論、抽象和設(shè)計(jì)三個(gè)過(guò)程，而且，通過(guò)對(duì)算法正確性的證明和復(fù)雜性的分析，深化對(duì)大問(wèn)題的復(fù)雜性、概念和形式模型、效率和抽象的層次、折衷和結(jié)論等在計(jì)算機(jī)學(xué)科中重復(fù)出現(xiàn)的概念的理解。必須強(qiáng)調(diào)指出，對(duì)于某些問(wèn)題(如NP--完全問(wèn)題)而言，用這里的方法和任何已知的方法都不可能設(shè)計(jì)出有效的算法。對(duì)于這種問(wèn)題，人們常?？紤]利用具體輸入的某些特點(diǎn)來(lái)設(shè)計(jì)有效算法或設(shè)計(jì)求問(wèn)題近似解的有效算法。這一部分內(nèi)容我們將在高級(jí)專題中討論。在對(duì)有關(guān)算法進(jìn)行形式描述時(shí)我們采用類Pascal的偽代碼，并作了一些簡(jiǎn)化，略去不言而喻的一些說(shuō)明，如函數(shù)、形參、變量等類型說(shuō)明。這里主要討論的算法設(shè)計(jì)策略有：遞歸技術(shù)——最常用的算法設(shè)計(jì)思想，體現(xiàn)于許多優(yōu)秀算法之中分治法——分而制之的算法思想，體現(xiàn)了一分為二的哲學(xué)思想模擬法——用計(jì)算機(jī)模擬實(shí)際場(chǎng)景，經(jīng)常用于與概率有關(guān)的問(wèn)題貪心算法——采用貪心策略的算法設(shè)計(jì)狀態(tài)空間搜索法——被稱為“萬(wàn)能算法”的算法設(shè)計(jì)策略隨機(jī)算法——利用隨機(jī)選擇自適應(yīng)地決定優(yōu)先搜索的方向動(dòng)態(tài)規(guī)劃——常用的最優(yōu)化問(wèn)題解決方法摘要本文介紹了分治法的基本思想和基本步驟，通過(guò)實(shí)例討論了利用分治策略設(shè)計(jì)算法的途徑。目錄

簡(jiǎn)介

分治法的基本思想

分治法的適用條件

分治法的基本步驟

分治法的復(fù)雜性分析

分治法的幾種變形

分治法的實(shí)例分析

其他資料參考文獻(xiàn)現(xiàn)代計(jì)算機(jī)常用數(shù)據(jù)結(jié)構(gòu)和算法，潘金貴等編著，南京大學(xué)出版社，1992算法與數(shù)據(jù)結(jié)構(gòu)，傅清祥王曉東編著，電子工業(yè)出版社，1998DictionaryofAlgorithms,DataStructures,andProblems，PaulE.Black，/dads/,下載該網(wǎng)站的鏡像（1,682KB）簡(jiǎn)介對(duì)于一個(gè)規(guī)模為n的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法。分治法的基本思想任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問(wèn)題，當(dāng)n=1時(shí)，不需任何計(jì)算。n=2時(shí)，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可，…。而當(dāng)n較大時(shí)，問(wèn)題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問(wèn)題，有時(shí)是相當(dāng)困難的。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。如果原問(wèn)題可分割成k個(gè)子問(wèn)題，1<k≤n，且這些子問(wèn)題都可解，并可利用這些子問(wèn)題的解求出原問(wèn)題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有steparemergedbeforethe"conquer"step.

pipelineddivideandconquer:Adivideandconquerparadigminwhichpartialresultsfromrecursivecallscanbeusedbeforethecallscomplete.Thetechniqueisoftenusefulforreducingthedepthofanalgorithm.

如果你有關(guān)于這兩種算法的資料請(qǐng)告訴我(mailto:Starfish.h@)。分治法的實(shí)例分析以上討論的是分治法的基本思想和一般原則，下面我們用具體的例子來(lái)說(shuō)明如何針對(duì)具體問(wèn)題用分治法來(lái)設(shè)計(jì)有效解法。例1和例2是分治法的經(jīng)典范例，其分解和合并過(guò)程都比較簡(jiǎn)單明顯；例3和例4的合并方法有多種選擇，只有選擇最好的合并方法才能夠改進(jìn)算法的復(fù)雜度；例5是一個(gè)計(jì)算幾何學(xué)中的問(wèn)題，它的合并步驟需要較高的技巧。例6則是IOI'95的試題WiresandSwitches。例1二分查找例2快速排序例3大整數(shù)乘法例4Strassen矩陣乘法例5最接近點(diǎn)對(duì)問(wèn)題例6導(dǎo)線和開關(guān)更多實(shí)例請(qǐng)參閱分治法問(wèn)題集其他資料請(qǐng)參閱以下文章：遞歸技術(shù)貪心法動(dòng)態(tài)規(guī)劃分治法問(wèn)題集

用遞歸中序遍歷二叉樹

#include<stdlib.h>struct

tree

//聲明樹的結(jié)構(gòu)

{

struct

tree

*left;

int

data;

struct

tree

*right;

};typedef

struct

tree

treenode;

type

treenode

*b_tree;

//聲明二叉樹鏈表//插入二叉樹的節(jié)點(diǎn)

b_tree

insert_node(b_tree

root,int

node)

{

b_tree

newnode;

b_tree

currentnode;

b_tree

parentnode;

newnode=(b_tree)malloc(sizeof(treenode));

//建立新節(jié)點(diǎn)的內(nèi)存空間

newnode->data=node;

newnode->right=NULL;

newnode->left=NULL;

if(root=NULL)

return

newnode;

else

{

currentnode=root;

while(currentnode!=NULL)

{

parentnode=currentnode;

if(

currentnode->data>node)

currentnode=currentnode->left;

else

currentnode=currentnode->right;

}

if(parentnode->data>node)

parentnode->left=newnode;

else

parentnode->right=newnode;

}

return

root;

}//

建立二叉樹

b_tree

create_btree(int

*data,int

len)

{

b_tree

root=NULL;

int

i;

for(i=0;i<len;i++)

root=insert_node(root,data[i]);

return

root;

}//二叉樹中序遍歷

void

inorder(b_tree

point)

{

if(point!=NULL)

{

inorder(point->left);

printf("%d",point->data);

inorder(point->right);

}

}//主程序

void

main(

)

{

b_tree

root=NULL;

int

i,index;

int

value;

int

nodelist[20];

printf("\n

pleaase

input

the

elements

of

binary

tree(exit

for

0

):\n");

index=0;

//讀取數(shù)值存到數(shù)組中

scanf("%d",&value);

while(value!=0)

{

nodelist[index]=value];

index=index+1;

scanf("%d",&value);

}

//建立二叉樹

root=create_btree(nodelist,index);

//中序遍歷二叉樹

printf("\nThe

inorder

traversal

result

is

:");

inorder(root);

printf("\n");

}

Bresenham高效畫線算法

畫線的算法不少，但要作到高速、簡(jiǎn)單并不容易。斜率相乘法是最簡(jiǎn)單的方法之一，但計(jì)算每個(gè)點(diǎn)均要花費(fèi)不少時(shí)間用于乘、除法運(yùn)算；下面介紹的是Bresenham's高效畫線算法，對(duì)每個(gè)點(diǎn)的坐標(biāo)計(jì)算只要加、減法就能完成。

簡(jiǎn)化算法用偽Pascal語(yǔ)言描述如下：

procedureDrawLine(x1,y1,x2,y2:Integer);

var

x,y,DeltaX,DeltaY,HalfX,ErrorTerm,i:Integer;

begin

DeltaX:=x2-x1;

DeltaY:=y2-y1;

HalfX:=(x2-x1)shr1;

ErrorTerm:=0;

x:=x1;

y:=y1;

fori:=0toDeltaXdo

begin

Plot(X,Y);

Inc(x);

ErrorTerm:=ErrorTerm+DeltaY;

ifErrorTerm>HalfXthen

begin

ErrorTerm:=ErrorTerm-DeltaX;

Inc(y);

end;

end;

end;

為方便閱讀，上述程序作了簡(jiǎn)化。實(shí)際程序應(yīng)略作修正，以分別處理DeltaX與DeltaY比較大小,必要時(shí)交換起始、結(jié)束點(diǎn)等。

修正后的的偽Pascal算法如下：

procedureDrawLine(x1,y1,x2,y2:Integer);

var

x,y,DeltaX,DeltaY,HalfCount,ErrorTerm,i,Flag:Integer;

begin

DeltaX:=x2-x1;

DeltaY:=y2-y1;ifAbs(DeltaY)<Abs(DeltaX)then

begin

ifDeltaX<0then

begin

i:=x1;x1:=x2;x2:=i;

i:=y1;y1:=y2;y2:=i;

DeltaX:=x2-x1;

DeltaY:=y2-y1;

end;

ifDeltaY<0thenFlag:=-1

elseFlag:=1;

DeltaY:=Abs(DeltaY);

HalfCount:=DeltaXshr1;

ErrorTerm:=0;

x:=x1;

y:=y1;

fori:=0toDeltaXdo

begin

Plot(X,Y);

Inc(x);

ErrorTerm:=ErrorTerm+DeltaY;

ifErrorTerm>HalfCountthen

begin

ErrorTerm:=ErrorTerm-DeltaX;

y:=y+Flag;

end;

end;

end

else

begin

ifDeltaY<0then

begin

i:=x1;x1:=x2;x2:=i;

i:=y1;y1:=y2;y2:=i;

DeltaX:=x2-x1;

DeltaY:=y2-y1;

end;

ifDeltaX<0thenFlag:=-1

elseFlag:=1;

DeltaX:=Abs(DeltaX);

HalfCount:=DeltaYshr1;

ErrorTerm:=0;

x:=x1;

y:=y1;

fori:=0toDeltaYdo

begin

Plot(X,Y);

Inc(y);

ErrorTerm:=ErrorTerm+DeltaX;

ifErrorTerm>HalfCountthen

begin

ErrorTerm:=ErrorTerm-DeltaY;

x:=x+Flag;

end;

end;

end;

end;

C++的沉迷與愛戀

每年的09/28對(duì)於我都是一個(gè)特殊的日子--不只是因?yàn)榻處煿?jié)。今年很特殊地沒(méi)有普天同慶，那麼我就寫篇文章自己慶祝一下好了。

我於今年七月發(fā)表了一本著作<多型與虛擬>和一本譯作<深度探索C++物件模型>，獲得很大的回響。這些作品都不是針對(duì)C++的完全初學(xué)者所寫，但從初階到高階為數(shù)眾多的C++guy，熱情地表達(dá)了他們對(duì)這些主題的喜悅。

在許多來(lái)信中，我看到一些有趣的現(xiàn)象，也感受到一些值得整理下來(lái)的想法。所以，根據(jù)我個(gè)人的學(xué)習(xí)過(guò)往、我的教學(xué)經(jīng)驗(yàn)、以及周遭朋友的心得交流，寫下這篇文章，或可為後學(xué)者戒。●<多型與虛擬>序言節(jié)錄首先讓我節(jié)錄<多型與虛擬>一書序言：<多型與虛擬>序節(jié)錄（侯俊杰/松崗/1998/07）一般而言，C++是一個(gè)難學(xué)易用的語(yǔ)言。C++的難學(xué)，初始在於其重重的布幕，布幕之中編譯器對(duì)我們的程式碼做了太多的手腳，使我們慣於循序思考的工程腦袋一無(wú)所措。及長(zhǎng)，又面臨新的思維模式，使我們必須扭轉(zhuǎn)慣常的思考習(xí)慣。C++的易用則在於其巨大的彈性，能夠以多型（polymorphism）、虛擬（virtual）、模板（template）、泛型（generalization）等種種型式，讓既有的碼去處理未知的、未來(lái)的資料型態(tài)。當(dāng)然，易用必須先能用。用不好或不能用的話，「寫C++程式」最後就成了只是「使用C++編譯器」，這是大家常拿來(lái)彼此調(diào)侃的笑話。在「難學(xué)」的背景下，「易用」是使我們依然前仆後繼的動(dòng)力。愈來(lái)愈多的大學(xué)資訊科系把C++開在大一課程，這雖然說(shuō)明C++是多麼地重要，可也苦了資訊新兵們。其實(shí)「難學(xué)」的最大癥結(jié)在於，很難得有一本書，能夠一針見血地指出多型與虛擬的重要性；在我們粗具語(yǔ)法基礎(chǔ)之後，直接把我們導(dǎo)引到最核心最重要的思想，并且在建立這個(gè)思想的過(guò)程中，提供足夠的必要基礎(chǔ)?！窭щy度之一「C++是個(gè)難學(xué)易用的語(yǔ)言」，這句話相信很多人心有戚戚。C++的學(xué)習(xí)難度，一在於語(yǔ)言本身太多的「幕」，一在於"paradigmshift"（思考模式的移轉(zhuǎn)）。傳統(tǒng)循序語(yǔ)言如C,Pascal,Basic,Fortran...，除了模樣看起來(lái)稍有不同，基本上都是函式call來(lái)call去，大同小異，很容易掌握。你想做的動(dòng)作，在code中都看得一清二楚。你所看不到的，犖犖大者也不過(guò)就是編譯器為你的函式加上用以處理堆疊的一小段碼（prologue和epilogue），這一小段碼基本上做的是housekeeping工作，你沒(méi)看到也沒(méi)有關(guān)系（更好），并不影響你對(duì)程式邏輯的思考。C++不一樣，C++有太多和程式邏輯息息相關(guān)的動(dòng)作是編譯器為我們加上去的。換句話說(shuō)C++編譯器為我們「加碼」。如果不識(shí)清這一節(jié)，學(xué)習(xí)C++有如霧里看花，霧非霧，花非花。編譯器為我們的C++程式加了什麼碼呢？很多！物件誕生時(shí)ctor會(huì)被喚起，物件死亡時(shí)dtor會(huì)被喚起，這都是加碼的結(jié)果。ctor中設(shè)定vtpr和vtbl，這也是加碼的結(jié)果。new單一物件時(shí)會(huì)產(chǎn)生memoryblockcookie，new物件陣列時(shí)會(huì)產(chǎn)生一個(gè)內(nèi)部結(jié)構(gòu)記錄著objectsize和classctor...，這也都是布幕後的工作。可以說(shuō)，程式碼中看不到而卻必須完成的所有與程式邏輯有關(guān)的動(dòng)作，統(tǒng)統(tǒng)都是C++編譯器加碼後的結(jié)果。當(dāng)「繼承」發(fā)生，整個(gè)情況變得稍微復(fù)雜起來(lái)?！付嘀乩^承」又更復(fù)雜一些，「虛擬繼承」再更復(fù)雜一些。這些布幕後的主題，統(tǒng)可歸類為所謂的C++objectmodel（物件模型）。如果不知道這些底層機(jī)制，你就只能夠把"makedestructorsvirtualinbaseclasses"（<EffectiveC++>,item14）或"nevertreatarrayspolymorphically"（<MoreEffectiveC++>,item3）這類規(guī)則硬背下來(lái)，卻不明白它的道理。用一樣?xùn)|西，卻不明白它的道理，林語(yǔ)堂如是說(shuō)：『不高明』。只知道how，不知道why，侯捷如是說(shuō)：『不高明』?！窭щy度之二C++的第二個(gè)學(xué)習(xí)難度在於"paradigmshift"（思考模式的移轉(zhuǎn)）。別說(shuō)自己設(shè)計(jì)classes了，光使用別人的classes，就都是一種思考模式和行為模式的移轉(zhuǎn)。MFC（或OWL或VCL）programmer必然甚能夠領(lǐng)略并體會(huì)我的意思。使用所謂的applicationframework（一種大型的、凝聚性強(qiáng)的、有著物件導(dǎo)向公共基礎(chǔ)建設(shè)的classlibrary），你的碼和framework之間究竟是怎樣的關(guān)系呢？framework提供的一大堆可改寫的虛擬函式的意義與價(jià)值究竟在哪里呢？為什麼framework所設(shè)計(jì)的種種美好性質(zhì)以及各式各樣的演算法竟然可以施行於我們自己設(shè)計(jì)的classtypes身上呢？framework被設(shè)計(jì)時(shí)，并不知道我們的存在呀！這正是物件導(dǎo)向中的多型（polymorphism）的威力。稍早所說(shuō)的C++物件模型，偏屬程式設(shè)計(jì)的低層面；這里所說(shuō)的思考模式移轉(zhuǎn)，則是程式設(shè)計(jì)的高層面。能夠把新思維模式的威力發(fā)揮得最淋漓盡致的，當(dāng)推物件導(dǎo)向的polymorphism（多型）和generalization（泛型）。如果你沒(méi)有使用這兩項(xiàng)特性，等於入C++寶山而空手返?！穹锤矡挘h(huán)震蕩想像C++是一把用來(lái)解決程式問(wèn)題的刀，要它堅(jiān)軔，要它鋒利，就必須經(jīng)過(guò)多次的回火，在高熱和驟冷之間煉。初學(xué)C++語(yǔ)法（syntax）之後，你應(yīng)該盡快嘗試體驗(yàn)polymorphism（大致而言也就是虛擬函式的運(yùn)用）。等到對(duì)OOP的精神有了大局掌控的能力，但對(duì)C++的許多小細(xì)節(jié)不甚清楚，就是回到C++物件模型煉的時(shí)機(jī)。成長(zhǎng)，是在高階（polymorphism）和低階（objectmodel）之間反覆震蕩，才能夠震蕩到更高的位階，而不是平平庸庸於中階（C++syntax）的一灘死水。●不要沉淪於C++syntax100個(gè)人跟我說(shuō)他懂C++/OOP，只有10%不到可以讓我認(rèn)為他沒(méi)有胡吹大氣。太多的人，上嘛上不到polymorphism，下嘛又下不到objectmodel。就這樣不上不下地卡在C++語(yǔ)法層面。大一學(xué)了C++，到大四快畢業(yè)了，連virtualfunctions是怎麼回事都期期艾艾支支吾吾說(shuō)不出個(gè)道理。有時(shí)候我覺(jué)得，太苛責(zé)同學(xué)也於心不忍，因?yàn)橥瑢W(xué)們事實(shí)上處?kù)兑环N無(wú)知的狀態(tài)，既不知道C++/OOP該怎麼學(xué)，也不知道哪些書可以教他們那麼學(xué)。所以，苛責(zé)同學(xué)，不如責(zé)怪老師。眾所周知，大學(xué)教授泰半是動(dòng)口不動(dòng)手，普遍的心態(tài)是「論文第一，升等為要；程式語(yǔ)言？哎，末流！」?！改┝鳌拐n程通常由教授們輪流教，誰(shuí)倒楣誰(shuí)來(lái)教；於是就常常有「下學(xué)期要教C++語(yǔ)言了，這學(xué)期寒（暑）假趕快去要本書來(lái)惡補(bǔ)」的情況發(fā)生。偏偏程式語(yǔ)言這東西，只動(dòng)口不管用，一定要?jiǎng)邮?，而且要常?dòng)手。老師自己沒(méi)有摸到C++/OOP的精神，學(xué)生又能學(xué)到什麼？有些學(xué)校資訊系并不教特定的程式語(yǔ)言，老師們的態(tài)度是「語(yǔ)言是一種自己學(xué)就好了的東西嘛，拿到大學(xué)殿堂來(lái)，哎，不入流」！於是應(yīng)該好好為學(xué)生打下實(shí)際基礎(chǔ)的課程，卻天馬行空地騰云駕霧起來(lái)，大談抽象意念。飽讀經(jīng)書的老師們可能忽略了，一個(gè)完全沒(méi)有技術(shù)基礎(chǔ)的學(xué)子，要的不是形而上的道，而是形而下的器。我們是先能夠欣賞具象畫，還是先能夠欣賞抽象畫？我們不都是先對(duì)畢卡索的畫大罵「這是什麼東西」，直到自己的藝術(shù)涵養(yǎng)夠豐富了、人生閱練更飽滿了、能夠舉一隅以三隅反了、能夠接觸類旁通左右逢源了，才轉(zhuǎn)而能夠欣賞甚至進(jìn)入畢卡索的抽象意境嗎？老師們各有專長(zhǎng)，要老師們來(lái)教非彼專長(zhǎng)的大班課、基礎(chǔ)課，我又覺(jué)得似乎也太為難老師了。那麼，苛責(zé)老師，不如責(zé)怪學(xué)校當(dāng)局。如果學(xué)校當(dāng)局能夠聘請(qǐng)經(jīng)驗(yàn)老道又有教學(xué)熱誠(chéng)的工程師來(lái)教這類實(shí)務(wù)學(xué)科，不是三方皆大歡喜嗎？不要說(shuō)什麼制度僵化啦，難以突破啦，大學(xué)是高度自治區(qū)，禮聘幾位兼任老師，不全都是系上的權(quán)責(zé)范圍內(nèi)嗎？當(dāng)學(xué)子們?cè)谡n程上學(xué)不到他要的東西，就只好閉門自修。但是，循序性（sequential）語(yǔ)言尚有自修學(xué)會(huì)的可能，物件導(dǎo)向語(yǔ)言嘛，以大學(xué)生的程度來(lái)講，我認(rèn)為自修實(shí)在困難，只會(huì)修出個(gè)四不像、半瓶水。管不到學(xué)校！管不到教授！自求多福的情況下，希望看到這篇文章的你，知道C++/OOP該怎麼學(xué)?！癫灰撩造禖++semantics和C++objectmodel對(duì)於底層知識(shí)有濃厚興趣的朋友，下探到objectmodel領(lǐng)域，一定會(huì)非常開心地在objectsize、objectlayout、vptr/vtbl、以及許多布幕後的技術(shù)之間玩將起來(lái)。了解這些東西，當(dāng)然是好的，但是由於一探究竟得其奧秘的快感與成就感，使得一些朋友們?cè)谶@個(gè)層面里「玩」起來(lái)了，小地方玩得很精，玩得不亦樂(lè)乎，玩得忽略了C++/OO的最終目標(biāo)。最終目標(biāo)是polymorphism！我要說(shuō)，在C++syntax以及相對(duì)低階的C++semantics里，不要玩得太過(guò)火。過(guò)猶不及，會(huì)傷身的。C++經(jīng)典名書內(nèi)附的一些習(xí)題，在我看來(lái)頗有點(diǎn)玩得過(guò)火的味道。至於什麼百題精選、題庫(kù)大成，除了修練基本功之外，都滿無(wú)趣的東西。Programming應(yīng)該是一種天馬行空的想像力與創(chuàng)意的組合；如果你能夠自己想題目，譬如說(shuō)實(shí)作一個(gè)天體運(yùn)行的class體系、或是實(shí)作一個(gè)生物分類（界門綱目科屬種）體系，不是很有趣嗎？準(zhǔn)備資料的過(guò)程中，查查百科全書，你也因此查到了太陽(yáng)系九大行星的幾何資料，哈雷慧星的軌道周期，或是黑面琵鷺的「界門綱目科屬種」英文名稱，這難道不比鉆研於++++i或----i或*&*&p之類的頭腦體操題目有趣嗎？（看過(guò)不少這類好笑題目，沒(méi)一個(gè)記下來(lái)，只好胡亂寫幾個(gè)運(yùn)算式。諸位應(yīng)該知道我說(shuō)的那種頭腦體操題目）固然，在科學(xué)與工程的領(lǐng)域里頭，無(wú)技術(shù)無(wú)以為立，但別把自己弄得過(guò)於僵化，過(guò)於匠氣。僵化與匠氣是我們教育體系的最大沉疴。到了高專層次，敗象顯露無(wú)遺?！衩麜扑]如果沒(méi)有介紹幾本好書，我就是為德不卒。讓我再節(jié)錄<多型與虛擬>的二刷感言：<多型與虛擬>一版二刷感言（侯俊杰/松崗/1998/08）...C++相關(guān)書籍，如天上繁星，如過(guò)江之鯽。廣博如四庫(kù)全書者有之（如TheC++ProgrammingLanguage、C++Primer），深?yuàn)W宛如山重水復(fù)有之（如InsideTheC++ObjectModel），獨(dú)沽一味者有之（如C++ProgrammingStyle、MoreEffectiveC++），獨(dú)樹一幟者有之（如TheDesignandEvolutionofC++），另辟蹊徑者亦有之（如STLtutorialReferenceGuide）。...以下是我認(rèn)為你應(yīng)該要擁有的書籍。有趣的是，我才在自己班上做了一個(gè)調(diào)查（我教的是物件導(dǎo)向Windows程式設(shè)計(jì)，學(xué)生應(yīng)該要有良好的C++/OOP基礎(chǔ)），擁有以下1~5本書的人舉手。舉手人數(shù)都很少，而且老是那幾位（最高記錄是擁有四本）。這讓我感覺(jué)，強(qiáng)者恒強(qiáng)，弱者恒弱。悲夫！1.C++Primer(3/e),Lippman/A.W./1998（聽說(shuō)1999將有中譯本）2.TheC++ProgrammingLanguage(3/e),Bjarne/A.W./1997（聽說(shuō)1999將有中譯本）以上兩本書是C++經(jīng)典百科。就內(nèi)容水平而言，我認(rèn)為同為瑜亮。普遍的印象是，第一本較易接受，第二本澀味稍重。第二本書作者Bjarne是C++語(yǔ)言的創(chuàng)造者，所以有其權(quán)威性。我認(rèn)識(shí)的多位C++/OOP高手，都是兩書齊具。3.InsideTheC++ObjectModel,Lippman/A.W./1996（中譯本<深度探索C++物件模型>）全書講解C++objectmodel，上窮碧落下黃泉。內(nèi)容很好，層次也高，可惜原文書大大小小的錯(cuò)誤繁如晨星，閱讀時(shí)需小心。4.EffectiveC++,Meyers/A.W./1992（印象似有中譯本，名稱忘了，誰(shuí)可補(bǔ)充說(shuō)明？）5.MoreEffectiveC++,Meyers/A.W./1996（有中譯本嗎？我不知道，誰(shuí)可補(bǔ)充說(shuō)明？）同一作者的這兩本書，專講C++programming的重要觀念，使你的程式更穩(wěn)健更有效率。書中許多觀念涉及C++objectmodel，與(3)書混合看，如魚得水。6.PolymorphisminC++<多型與虛擬>侯俊杰/松崗/1998（沒(méi)有中譯本--它本身就是中文書）在語(yǔ)法粗具的基礎(chǔ)上，直接把讀者導(dǎo)引到最核心最重要的思想，并且在建立這個(gè)思想的過(guò)程中，提供足夠的必要基礎(chǔ)。我只列出一本中文書，是因?yàn)檫@方面的中文書我看得少，英文書看得多?！缚钟羞z珠之憾」這類「八方得體」的話，還是說(shuō)一下好了:)。注意，這些都只是強(qiáng)本固元用來(lái)扎基礎(chǔ)的書籍而已，要觀摩大型程式經(jīng)驗(yàn)，還有諸如LargeScaleC++SoftwareDesign（JohnLakos/A.W./1996）可以閱讀。OO的世界，不止OOP，還有OOA/OOD，那又是一缸子的學(xué)問(wèn)和一缸子的書。

C++語(yǔ)言程序設(shè)計(jì)試題

2001年1月

說(shuō)明：在本試卷中規(guī)定整型(int)數(shù)據(jù)占用4個(gè)字節(jié)的存儲(chǔ)單元。

一、選擇題(每小題1分，共6分)

1．由C++目標(biāo)文件連接而成的可執(zhí)行文件的缺省擴(kuò)展名為

。

A．

cpp

B.

exe

C．

obj

D.

lik2．在下面的一維數(shù)組定義中，哪一個(gè)有語(yǔ)法錯(cuò)誤。

A.

int

a[]={1,2,3}

B.

int

a[10]={0}

C.

int

a[]

D.

int

a[5]3．在下面的函數(shù)聲明中，存在著語(yǔ)法錯(cuò)誤的是

。

A.

void

BC(int

a,int)

B.

void

BD(int,int)

C.

void

BE(int,int=5)

D.

int

BF(int

x;int

y)4.假定AB為一個(gè)類，則該類的拷貝構(gòu)造函數(shù)的聲明語(yǔ)句為

。

A．

AB&(AB

x)

B.

AB(AB

x)

C．

AB(AB

&)

D.

AB(AB*x)5．對(duì)于結(jié)構(gòu)中定義的成員，其隱含訪問(wèn)權(quán)限為

。

A．

public

B.

protected

C．

private

D.

static6．當(dāng)使用fstream流類定義一個(gè)流對(duì)象并打開一個(gè)磁盤文件時(shí)，文件的隱含打開方式為

。

A．

ios::in

B.

ios::out

C．

ios::int|ios::out

D.

沒(méi)有

二、填空題(每小題2分，共24分)1．執(zhí)行“cout

<<43<<’-‘<<18<<’=’<<43-18<<endl;”語(yǔ)句后得到的輸出結(jié)果為

。2．已知’A’～’Z’的ASCII碼為65～90，當(dāng)執(zhí)行“char

ch=14*5+2;cout

<<ch<<endl;”語(yǔ)句序列后，得到