1、2020/7/28,計(jì)算機(jī)算法基礎(chǔ),華中科技大學(xué)計(jì)算機(jī)學(xué)院 韓建軍 ,2020/7/28,序,專業(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)用的核心,2020/7/28,教材： 計(jì)算機(jī)算法基礎(chǔ) 余祥宣等編著 華中科技大學(xué)出版社 參考書： 算法設(shè)計(jì)與分析 王曉東編著 清華大學(xué)出版社 計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析 盧開澄編著 清華大學(xué)出版社 Introduction To Algorithm 高教出版社，MIT Press 學(xué)時：36+4學(xué)時,2020/7/28,章節(jié)安排,第一章 導(dǎo)引與基本數(shù)

2、據(jù)結(jié)構(gòu) 第二章 分治法 第三章 貪心方法 第四章 動態(tài)規(guī)劃 第五章 檢索與周游 第六章 回溯法 第七章 分枝-限界 第八章 NP-問題?,2020/7/28,第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu),1.1 算法的定義及特性 1. 什么是算法？ 算法如數(shù)字、計(jì)算一樣，是一個基本概念。 算法是解一確定類問題的任意一種特殊的方法。 在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問題的精確、有效方法的代名詞； 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型 問題的一系列運(yùn)算。,2020/7/28,2. 算法的五個重要特性 確定性、能行性、輸入、輸出、有窮性,1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例

3、：不符合確定性的運(yùn)算 5/0 將6或7與x相加 未賦值變量參與運(yùn)算,2020/7/28,2）能行性 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在“有限”的時間內(nèi)完成。 例：整數(shù)的算術(shù)運(yùn)算是“能行”的 實(shí)數(shù)的算術(shù)運(yùn)算是“不能行”的,2020/7/28,3）輸入 每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合定義域（或值域）,4）輸出 一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關(guān)系的量。,2020/7/28,5）有窮性 一個算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。 計(jì)算過程：只滿足確定性、能行性、輸入、輸出四個特性的一組規(guī)則。 算

4、法和計(jì)算過程的區(qū)別： 計(jì)算過程：操作系統(tǒng)(不終止的運(yùn)行過程) 算法是“可以終止的計(jì)算過程” 算法的時效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投 入到計(jì)算機(jī)上運(yùn)行,2020/7/28,4. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個方面的內(nèi)容： 1）設(shè)計(jì)算法：創(chuàng)造性的活動 2）表示算法：思想的表示形式，SPARKS語言 3）確認(rèn)算法：證明算法對所有可能的合法輸入都能得出正確的答案。 算法證明：證明算法的正確性，與語言無關(guān) 程序證明：證明程序的正確性 4）分析算法：對算法的時、空特性做定量分析，以了解算法的好壞 5）測試程序： 調(diào)試：“調(diào)試只能指出有錯誤，而不能指出它們不存在錯誤” 作時空分布圖：驗(yàn)證分析結(jié)論

5、，優(yōu)化算法設(shè)計(jì) 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ),2020/7/28,5. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)語言：結(jié)構(gòu)化設(shè)計(jì) 數(shù)學(xué)基礎(chǔ) 非數(shù)值計(jì)算領(lǐng)域的基本知識,2020/7/28,1.2 分析算法,1. 分析算法的目的 在于：通過對算法的分析，在把算法變成程序?qū)嶋H運(yùn)行前，就知道為完成一項(xiàng)任務(wù)所設(shè)計(jì)的算法的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無益的人力和物力浪費(fèi)。 算法分析是計(jì)算機(jī)領(lǐng)域的古老而前沿的課題。,2020/7/28,2. 重要的假設(shè)和約定 1）計(jì)算機(jī)模型的假設(shè) 計(jì)算機(jī)形式理論模型： Turing機(jī)

6、模型 通用計(jì)算機(jī)模型： 順序計(jì)算機(jī) 有足夠的“內(nèi)存” 能在固定的時間內(nèi)存取數(shù)據(jù)單元,2020/7/28,2）計(jì)算的約定 算法的執(zhí)行時間=fi*ti 其中，fi是算法中用到的某種運(yùn)算i的次數(shù)稱為該運(yùn)算的“頻率計(jì)數(shù)” ti是該運(yùn)算執(zhí)行一次所用的時間 與程序語言和硬件有關(guān) 確定：使用何種運(yùn)算及其執(zhí)行時間。 從運(yùn)算的“時間特性”上將運(yùn)算的分類： 時間囿界于常數(shù)的運(yùn)算： 基本算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除 字符運(yùn)算、賦值運(yùn)算、過程調(diào)用等 特點(diǎn)：盡管每種運(yùn)算的執(zhí)行時間不同，但一般只花一個 固定量的時間（單位時間）就可完成。,2020/7/28,2）計(jì)算的約定（續(xù)）,其他運(yùn)算： 字符串操作：與字符

