計(jì)算機(jī)算法基礎(chǔ)1

計(jì)算機(jī)導(dǎo)法基砒

（課件V0.1）

王多強(qiáng)

華中科技大學(xué)計(jì)算機(jī)學(xué)院

2011-7-7

序

專業(yè)基礎(chǔ)課程：

數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)語言

操作系統(tǒng)、編譯

如何編寫計(jì)算機(jī)程序：

?數(shù)據(jù)結(jié)構(gòu)+算法=程序

?算法：計(jì)算機(jī)軟件的“靈魂”

算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心

2011-7-7

教材：

計(jì)算機(jī)算法基礎(chǔ)余祥宣等編著華中科技大學(xué)出版社

參考書：

算法設(shè)計(jì)與分析王曉東編著清華大學(xué)出版社

計(jì)算機(jī)算法導(dǎo)引——設(shè)計(jì)與分析盧開澄編著清華大

學(xué)出版社

IntroductionToAlgorithm高教出版社，MITPress

學(xué)時(shí)：32+8學(xué)時(shí)

2011-7-7

章節(jié)安排

?第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)

?第二章分治法

?第三章貪心方法

?第四章動態(tài)規(guī)劃

?第五章檢索與周游

?第六章回溯法?

?第七章分枝邛艮界?

?第八章NP-問題9

2011-7-7

第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)::

1.1算法的定義及特性

1.什么是算法？

★算法如數(shù)字、計(jì)算一樣，是一個(gè)基本概念。

★算法是解一確定類問題的任意一種特殊的方法。

★在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問題

的精確、有效方法的代名詞；

算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型

問題的一系列運(yùn)算。

2011-7-7

2.算法的五個(gè)重要特性

確定性、能行性、輸入、輸出、有窮性

1）確定性：算法的每種運(yùn)算必須要有確切的定

義，不能有二義性。

例：不符合確定性的運(yùn)算

?5/0

?將6或7與x相加I

?未賦值變量參與運(yùn)算

2011-7-7

2）能行性

算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，

原理上每種運(yùn)算都能由人用紙和筆在“有限”的

時(shí)間內(nèi)完成。

例：整數(shù)的算術(shù)運(yùn)算是“能行”的

實(shí)數(shù)的算術(shù)運(yùn)算是“不能行”的

2011-7-7

3）輸入

每個(gè)算法有。個(gè)或多個(gè)輸入。這些輸入是在算法開始之前

給出的量，取自于特定的對象集合——定義域（或值域）

4）輸出

一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種

特定關(guān)系的量。

2011-7-7

5）有窮性

一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。

計(jì)算過程：只滿足確定性、能行性、輸入、輸出四個(gè)特

性的一組規(guī)則

?算法和計(jì)算過程的區(qū)別：

＞計(jì)算過程：操作系統(tǒng)（不終止的運(yùn)行過程）

＞算法是“可以終止的計(jì)算過程”

?算法的時(shí)效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投

入到計(jì)算機(jī)上運(yùn)行

2011-7-7

4.我們的主要任務(wù)???:

算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容：：

1）設(shè)計(jì)算法：創(chuàng)造性的活動

2）表示算法：思想的表示形式，SPARKS語言

3）確認(rèn)算法：證明算法對所有可能的合法輸入都能得出正確的答案。

算法證明：證明算法的正確性，與語言無關(guān)

程序證明：證明程序的正確性

4）分析算法：對算法的時(shí)、空特性做定量分析，以了解算法的好壞

5）測試程序：

調(diào)試：“調(diào)試只能指出有錯(cuò)誤，而不能指出它們不存在錯(cuò)誤”

作時(shí)空分布圖：驗(yàn)證分析結(jié)論，優(yōu)化算法設(shè)計(jì)

本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算

法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基

礎(chǔ)

2011-7-7

5.課程關(guān)系

數(shù)據(jù)結(jié)構(gòu)

程序設(shè)計(jì)語言：結(jié)構(gòu)化設(shè)計(jì)