7、串中字符的數(shù)量成正比 記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān) 特點(diǎn)：運(yùn)算時間無定量。 如何分析非時間囿界于常數(shù)的運(yùn)算：分解成若干時間囿界于常數(shù)的運(yùn)算。 如：tstring = Length（String）* tchar,2020/7/28,3）工作數(shù)據(jù)集的選擇 編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運(yùn)行算法，以了解算法的性能。 編制測試數(shù)據(jù)是程序測試與算法分析中的關(guān)鍵技術(shù)之一。 作為算法分析的數(shù)據(jù)集：反映算法的典型特征 作為程序正確性及性能測試的數(shù)據(jù)集：測試程序的對錯，反映對性能指標(biāo)產(chǎn)生影響的方面,如邊界值,2020/7/28,3. 如何進(jìn)行算法分析？

8、對算法進(jìn)行全面分析，可分兩個階段進(jìn)行： 事前分析：就算法本身，通過對其執(zhí)行性能的“理論”分析， 得出關(guān)于算法特性時間和空間的一個特征 函數(shù)（、）與計(jì)算機(jī)物理軟硬件沒有 直接關(guān)系。 事后測試：將算法編制成程序后實(shí)際放到計(jì)算機(jī)上運(yùn)行， 收集其執(zhí)行時間和空間占用等統(tǒng)計(jì)資料，進(jìn)行 分析判斷直接與物理實(shí)現(xiàn)有關(guān)。,2020/7/28,1）事前分析 目的：試圖得出關(guān)于算法特性的一種形式描 述，以“理論上”衡量算法的“好壞”。 如何給出反映算法特性的描述？ 統(tǒng)計(jì)算法中各種運(yùn)算的執(zhí)行情況，包括： 引用了哪些運(yùn)算 每種運(yùn)算被執(zhí)行的次數(shù) 該種運(yùn)算執(zhí)行一次所花費(fèi)的時間等。 算法的執(zhí)行時間=fi*ti,2020/7/2

9、8,頻率計(jì)數(shù) 頻率計(jì)數(shù)：算法中語句或運(yùn)算的執(zhí)行次數(shù)。 例： xx+y for i 1 to n do for i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b) (c) 分析： (a)： xx+y執(zhí)行了1次 (b)： xx+y執(zhí)行了n次 (c)： xx+y執(zhí)行了n2次,2020/7/28,一條語句在整個程序運(yùn)行時實(shí)際執(zhí)行時間= 頻率計(jì)數(shù) * 每執(zhí)行一次該語句所需的時間 在事前分析中，只限于確定與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)的頻率計(jì)數(shù)，依此建立一種理論上分析模型。,2020/7/28,數(shù)量級 用來衡量頻

10、率計(jì)數(shù)的“大小”的一種測度 語句的數(shù)量級：語句的執(zhí)行頻率 例：1，n ，n2 算法的數(shù)量級：算法所包含的所有語句的執(zhí)行頻率之和。 數(shù)量級反映了算法復(fù)雜度的最本質(zhì)的特征。 例：假如求解同一個問題的三個算法分別具有n， n2 ， n3數(shù)量級。 若n=10，則可能的執(zhí)行時間將分別是10，100，1000個單 位時間與環(huán)境因素?zé)o關(guān)。,2020/7/28,頻率計(jì)數(shù)的函數(shù)表示 就計(jì)算時間而言，事前分析階段求得算法在頻率計(jì)數(shù) 上的函數(shù)表示與規(guī)模n有關(guān)的函數(shù)形式，記為： g(n) 不同的算法，g(n)的具體形式是不同的，如 logn，nlogn，n2等 g(n)的一般形式：關(guān)于n的簡單函數(shù)式 “實(shí)際”能夠得到

11、的： 1) 函數(shù)式的最高次項(xiàng) 2)最高次項(xiàng)與函數(shù)整體的關(guān)系。 空間特性分析（與時間特性的分析類似，略）,2020/7/28,2）事后測試 目的：運(yùn)行程序，確定程序?qū)嶋H耗費(fèi)的準(zhǔn)確的時間與空間，與事前分析的結(jié)論進(jìn)行比較，驗(yàn)證先前的分析結(jié)論包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計(jì)的算法。 分析手段：作時、空性能分布圖,2020/7/28,4. 計(jì)算時間的漸近表示,記：算法的實(shí)際計(jì)算時間為f(n)，計(jì)算時間的限界函數(shù)為g(n) 其中， n是輸入或輸出規(guī)模的某種測度。 f(n)表示算法的“實(shí)際”執(zhí)行時間與機(jī)器及語言有關(guān)。 g(n)是事前分析的結(jié)果一個形式簡單的函數(shù)，如nm，logn，2n，n!等。是與頻

12、率計(jì)數(shù)有關(guān)、而與機(jī)器及語言無 關(guān)的函數(shù)。 以下給出算法執(zhí)行時間：上界（）、下界（）、“平均”（ ）的定義。,2020/7/28,1）上界函數(shù),定義1 如果存在兩個正常數(shù)c和n0，對于所有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n) 含義： 如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計(jì)算時間f(n)的一個上界函數(shù)。 f(n)的數(shù)量級就是g(n)。 試圖求出最小的g(n)，使得f(n) = (g(n)。,2020/7/28,多項(xiàng)式定理 定理1 若A(n) = amnm+a1n+a0是一個m次多項(xiàng)式，則有

13、 A(n) = (nm) 即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階 nm同階。 證明：取n0=1,當(dāng)nn0時，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 則，定理得證。,2020/7/28,計(jì)算時間的數(shù)量級的大小對算法的有效性有決定性的影響 例：假設(shè)解決同一個問題的兩個算法，它們都有n個輸入, 計(jì)算時間的數(shù)量級分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運(yùn)算。 n=2048：分別需要4194304和

14、22528次運(yùn)算。 分析： 同等規(guī)模下的計(jì)算量比較： 規(guī)模增大情況下的比較：在n加倍的情況下，一個(n2)的算法計(jì)算時間增長4倍，而一個(nlogn)算法則只用兩倍多一點(diǎn)的時間即可完成。,2020/7/28,多項(xiàng)式時間算法和指數(shù)時間算法,多項(xiàng)式時間算法：可用多項(xiàng)式（函數(shù)）對其計(jì)算時間限界 的算法。 常見的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3) 指數(shù)時間算法：計(jì)算時間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時間限界函數(shù)： (2n) (n！) (nn) 說明：當(dāng)n取值較大時，指數(shù)時間算法和多項(xiàng)式時間算法在計(jì)算時 間上非常懸殊。,2020/7/28,典型的計(jì)算時

15、間函數(shù)曲線,2020/7/28,一般認(rèn)識 當(dāng)數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行 具有比(nlogn)復(fù)雜度還高的算法是比較困難的。 指數(shù)時間算法只有在n取值非常小時才實(shí)用。 要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑 是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算 機(jī)的速度。,2020/7/28,計(jì)算時間函數(shù)值比較,3,2020/7/28,定義1.2 如果存在兩個正常數(shù)c和n0，對于所有的nn0， 有 |f(n)| c|g(n)| 則記作f(n) = (g(n) 含義： 如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間總是不小于|g(n)|的一個常數(shù)倍。所以

16、g(n)是計(jì)算時間f(n)的一個下界函數(shù)。 試圖求出“最大”的g(n)，使得f(n) = (g(n)。,2）下界函數(shù),2020/7/28,定義1.3 如果存在正常數(shù)c1，c2和n0，對于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)| 則記作 含義： 算法在最好和最壞情況下的計(jì)算時間就一個常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎?既有 f(n) = (g(n)，又有f(n) = (g(n),3）“平均情況”限界函數(shù),2020/7/28,4）限界函數(shù)的性質(zhì),1）若 且 ，則 。即具有傳遞性。（ 同） 2） 當(dāng)且僅當(dāng) 3）若 ，則 。即， 定義了一個等價關(guān)系（等價類） 證明： 從定義

17、出發(fā)。證明過程略。,2020/7/28,5. 常用的整數(shù)求和公式,在算法分析中，在統(tǒng)計(jì)語句的頻率時，求和公式的一般形式為： 如：,2020/7/28,1.3 關(guān)于SPARKS語言,本書為描述算法選用的一種計(jì)算機(jī)語言 類PASCAL語言 結(jié)構(gòu)化設(shè)計(jì),2020/7/28,1. 基本語法成分,1）數(shù)據(jù)類型 整型 integer 實(shí)型 float 布爾型 boolean 字符型 char,2）變量聲明 類型說明符 變量； integer i,j; boolean b; char c 3）數(shù)組 任意整數(shù)下標(biāo) integer A(1:5,7:20) integer B(5,7:20),2020/7/28,

18、4）賦值運(yùn)算 （變量）（表達(dá)式） x 2 + x; 5）邏輯運(yùn)算：and or not 6）關(guān)系運(yùn)算： ,2020/7/28,7）控制結(jié)構(gòu)： 順序:（略） 分支: if condition then S1 else S2 endif case :cond1:S1; :cond2:S2; :condn:Sn :else:Sn+1 endcase,循環(huán): while cond do S repeat loop S until cond repeat for vblestart to finish by increment do S repeat,2020/7/28,8) 函數(shù)的定義與調(diào)用 過程定義

19、 procedure NAME(參數(shù)表) （說明部分） S end NAME 過程的調(diào)用： CALL 過程名 函數(shù)定義 類型名 function NAME(參數(shù)表) （說明部分） S return (表達(dá)式) end NAME 函數(shù)的引用：x function（參數(shù)）；,2020/7/28,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ù)值返回，只

20、通過邊界效應(yīng)帶出輸出結(jié)果,2020/7/28,10) 特殊語句 a）exit 退出當(dāng)前一層的循環(huán) b）return 退出過程 return(表達(dá)式) : 函數(shù)返回結(jié)果 c）goto 無條件轉(zhuǎn)向語句 goto label 11) 遞歸 a）直接遞歸：過程中包含對自身的調(diào)用 b）間接遞歸：間接調(diào)用自身 12) 輸入輸出 read、print 13）注釋 /注釋/,2020/7/28,1.4 基本數(shù)據(jù)結(jié)構(gòu),1. 棧和隊(duì)列 線性表： n個元素的有序表 棧和隊(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)算,2020/7/2