數(shù)學(xué)基礎(chǔ)

非數(shù)值計(jì)算領(lǐng)域的基本知識

2011-7-7

1.2分析算法

1.分析算法的目的

在于：通過對算法的分析，在把算法變成程序?qū)嶋H運(yùn)行前,

就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法的好壞，從而運(yùn)行好的算

法，改進(jìn)差的算法，避免無益的人力和物力浪費(fèi)。

算法分析是計(jì)算機(jī)領(lǐng)域的“古老”而“前沿”的課題。

2011-7-7

2.重要的假設(shè)和約定

1）計(jì)算機(jī)模型的假設(shè)

?計(jì)算機(jī)形式理論模型：Turing機(jī)模型

?通用計(jì)算機(jī)模型：

>順序計(jì)算機(jī)

>有足夠的“內(nèi)存”

>能在固定的時(shí)間內(nèi)存取數(shù)據(jù)單元

2011-7-7

2）計(jì)算的約定：：：!

算法的執(zhí)行時(shí)間立fJt??

其中，才是算法中用到的某種運(yùn)算i的次數(shù)——稱為該運(yùn)算的“頻率計(jì)數(shù)”

t是該運(yùn)算執(zhí)行一次所用的時(shí)間——與程序語言和硬件有關(guān)

確定：使用何種運(yùn)算及其執(zhí)行時(shí)間。

?從運(yùn)算的“時(shí)間特性”上將運(yùn)算的分類：

＞時(shí)間囿界于常數(shù)的運(yùn)算：

.基本算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除

?字符運(yùn)算、賦值運(yùn)算、過程調(diào)用等

特點(diǎn)：盡管每種運(yùn)算的執(zhí)行時(shí)間不同，但一般只花一個(gè)

固定量的時(shí)間（單位時(shí)間）就可完成。

2011-7-7

2）計(jì)算的約定（續(xù)）：

A其他運(yùn)算：

?字符串操作：與字符串中字符的數(shù)量成正比

?記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān)

特點(diǎn)：運(yùn)算時(shí)間無定量。

如何分析非時(shí)間囿界于常數(shù)的運(yùn)算：分解成若干時(shí)間囿

界于常數(shù)的運(yùn)算。

如:tstring=Length（String）*tchar

2011-7-7

3）工作數(shù)據(jù)集的選擇

?編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)

配置。然后使用這些數(shù)據(jù)配置運(yùn)行算法，以了解算法的性

能。

編制測試數(shù)據(jù)是程序測試與算法分析中的關(guān)鍵技術(shù)之一。

?作為算法分析的數(shù)據(jù)集：反映算法的典型特征

?作為程序正確性及性能測試的數(shù)據(jù)集：測試程序的對錯(cuò)，反映對性

能指標(biāo)產(chǎn)生影響的方面，如邊界值

2011-7-7

3?如何進(jìn)行算法分析？?

對算法進(jìn)行全面分析，可分兩個(gè)階段進(jìn)行：

?事前分析：求算法的一個(gè)時(shí)間/空間限界函數(shù)，即通過對算

法的“理論”分析，得出關(guān)于算法時(shí)間和空間

特性

的特征函數(shù)（0、Q）——與計(jì)算機(jī)物理軟硬

件沒有直接關(guān)系。

?事后測試：將算法編制成程序后實(shí)際放到計(jì)算機(jī)上運(yùn)行，

收集其執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，進(jìn)行

分析判斷一一直接與物理實(shí)現(xiàn)有關(guān)。

2011-7-7

1）事前分析

?目的：試圖得出關(guān)于算法特性的一種形式描

述，以“理論上”衡量算法的“好壞”。

?如何給出反映算法特性的描述？

統(tǒng)計(jì)算法中各種運(yùn)算的執(zhí)行情況，包括：

>引用了哪些運(yùn)算

>每種運(yùn)算被執(zhí)行的次數(shù)

>該種運(yùn)算執(zhí)行一次所花費(fèi)的時(shí)間等。

算法的執(zhí)行時(shí)間二Zfjtj

2011-7-7

?頻率計(jì)數(shù)

頻率計(jì)數(shù)：算法中語句或運(yùn)算的執(zhí)行次數(shù)。

例:

x<—x+yfori<—1tondofori<—1tondo

x<—x+yforj<—1tondo

repeatx—x+y

repeat

repeat

(a)(b)⑹

分析:

(/a\

\7?X—x+y執(zhí)行了1次

(zb!\

\/?x-x+y執(zhí)行了n次

(/c)\

\/?x—x+y執(zhí)行了《次

2011-7-7

一條語句在整個(gè)程序運(yùn)行時(shí)實(shí)際執(zhí)行時(shí)間二

頻率計(jì)數(shù)*每執(zhí)行一次該語句所需的時(shí)間

?在事前分析中，只限于確定與所使用的機(jī)器及其他環(huán)境因

素?zé)o關(guān)的頻率計(jì)數(shù)，依此建立一種理論上分析模型。

2011-7-7

?數(shù)量級

—衡量頻率計(jì)數(shù)的“大小”的一種測度

>語句的數(shù)量級：語句的執(zhí)行頻率

例：1,n,n2

a算法的數(shù)量級：算法所包含的所有語句的執(zhí)行頻率之和。

數(shù)量級反映了算法復(fù)雜度的最本質(zhì)的特征。

例：假如求解同一個(gè)問題的三個(gè)算法分別具有n,n2,2數(shù)量級。

若n=10,則可能的執(zhí)行時(shí)間將分別是10,100,1000個(gè)單

位時(shí)間——與環(huán)境因素?zé)o關(guān)。

2011-7-7

?頻率計(jì)數(shù)的函數(shù)表示

就計(jì)算時(shí)間而言，事前分析階段求得算法在頻率計(jì)成

上的函數(shù)表示——與規(guī)模n有關(guān)的函數(shù)形式，記為：g(n)

不同的算法，g(n)的具體形式是不同的，如

logn,nlogn,?等

g(n)的一般形式：關(guān)于n的簡單函數(shù)式

“實(shí)際”能夠得到的：

1)函數(shù)式的最高次項(xiàng)

2)最高次項(xiàng)與函數(shù)整體的關(guān)系。

?空間特性分析(與時(shí)間特性的分析類似，略)

2011-7-7

2）事后測試

?H的：運(yùn)行程序，統(tǒng)計(jì)執(zhí)行實(shí)際耗費(fèi)的準(zhǔn)確的時(shí)

間與空間，與事前分析的結(jié)論進(jìn)行比較，驗(yàn)證先

前的分析結(jié)論——包括正確性、執(zhí)行性能等，比

較、優(yōu)化所設(shè)計(jì)的算法。

?分析手段：作時(shí)、空性能分布圖

2011-7-7

4,計(jì)算時(shí)間的漸近表示?：

記：算法的實(shí)際計(jì)算時(shí)間為f(n),計(jì)算時(shí)間的限界函數(shù)為g(n)::'

其中，

?n是輸入或輸出規(guī)模的某種測度。

?f(n)表示算法的“實(shí)際”執(zhí)行時(shí)間一與機(jī)器及語言有關(guān)。

?g(n)是事前分析的結(jié)果---一個(gè)形式簡單的函數(shù)，如nm,logn,

2n,n!等。是與頻率計(jì)數(shù)有關(guān)、而與機(jī)器及語言無

關(guān)的函數(shù)。

以下給出算法執(zhí)行時(shí)間：上界(0)、下界(。)、“平均”

()有J定義。

2011-7-7

1)上界函數(shù)

定義1如果存在兩個(gè)正常數(shù)c和n。，對于所有的nN國,有

If(n)|<c|g(n)

則記作f(n)=O(g(n))

含義：

?如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時(shí)，所用的

時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的

一個(gè)上界函數(shù)。f(n)的數(shù)量級就是g(n)。

?試圖求出最小的g(n),使得f(n)=0(g(n))o

2011-7-7