21、8,2. 樹 定義1.4 樹（tree）是一個或多個結(jié)點(diǎn)的有限集合，它使得： 有一個指定為根（root）的結(jié)點(diǎn) 剩余結(jié)點(diǎn)被劃分成m0個不相交的集合： T1，Tm 這些集合的每一個又都是一棵樹，并稱T1，Tm為根的子樹。,2020/7/28,關(guān)于樹的重要概念 結(jié)點(diǎn)的度（degree）：一個結(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) 森林：m0個不相交樹的集合。,2020/7/28,3 二元樹 定義1.5 二

22、元樹（binary tree）是結(jié)點(diǎn)的有限集合，它或者為空，或者由一個根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。 二元樹與度為2的樹的區(qū)別 二元樹性質(zhì)： 引理1.1 一棵二元樹第 i級的最大結(jié)點(diǎn)數(shù)是2i-1。深度為k的二元樹的最大結(jié)點(diǎn)數(shù)為2k-1,k0。,2020/7/28,2020/7/28,特殊形態(tài)的二元樹 滿二元樹：深度為k且有2k-1個結(jié)點(diǎn)的二元樹,2020/7/28, 完全二元樹：一棵有n個結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的 結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹中編號為1到 n的結(jié)點(diǎn)時，稱該二元樹是完全的。 完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級上。 完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個一

23、維數(shù)組中（性質(zhì)見引理1.2）。,2020/7/28, 堆：堆是一棵完全二元樹，它的每個結(jié)點(diǎn)的值至少和 該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大 （ max-堆）（或小， min-堆）。 二分檢索樹：二分檢索樹是一棵二元樹，它或者為空， 或者每個結(jié)點(diǎn)含有一個可以比較大小的數(shù)據(jù)元素，且 有： 的左子樹的所有元素比根結(jié)點(diǎn)中的元素小； 的右子樹的所有元素比根結(jié)點(diǎn)中的元素大； 的左子樹和右子樹也是二分檢索樹。 注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異,2020/7/28,3. 圖,圖由稱之為結(jié)點(diǎn)和邊的兩個集合組成，記為 G=（V，E） 其中，是一個有限非空的結(jié)點(diǎn)集合；是結(jié)點(diǎn)對偶的集合，的每一對偶表示的