多項(xiàng)式定理：

定理1若A(n)=*心+…+即口+@0是一個(gè)m次多項(xiàng)式，則有

A(n)=O(nm)

即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階

W同階。

證明：取國=1,當(dāng)nNrio時(shí)，有

m

|A(n)|<|am|n+..,+laJn+laol

+mm

^(|aml|am-il/n+...+|a0|/n)n

m

=(|am|+|am,1|+...+|a0|)n

令c二|am|+|am,1|+...+|a0|

則,定理得證。

2011-7-7

計(jì)算時(shí)間的數(shù)量級的大小對算法的有效性有決定性的影響

??

例：假設(shè)解決同一個(gè)問題的兩個(gè)算法，它們都有n個(gè)輸入，

計(jì)算時(shí)間的數(shù)量級分別是M和nlogn。貝U,

n=1024：分別需要1048576和10240次運(yùn)算。

n=2048：分別需要4194304和22528次運(yùn)算。

分析：

*同等規(guī)模下的計(jì)算量比較：

☆規(guī)模增大情況下的比較：在n加倍的情況下，一個(gè)0(小)的

算法計(jì)算時(shí)間增長4倍，而一個(gè)0(nlogn)算法則只用兩倍多一點(diǎn)的

時(shí)間即可完成。

2011-7-7

多項(xiàng)式時(shí)間算法和指數(shù)時(shí)間算法

>多項(xiàng)式時(shí)間算法：可用多項(xiàng)式(函數(shù))對其計(jì)算時(shí)間限界

的算法。

常見的多項(xiàng)式限界函數(shù)有：

0(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)

>指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法

常見的指數(shù)時(shí)間限界函數(shù)：

O⑵)<O(n!)<O(nn)

說明：當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)

間上非常懸殊。

2011-7-7

典型的計(jì)算時(shí)間函數(shù)曲線

圖1.1一般計(jì)算時(shí)間函數(shù)的曲線

2011-7-7

?一般認(rèn)識

＞當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行

具有比O(nlogn)復(fù)雜度還高的算法是比較困難的。

＞指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。

＞要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑

是降低算法的計(jì)算復(fù)雜度，而不是(僅僅依靠)提高計(jì)算

機(jī)的速度。

2011-7-7

計(jì)算時(shí)間函數(shù)值比較

表LI計(jì)算時(shí)間困數(shù)值

lognnnlognn2n32°

0101..'-12

122484

248166416

382464512256

41664256409665536

532160102432768(4294967296).

2011-7-7

2)下界函數(shù)

定義1.2如果存在兩個(gè)正常數(shù)c和n0,對于所有的nNn0,

If(n)2c|g(n)

則記作f(n)。(g(n))

含義:

?如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時(shí)，所用的

時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)

的一個(gè)下界函數(shù)。

?試圖求出“最大”的g(n),使得f(n)=Q(g(n))o

2011-7-7

???

3)“平均情況”限界函數(shù)

???

???

定義1.3如果存在正常數(shù)”，和n0,對于所有的nNn0,有

ct|g(n)|<|f(n)|Cc2|g(n)

則記作

f(n)=?(g5))

含義：

?算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言

是相同的?？煽醋鳎?/p>

既有f(n)=Q(g(n)),又有f(n)=O(g(n))

2011-7-7

4)限界函數(shù)的性質(zhì)

1)若/=o(g)且g=o=),則/=。(%)。即0具有傳

遞性。(Q、。同)

2)/=O(g)當(dāng)且僅當(dāng)g=Q(7)

3)若/=3(g)則g=0(/)o即，Q定乂了一*個(gè)等

價(jià)關(guān)系(等價(jià)類)

證明：

從定義出發(fā)。證明過程略。

2011-7-7

5.常用的整數(shù)求和公式

在算法分析中，在統(tǒng)計(jì)語句的頻率時(shí)，求和公

式的一般形式為：

如：

=€）（/+1）

\<i<n

2011-7-7

1.3關(guān)于SPARKS語言

?本書為描述算法選用的一種計(jì)算機(jī)語言

?類PASCAL語言

?結(jié)構(gòu)化設(shè)計(jì)

2011-7-7

1.基本語法成分2)變量聲明

類型說明符變量;

1）數(shù)據(jù)類型

integeri,j;

整型integer

booleanb;

實(shí)型float

charc

布爾型boolean

3)數(shù)組

字符型char

任意整數(shù)下標(biāo)

integerA(1:5,7:20)

integerB(5,7:20)

2011-7-7

4）賦值運(yùn)算

（變量）-（表達(dá)式）

x—2+x;

5）邏輯運(yùn)算：andornot

6）關(guān)系運(yùn)算：<<=#>>

2011-7-7

7）控制結(jié)構(gòu):

順序：（略）

分支：循環(huán)：

?ifconditionthenS1?whileconddo

elseS2S

endif

repeat

?case

?loop

:cond1:S1;

:cond2:S2;S

untilcondrepeat

:condn:Sn?forvble<—starttofinishby

:else:Sn+1incrementdo

endcaseS

repeat

2011-7-7

8）函數(shù)的定義與調(diào)用

過程定義

procedureNAME（（參數(shù)表））

（說明部分）

S

endNAME

過程的調(diào)用：CALL過程名

函數(shù)定義

類型名procedureNAME（（參數(shù)表））

（說明部分）

S

return（表達(dá)式）

endNAME

函數(shù)的引川：X-function（參數(shù)）；

2011-7-7

9）變量的分類

a）根據(jù)數(shù)據(jù)類型分類

整型、實(shí)型、字符型等

b）根據(jù)作用域分類：

全程變量、局部變量、形式參數(shù)

c）根據(jù)是否帶入、帶出數(shù)據(jù)值/結(jié)果分類：

in型變量

out型變量

inout型變量

邊界效應(yīng)：改變了參變量或全程變量的值

函數(shù)：通過函數(shù)值返回輸出結(jié)果，沒有邊界效應(yīng)

純過程：沒有函數(shù)值返回，只通過邊界效應(yīng)帶出輸出結(jié)果

2011-7-7

10）特殊語句

a）exit

退出當(dāng)前一層的循環(huán)

b）return

退出過程

return（表達(dá)式）：函數(shù)返回結(jié)果

c）goto無條件轉(zhuǎn)向語句

gotolabel

11）遞歸

a）直接遞歸：過程中包含對自身的調(diào)用

b）間接遞歸：間接調(diào)用自身

12）輸入輸出

read>print

13）注釋

〃注釋//

2011-7-7

1.4基本數(shù)據(jù)結(jié)構(gòu)

1.棧和隊(duì)列

?線性表：n個(gè)元素的有序表

?棧和隊(duì)列：特殊的線性表

?利用動態(tài)數(shù)據(jù)結(jié)構(gòu)—鏈表實(shí)現(xiàn)?；蜿?duì)列

?利用靜態(tài)數(shù)據(jù)結(jié)構(gòu)—數(shù)組實(shí)現(xiàn)棧或隊(duì)列

?基于以上兩種表示形式的棧和隊(duì)列上的基本運(yùn)算

2011-7-7

圖L10含有元素工」2，八」且容量為n的環(huán)形隊(duì)列

2.樹

定義1.4樹(tree)是一個(gè)或多個(gè)結(jié)點(diǎn)的有限集合，它使K：

?有一個(gè)指定為根(root)的結(jié)點(diǎn)

?剩余結(jié)點(diǎn)被劃分成mNO個(gè)不相交的集合：

這些集合的每一個(gè)又都是一棵樹，并稱L，…，*為根的子樹。

2011-7-7

關(guān)于樹的重要概念

?結(jié)點(diǎn)的度（degree）：一個(gè)結(jié)點(diǎn)的子樹數(shù)

?樹的度：樹中結(jié)點(diǎn)度的最大值

?結(jié)點(diǎn)的級（level）（又叫層）：設(shè)根是1級，若某結(jié)點(diǎn)在p級,