24、一條邊。,2020/7/28,有關(guān)圖的的重要概念,無向圖：邊表示為（，） 有向圖：邊表示為， 成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖） 鄰接 結(jié)點(diǎn)的度（出度入度） 路徑：由結(jié)點(diǎn)vp到vq的一條路（path）是結(jié)點(diǎn) vp ， vi1 ， vi2 ， ， vim ， vq的一個序列，它使得 ( vp ， vi1 ) ，( vi1 ，vi2 ) ， ，( vim ， vq ) 是E（G）的邊。 路的長度：組成路的邊數(shù)。,2020/7/28,簡單路徑：除了第一和最后一個結(jié)點(diǎn)可以相同以外，其它 所有結(jié)點(diǎn)都不同。 環(huán)：第一個和最后一個結(jié)點(diǎn)相同的簡單路。 連通圖：在無向圖中，如果每對結(jié)點(diǎn)之間都存在一條路徑，則

25、稱該圖是連通的。 子圖：是由G的結(jié)點(diǎn)集V的子集（記為VB）和邊集E中連接VB 中結(jié)點(diǎn)的邊的子集所組成的圖。 連通分圖：一個圖的最大連通子圖。 有向圖的強(qiáng)連通性：在有向圖中，如果對于每一對結(jié)點(diǎn)i和j， 既存在一條從i到j(luò)的路，又存在一條從j 到i的路，則稱該有向圖是強(qiáng)連通的。,2020/7/28,圖的表示方法,鄰接矩陣 鄰接表,2020/7/28,1.5 遞歸和消去遞歸,1. 遞歸 遞歸是一種強(qiáng)有力的設(shè)計(jì)方法 遞歸的效率問題,2020/7/28,例1.3 斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 + Fi-2 （i1) 算法1.7 求斐波那契數(shù) proce

26、dure F(n) /返回第n個斐波那契數(shù)/ integer n if n= 1 then return(1) else return(F(n-1) + F(n-2) endif end F 算法效率：對F(n-1) 、F(n-2)存在大量的重復(fù)計(jì)算 改 進(jìn)：保存中間結(jié)果,2020/7/28,例1.4 歐幾里得算法 已知兩個非負(fù)整數(shù)a和b，且ab0，求這兩個數(shù)的 最大公因數(shù)。 輾轉(zhuǎn)相除法：若b=0，則a和b的最大公因數(shù)等于a；若b0，則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。 算法1.8 求最大公因數(shù) procedure GCD(a,b) / 約定ab / if b=0 then

27、 return(a) else return (GCD(b,a mod b) endif end GDC 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,2020/7/28,例1.5 用遞歸策略設(shè)計(jì)的檢索算法 已知元素x和元素表A（1：n），判斷x是否等于A中 某元素的值。 算法1.9 在A（1：n）中檢索x procedure SEARCH(i) /如果在A（1：n）/中有一元素A（k）=x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0/ global n,x,A(1:n) case :in: return(0) :A(i) = x; ret

28、urn(i) :else: return(SEARCH(i+1) endcase end SEARCH,2020/7/28,2. 消去遞歸,直接遞歸的消去規(guī)則： 基本思路：將遞歸調(diào)用的地方用等價的非遞歸代碼來代替，并對return語句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用和return語句，將之轉(zhuǎn)換成等價的迭代代碼。 初始化 在過程的開始部分，插入說明為棧的代碼并將其初始化為空。在一般情況下，這個棧用來存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 將標(biāo)號L1附于第一條可執(zhí)行語句。然后對于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來代替。,2020/7/28,處理遞歸調(diào)用語句 將所有

29、參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個全程變量來看待。 建立第i個新標(biāo)號Li，并將i存入棧。這個標(biāo)號的i值將用來計(jì)算返回地址。 此標(biāo)號放在規(guī)則所描述的程序段中。 計(jì)算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分： goto L1,2020/7/28,對退出一層遞歸調(diào)用后的處理 如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用 的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂 取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將中建立的標(biāo)號附于這條語句上。 如果此過程不是函數(shù)，則將中建立的標(biāo)號附于所產(chǎn)

30、生的轉(zhuǎn)移語句后面的那條語句。 以上步驟消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return語句進(jìn)行處理。 （純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）,2020/7/28,對每個有return語句的地方，執(zhí)行下述規(guī)則： 如果棧為空，則執(zhí)行正常返回。 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)，out/ inout型）的當(dāng)前值賦給棧頂上的那些對應(yīng)的變量。 如果棧中有返回地址標(biāo)號的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個下標(biāo)賦給一個未使用的變量。 從棧中退出所有局部變量和參數(shù)的值并吧它們賦給對應(yīng)的變量。 如果這個過程是函數(shù)，則插入以下指令，這些指令用來計(jì)算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 用返回地址標(biāo)