則它的兒子在P+1級

?樹的高度（或深度）：樹中結(jié)點(diǎn)的最大級數(shù)

?葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)

?內(nèi)結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)

?森林：m2。個(gè)不相交樹的集合。

2011-7-7

3二元樹：：

定義1.5二元樹(binarytree)是結(jié)點(diǎn)的有限集合，它或者為

空，或者由一個(gè)根和兩棵稱為左子樹和右子樹的不相交二元樹所

組成。

?二元樹與度為2的樹的區(qū)別

?二元樹性質(zhì)：

引理1.1一棵二元樹第i級的最大結(jié)點(diǎn)數(shù)是2"。深度為k的二元

樹的最大結(jié)點(diǎn)數(shù)為2匕1,k>0。

2011-7-7

圖1.14兩棵特殊的二元樹

2011-7-7

?特殊形態(tài)的二元樹

①滿二元樹：深度為k且有2匕1個(gè)結(jié)點(diǎn)的二元樹

2011-7-7

②完全二元樹：一棵有n個(gè)結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的

結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹中編號為1到

n的結(jié)點(diǎn)時(shí)，稱該二元樹是完全的。

＞完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級上。

＞完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個(gè)一維數(shù)組中（性質(zhì)見

引理1.2）。

2011-7-7

③堆：堆是一棵完全二元樹，它的每個(gè)結(jié)點(diǎn)的值至少和

該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大

（max-堆）（或小，min一堆）。

④二分檢索樹：二分檢索樹T是一棵二元樹，它或者為空,

或者每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且

有：

?T的左子樹的所有元素比根結(jié)點(diǎn)中的元素?。?/p>

?T的右子樹的所有元素比根結(jié)點(diǎn)中的元素大；

?T的左子樹和右子樹也是二分檢索樹。

注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異

2011-7-7

3.圖

圖G由稱之為結(jié)點(diǎn)V和邊E的兩個(gè)集合組成，記為

G=(V,E)

其中，V是一個(gè)有限非空的結(jié)點(diǎn)集合；E是結(jié)點(diǎn)對偶的

集合，E的每一對偶表示G的一條邊。

2011-7-7

有關(guān)圖的的重要概念

?無向圖：邊表示為（i,j）

?有向圖：邊表示為〈i,j〉

?成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖）

?鄰接

?結(jié)點(diǎn)的度（出度/入度）

?路徑：由結(jié)點(diǎn)v到v的一條路（path）是結(jié)點(diǎn)

Vp,4,vj2,...,vim,Vq的一個(gè)序列，它使得

（Vp，Mi），（VM,Vj2），…，（Vjm,vq）

是E（G）的邊。

?路的長度：組成路的邊數(shù)。

2011-7-7

?簡單路徑：除了第一和最后一個(gè)結(jié)點(diǎn)可以相同以外，其它?

所有結(jié)點(diǎn)都不同。：

?環(huán)：第一個(gè)和最后一個(gè)結(jié)點(diǎn)相同的簡單路。

?連通圖：在無向圖中，如果每對結(jié)點(diǎn)之間都存在一條路徑，則

稱該圖是連通的。

?子圖：是由G的結(jié)點(diǎn)集V的子集（記為VB）和邊集E中連接VB

中結(jié)點(diǎn)的邊的子集所組成的圖。

?連通分圖：一個(gè)圖的最大連通子圖。

?有向圖的強(qiáng)連通性：在有向圖中，如果對于每一對結(jié)點(diǎn)i和j,

既存在一條從i到j(luò)的路，又存在一條從j

到i的路，則稱該有向圖是強(qiáng)連通的。

2011-7-7

???

圖的表示方法

(a)

圖1.26兩個(gè)實(shí)例圖

?鄰接矩陣鄰接表

X1.4BU27的鄰接矩陣

1234512345

⑴「01110'■01110-

(2)0010010100

(3)0000011000

(4)0000110001

(b)

⑸L00000.-00010-

圖1?27圖1.26的鄰接表

2011-7-7

1.5遞歸和消去遞歸

1.遞歸

?遞歸是一種強(qiáng)有力的設(shè)計(jì)方法

?遞歸的效率問題

2011-7-7

例1.3斐波那契(Fibonacci)序列：

F。=F1二1

F產(chǎn)Fg+F'2(>1)

算法1.7求斐波那契數(shù)

procedureF(n)

〃返回第n個(gè)斐波那契數(shù)〃

integern

ifn<=1thenreturn(1)

elsereturn(F(n-1)+F(n-2))

endif

endF

?算法效率：對F(n-1)、F(n-2)存在大量的重復(fù)計(jì)算

?改進(jìn)：保存中間結(jié)果

2011-7-7

例1.4歐幾里得算法

已知兩個(gè)非負(fù)整數(shù)a和b,且a〉bNO,求這兩個(gè)數(shù)的

最大公因數(shù)。

輾轉(zhuǎn)相除法：若b=0,則a和b的最大公因數(shù)等于a；若b>0,

則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。

算法1.8求最大公因數(shù)

procedureGCD(a,b)//約定a>b//

ifb=0thenreturn(a)

elsereturn(GCD(b,amodb))

endif

endGDC

例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;

2011-7-7

例1.5用遞歸策略設(shè)計(jì)的檢索算法

已知元素x和元素表A(1：n),判斷x是否等于A中

某元素的值。

算法1.9在A(1：n)中檢索x

procedureSEARCH(i)

〃如果在A(1：n)〃中有一元素A(k二x,則將其第一次出現(xiàn)的下標(biāo)k返回,

否則返回0〃

globaln,x,A(1:n)

case

:i>n:return(O)

:A(i)=x;return(i)

:else:return(SEARCH(i+1))

endcase

endSEARCH

2011-7-7

2.消去遞歸：：

??

直接遞歸的消去規(guī)則：

基本思路：將遞歸調(diào)用的地方用等價(jià)的非遞歸代碼來代替，并

對return語句做適當(dāng)處理。

13條規(guī)則：處理直接遞歸調(diào)用和return語句，將之轉(zhuǎn)換成等價(jià)

的迭代代碼。

?初始化

⑴在過程的開始部分，插入說明為棧的代碼并將其初始化為

空。在一般情況下，這個(gè)棧用來存放參數(shù)、局部變量和函數(shù)的值、

每次遞歸調(diào)用的返回地址。

⑵將標(biāo)號L附于第一條可執(zhí)行語句。然后對于每一處遞歸調(diào)

用都用一組執(zhí)行下列規(guī)則的指令來代替。

2011-7-7

?處理遞歸調(diào)用語句

⑶將所有參數(shù)和局部變量的值存入棧。

棧頂指針可作為一個(gè)全程變量來看待。

(4)建立第i個(gè)新標(biāo)號j,并將i存入棧。這個(gè)標(biāo)號的i值將用來

計(jì)算返回地址。

此標(biāo)號放在規(guī)則⑺所描述的程序段中。

⑸計(jì)算這次調(diào)用的各實(shí)在參數(shù)(可能是表達(dá)式)的值，并把這

些值賦給相應(yīng)的形式參數(shù)。

(6)插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分：

gotoI

2011-7-7

?對退出一層遞歸調(diào)用后的處理

⑺如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用

的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂

取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄,

并將⑷中建立的標(biāo)號附于這條語句上。

如果此過程不是函數(shù)，則將⑷中建立的標(biāo)號附于⑹所產(chǎn)生的

轉(zhuǎn)移語句后面的那條語句。

以上步驟消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return

語句進(jìn)行處理。

（純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）

2011-7-7

?對每個(gè)有return語句的地方，執(zhí)行下述規(guī)則：

(8)如果棧為空，則執(zhí)行正常返回。

⑼否則，將所有輸出參數(shù)(帶有返回值的出口參數(shù)，out/

inout型)的當(dāng)前值賦給棧頂上的那些對應(yīng)的變量。