計算機算法基礎(chǔ)

計算機算法基礎(chǔ)2023/5/7第1頁，共67頁，2023年，2月20日，星期四序?qū)I(yè)基礎(chǔ)課程：數(shù)據(jù)結(jié)構(gòu)、計算機語言操作系統(tǒng)、編譯如何編寫計算機程序：數(shù)據(jù)結(jié)構(gòu)+算法=程序算法：計算機軟件的“靈魂”算法是計算機科學(xué)和計算機應(yīng)用的核心2023/5/7第2頁，共67頁，2023年，2月20日，星期四教材：計算機算法基礎(chǔ)余祥宣等編著華中科技大學(xué)出版社參考書：算法設(shè)計與分析王曉東編著清華大學(xué)出版社計算機算法導(dǎo)引——設(shè)計與分析盧開澄編著清華大學(xué)出版社IntroductionToAlgorithm高教出版社，MITPress

學(xué)時：32+8學(xué)時2023/5/7第3頁，共67頁，2023年，2月20日，星期四章節(jié)安排第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)√第二章分治法 √第三章貪心方法 √第四章動態(tài)規(guī)劃√第五章檢索與周游 √第六章回溯法 ⊙第七章分枝-限界 ⊙第八章NP-問題 ?

2023/5/7第4頁，共67頁，2023年，2月20日，星期四第一章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1.1算法的定義及特性1.什么是算法？

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

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

★在計算機科學(xué)中，算法是使用計算機解一類問題的精確、有效方法的代名詞；

算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。2023/5/7第5頁，共67頁，2023年，2月20日，星期四2.算法的五個重要特性確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運算必須要有確切的定義，不能有二義性。例：不符合確定性的運算5/0將6或7與x相加未賦值變量參與運算2023/5/7第6頁，共67頁，2023年，2月20日，星期四2）能行性算法中有待實現(xiàn)的運算都是基本的運算，原理上每種運算都能由人用紙和筆在“有限”的時間內(nèi)完成。例：整數(shù)的算術(shù)運算是“能行”的實數(shù)的算術(shù)運算是“不能行”的2023/5/7第7頁，共67頁，2023年，2月20日，星期四3）輸入每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合——定義域（或值域）4）輸出一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關(guān)系的量。2023/5/7第8頁，共67頁，2023年，2月20日，星期四5）有窮性一個算法總是在執(zhí)行了有窮步的運算之后終止。

計算過程：只滿足確定性、能行性、輸入、輸出四個特性的一組規(guī)則。

算法和計算過程的區(qū)別：計算過程：操作系統(tǒng)(不終止的運行過程)算法是“可以終止的計算過程”算法的時效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投入到計算機上運行2023/5/7第9頁，共67頁，2023年，2月20日，星期四4.我們的主要任務(wù)算法學(xué)習(xí)將涉及5個方面的內(nèi)容：1）設(shè)計算法：創(chuàng)造性的活動2）表示算法：思想的表示形式，SPARKS語言3）確認算法：證明算法對所有可能的合法輸入都能得出正確的答案。

算法證明：證明算法的正確性，與語言無關(guān)程序證明：證明程序的正確性4）分析算法：對算法的時、空特性做定量分析，以了解算法的好壞5）測試程序：

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

作時空分布圖：驗證分析結(jié)論，優(yōu)化算法設(shè)計本課程集中于學(xué)習(xí)算法的設(shè)計與分析。通過學(xué)習(xí)，掌握計算機算法設(shè)計和分析基本策略與方法，為設(shè)計更復(fù)雜、更有效的算法奠定基礎(chǔ)2023/5/7第10頁，共67頁，2023年，2月20日，星期四5.課程關(guān)系數(shù)據(jù)結(jié)構(gòu)程序設(shè)計語言：結(jié)構(gòu)化設(shè)計數(shù)學(xué)基礎(chǔ)非數(shù)值計算領(lǐng)域的基本知識2023/5/7第11頁，共67頁，2023年，2月20日，星期四1.2分析算法1.分析算法的目的在于：通過對算法的分析，在把算法變成程序?qū)嶋H運行前，就知道為完成一項任務(wù)所設(shè)計的算法的好壞，從而運行好的算法，改進差的算法，避免無益的人力和物力浪費。算法分析是計算機領(lǐng)域的“古老”而“前沿”的課題。

2023/5/7第12頁，共67頁，2023年，2月20日，星期四2.重要的假設(shè)和約定1）計算機模型的假設(shè)計算機形式理論模型：Turing機模型通用計算機模型：順序計算機有足夠的“內(nèi)存”能在固定的時間內(nèi)存取數(shù)據(jù)單元

2023/5/7第13頁，共67頁，2023年，2月20日，星期四2）計算的約定算法的執(zhí)行時間=∑fi*ti

其中，fi是算法中用到的某種運算i的次數(shù)——稱為該運算的“頻率計數(shù)”ti是該運算執(zhí)行一次所用的時間——與程序語言和硬件有關(guān)

確定：使用何種運算及其執(zhí)行時間。從運算的“時間特性”上將運算的分類：

時間囿界于常數(shù)的運算：

·基本算術(shù)運算，如整數(shù)、浮點數(shù)的加、減、乘、除

·字符運算、賦值運算、過程調(diào)用等特點：盡管每種運算的執(zhí)行時間不同，但一般只花一個固定量的時間（單位時間）就可完成。2023/5/7第14頁，共67頁，2023年，2月20日，星期四2）計算的約定（續(xù)）其他運算：

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

·記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān)特點：運算時間無定量。如何分析非時間囿界于常數(shù)的運算：分解成若干時間囿界于常數(shù)的運算。

如：tstring=Length（String）*tchar2023/5/7第15頁，共67頁，2023年，2月20日，星期四3）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運行算法，以了解算法的性能。編制測試數(shù)據(jù)是程序測試與算法分析中的關(guān)鍵技術(shù)之一。

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

·作為程序正確性及性能測試的數(shù)據(jù)集：測試程序的對錯，反映對性能指標(biāo)產(chǎn)生影響的方面,如邊界值2023/5/7第16頁，共67頁，2023年，2月20日，星期四3.如何進行算法分析？對算法進行全面分析，可分兩個階段進行：事前分析：求算法的一個時間/空間限界函數(shù)，即通過對算法的“理論”分析，得出關(guān)于算法時間和空間特性的特征函數(shù)（Ο、Ω）——與計算機物理軟硬件沒有直接關(guān)系。事后測試：將算法編制成程序后實際放到計算機上運行，收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行分析判斷——直接與物理實現(xiàn)有關(guān)。2023/5/7第17頁，共67頁，2023年，2月20日，星期四1）事前分析目的：試圖得出關(guān)于算法特性的一種形式描述，以“理論上”衡量算法的“好壞”。如何給出反映算法特性的描述？統(tǒng)計算法中各種運算的執(zhí)行情況，包括：引用了哪些運算每種運算被執(zhí)行的次數(shù)該種運算執(zhí)行一次所花費的時間等。

算法的執(zhí)行時間=∑fi*ti2023/5/7第18頁，共67頁，2023年，2月20日，星期四頻率計數(shù)

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

例：x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)分析：(a)：x←x+y執(zhí)行了1次(b)：x←x+y執(zhí)行了n次(c)：x←x+y執(zhí)行了n2次2023/5/7第19頁，共67頁，2023年，2月20日，星期四一條語句在整個程序運行時實際執(zhí)行時間=

頻率計數(shù)*每執(zhí)行一次該語句所需的時間在事前分析中，只限于確定與所使用的機器及其他環(huán)境因素?zé)o關(guān)的頻率計數(shù)，依此建立一種理論上分析模型。2023/5/7第20頁，共67頁，2023年，2月20日，星期四數(shù)量級——衡量頻率計數(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)。2023/5/7第21頁，共67頁，2023年，2月20日，星期四頻率計數(shù)的函數(shù)表示就計算時間而言，事前分析階段求得算法在頻率計數(shù)上的函數(shù)表示——與規(guī)模n有關(guān)的函數(shù)形式，記為：g(n)

★不同的算法，g(n)的具體形式是不同的，如logn，nlogn，n2等

★g(n)的一般形式：關(guān)于n的簡單函數(shù)式“實際”能夠得到的：1)函數(shù)式的最高次項2)最高次項與函數(shù)整體的關(guān)系。空間特性分析（與時間特性的分析類似，略）2023/5/7第22頁，共67頁，2023年，2月20日，星期四2）事后測試目的：運行程序，統(tǒng)計執(zhí)行實際耗費的準(zhǔn)確的時間與空間，與事前分析的結(jié)論進行比較，驗證先前的分析結(jié)論——包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計的算法。分析手段：作時、空性能分布圖2023/5/7第23頁，共67頁，2023年，2月20日，星期四4.計算時間的漸近表示記：算法的實際計算時間為f(n)，計算時間的限界函數(shù)為g(n)其中，

n是輸入或輸出規(guī)模的某種測度。f(n)表示算法的“實際”執(zhí)行時間—與機器及語言有關(guān)。

g(n)是事前分析的結(jié)果——一個形式簡單的函數(shù)，如nm，logn，2n，n!等。是與頻率計數(shù)有關(guān)、而與機器及語言無關(guān)的函數(shù)。

以下給出算法執(zhí)行時間：上界（О）、下界（Ω）、“平均”（）的定義。2023/5/7第24頁，共67頁，2023年，2月20日，星期四1）上界函數(shù)定義1如果存在兩個正常數(shù)c和n0，對于所有的n≥n0，有|f(n)|≤c|g(n)|則記作f(n)=Ο(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個上界函數(shù)。f(n)的數(shù)量級就是g(n)。試圖求出最小的g(n)，使得f(n)=Ο(g(n))。

2023/5/7第25頁，共67頁，2023年，2月20日，星期四多項式定理定理1若A(n)=amnm+…+a1n+a0是一個m次多項式，則有A(n)=Ο(nm)即：變量n的固定階數(shù)為m的任一多項式，與此多項式的最高階

nm同階。證明：取n0=1,當(dāng)n≥n0時，有|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm

＝(|am|+|am-1|+…+|a0|)nm

令c=|am|+|am-1|+…+|a0|則，定理得證。2023/5/7第26頁，共67頁，2023年，2月20日，星期四計算時間的數(shù)量級的大小對算法的有效性有決定性的影響例：假設(shè)解決同一個問題的兩個算法，它們都有n個輸入,計算時間的數(shù)量級分別是n2和nlogn。則，n=1024：分別需要1048576和10240次運算。n=2048：分別需要4194304和22528次運算。分析：

★

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

★

規(guī)模增大情況下的比較：在n加倍的情況下，一個Ο(n2)的算法計算時間增長4倍，而一個Ο(nlogn)算法則只用兩倍多一點的時間即可完成。2023/5/7第27頁，共67頁，2023年，2月20日，星期四多項式時間算法和指數(shù)時間算法多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。常見的多項式限界函數(shù)有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法常見的指數(shù)時間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)說明：當(dāng)n取值較大時，指數(shù)時間算法和多項式時間算法在計算時間上非常懸殊。2023/5/7第28頁，共67頁，2023年，2月20日，星期四典型的計算時間函數(shù)曲線2023/5/7第29頁，共67頁，2023年，2月20日，星期四一般認識當(dāng)數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)有的計算機系統(tǒng)上運行具有比Ο(nlogn)復(fù)雜度還高的算法是比較困難的。指數(shù)時間算法只有在n取值非常小時才實用。要想在順序處理機上擴大所處理問題的規(guī)模，有效的途徑是降低算法的計算復(fù)雜度，而不是（僅僅依靠）提高計算機的速度。2023/5/7第30頁，共67頁，2023年，2月20日，星期四計算時間函數(shù)值比較32023/5/7第31頁，共67頁，2023年，2月20日，星期四定義1.2如果存在兩個正常數(shù)c和n0，對于所有的n≥n0，有|f(n)|≥c|g(n)|則記作f(n)=Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是不小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個下界函數(shù)。試圖求出“最大”的g(n)，使得f(n)=Ω(g(n))。2）下界函數(shù)2023/5/7第32頁，共67頁，2023年，2月20日，星期四定義1.3如果存在正常數(shù)c1，c2和n0，對于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|則記作含義：算法在最好和最壞情況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔衒(n)=Ω(g(n))，又有f(n)=Ο(g(n))3）“平均情況”限界函數(shù)2023/5/7第33頁，共67頁，2023年，2月20日，星期四4）限界函數(shù)的性質(zhì)1）若且，則。即О具有傳遞性。（同）2）當(dāng)且僅當(dāng)3）若，則。即，定義了一個等價關(guān)系（等價類）證明：從定義出發(fā)。證明過程略。2023/5/7第34頁，共67頁，2023年，2月20日，星期四5.常用的整數(shù)求和公式在算法分析中，在統(tǒng)計語句的頻率時，求和公式的一般形式為：如：2023/5/7第35頁，共67頁，2023年，2月20日，星期四1.3關(guān)于SPARKS語言本書為描述算法選用的一種計算機語言類PASCAL語言結(jié)構(gòu)化設(shè)計2023/5/7第36頁，共67頁，2023年，2月20日，星期四1.基本語法成分1）數(shù)據(jù)類型整型integer實型float布爾型boolean字符型char2）變量聲明類型說明符變量；integeri,j;booleanb;charc3）數(shù)組任意整數(shù)下標(biāo)integerA(1:5,7:20)integerB(5,7:20)2023/5/7第37頁，共67頁，2023年，2月20日，星期四4）賦值運算

（變量）←（表達式）x←2+x;5）邏輯運算：andornot6）關(guān)系運算：＜≤＝≠≥＞2023/5/7第38頁，共67頁，2023年，2月20日，星期四7）控制結(jié)構(gòu)：

順序:（略）分支:

·ifconditionthenS1elseS2endif

·case:cond1:S1;:cond2:S2;…:condn:Sn:else:Sn+1endcase循環(huán):

·whileconddoSrepeat

·loopSuntilcondrepeat

·forvble←starttofinishbyincrementdoSrepeat2023/5/7第39頁，共67頁，2023年，2月20日，星期四8)函數(shù)的定義與調(diào)用

過程定義procedureNAME((參數(shù)表))（說明部分）SendNAME

過程的調(diào)用：CALL過程名函數(shù)定義類型名procedureNAME((參數(shù)表))（說明部分）Sreturn(表達式)endNAME

函數(shù)的引用：x←function（參數(shù)）；2023/5/7第40頁，共67頁，2023年，2月20日，星期四9)變量的分類a）根據(jù)數(shù)據(jù)類型分類整型、實型、字符型等b）根據(jù)作用域分類：全程變量、局部變量、形式參數(shù)c）根據(jù)是否帶入、帶出數(shù)據(jù)值/結(jié)果分類：in型變量out型變量inout型變量

邊界效應(yīng)：改變了參變量或全程變量的值函數(shù)：通過函數(shù)值返回輸出結(jié)果，沒有邊界效應(yīng)純過程：沒有函數(shù)值返回，只通過邊界效應(yīng)帶出輸出結(jié)果2023/5/7第41頁，共67頁，2023年，2月20日，星期四10)特殊語句a）exit退出當(dāng)前一層的循環(huán)b）return退出過程return(表達式):函數(shù)返回結(jié)果c）goto無條件轉(zhuǎn)向語句gotolabel11)遞歸a）直接遞歸：過程中包含對自身的調(diào)用b）間接遞歸：間接調(diào)用自身12)輸入輸出read、print13）注釋//注釋//2023/5/7第42頁，共67頁，2023年，2月20日，星期四1.4基本數(shù)據(jù)結(jié)構(gòu)1.棧和隊列線性表：n個元素的有序表棧和隊列：特殊的線性表利用動態(tài)數(shù)據(jù)結(jié)構(gòu)——鏈表實現(xiàn)?；蜿犃欣渺o態(tài)數(shù)據(jù)結(jié)構(gòu)——數(shù)組實現(xiàn)?；蜿犃谢谝陨蟽煞N表示形式的棧和隊列上的基本運算2023/5/7第43頁，共67頁，2023年，2月20日，星期四2.樹定義1.4樹（tree）是一個或多個結(jié)點的有限集合，它使得：有一個指定為根（root）的結(jié)點剩余結(jié)點被劃分成m≥0個不相交的集合：T1，…，Tm這些集合的每一個又都是一棵樹，并稱T1，…，Tm為根的子樹。2023/5/7第44頁，共67頁，2023年，2月20日，星期四關(guān)于樹的重要概念結(jié)點的度（degree）：一個結(jié)點的子樹數(shù)樹的度：樹中結(jié)點度的最大值結(jié)點的級（level）（又叫層）：設(shè)根是1級，若某結(jié)點在p級，則它的兒子在p+1級樹的高度（或深度）：樹中結(jié)點的最大級數(shù)葉子（終端結(jié)點）：度為0的結(jié)點內(nèi)結(jié)點（非終端結(jié)點）：度不為0的結(jié)點森林：m≥0個不相交樹的集合。2023/5/7第45頁，共67頁，2023年，2月20日，星期四3二元樹定義1.5二元樹（binarytree）是結(jié)點的有限集合，它或者為空，或者由一個根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。二元樹與度為2的樹的區(qū)別二元樹性質(zhì)：引理1.1一棵二元樹第i級的最大結(jié)點數(shù)是2i-1。深度為k的二元樹的最大結(jié)點數(shù)為2k-1,k>0。

2023/5/7第46頁，共67頁，2023年，2月20日，星期四2023/5/7第47頁，共67頁，2023年，2月20日，星期四特殊形態(tài)的二元樹①滿二元樹：深度為k且有2k-1個結(jié)點的二元樹

2023/5/7第48頁，共67頁，2023年，2月20日，星期四②完全二元樹：一棵有n個結(jié)點深度為k的二元樹，當(dāng)它的結(jié)點相當(dāng)于深度為k的滿二元樹中編號為1到n的結(jié)點時，稱該二元樹是完全的。完全二元樹的葉子結(jié)點至多出現(xiàn)在相鄰的兩級上。完全二元樹的結(jié)點可以緊湊地存放在一個一維數(shù)組中（性質(zhì)見引理1.2）。2023/5/7第49頁，共67頁，2023年，2月20日，星期四③堆：堆是一棵完全二元樹，它的每個結(jié)點的值至少和該結(jié)點的兒子們（如果存在的話）的值一樣大（max-堆）（或小，min-堆）。④二分檢索樹：二分檢索樹Ｔ是一棵二元樹，它或者為空，或者每個結(jié)點含有一個可以比較大小的數(shù)據(jù)元素，且有：·Ｔ的左子樹的所有元素比根結(jié)點中的元素?。弧ぃ缘挠易訕涞乃性乇雀Y(jié)點中的元素大；·Ｔ的左子樹和右子樹也是二分檢索樹。

注：二分檢索樹要求樹中所有結(jié)點的元素值互異2023/5/7第50頁，共67頁，2023年，2月20日，星期四3.圖圖Ｇ由稱之為結(jié)點Ｖ和邊Ｅ的兩個集合組成，記為G=（V，E）其中，Ｖ是一個有限非空的結(jié)點集合；Ｅ是結(jié)點對偶的集合，Ｅ的每一對偶表示Ｇ的一條邊。2023/5/7第51頁，共67頁，2023年，2月20日，星期四有關(guān)圖的的重要概念無向圖：邊表示為（ｉ，ｊ）有向圖：邊表示為〈ｉ，ｊ〉成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖）鄰接結(jié)點的度（出度／入度）路徑：由結(jié)點vp到vq的一條路（path）是結(jié)點vp，

vi1，

vi2，

…，

vim，

vq的一個序列，它使得(vp，

vi1)

，(vi1，vi2)

，

…，(

vim，

vq)是E（G）的邊。路的長度：組成路的邊數(shù)。2023/5/7第52頁，共67頁，2023年，2月20日，星期四簡單路徑：除了第一和最后一個結(jié)點可以相同以外，其它所有結(jié)點都不同。環(huán)：第一個和最后一個結(jié)點相同的簡單路。連通圖：在無向圖中，如果每對結(jié)點之間都存在一條路徑，則稱該圖是連通的。子圖：是由G的結(jié)點集V的子集（記為VB）和邊集E中連接VB中結(jié)點的邊的子集所組成的圖。連通分圖：一個圖的最大連通子圖。有向圖的強連通性：在有向圖中，如果對于每一對結(jié)點i和j，既存在一條從i到j(luò)的路，又存在一條從j到i的路，則稱該有向圖是強連通的。2023/5/7第53頁，共67頁，2023年，2月20日，星期四圖的表示方法鄰接矩陣鄰接表2023/5/7第54頁，共67頁，2023年，2月20日，星期四1.5遞歸和消去遞歸1.遞歸遞歸是一種強有力的設(shè)計方法遞歸的效率問題2023/5/7第55頁，共67頁，2023年，2月20日，星期四例1.3斐波那契(Fibonacci)序列：F0=F1=1Fi=Fi-1+Fi-2（i>1)算法1.7求斐波那契數(shù)procedureF(n)//返回第n個斐波那契數(shù)//integernifn<=1thenreturn(1)elsereturn(F(n-1)+F(n-2))endifendF算法效率：對F(n-1)、F(n-2)存在大量的重復(fù)計算改進：保存中間結(jié)果2023/5/7第56頁，共67頁，2023年，2月20日，星期四例1.4歐幾里得算法已知兩個非負整數(shù)a和b，且a＞b≥0，求這兩個數(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))endifendGDC例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;2023/5/7第57頁，共67頁，2023年，2月20日，星期四例1.5用遞歸策略設(shè)計的檢索算法已知元素x和元素表A（1：n），判斷x是否等于A中某元素的值。算法1.9在A（1：n）中檢索xprocedureSEARCH(i)//如果在A（1：n）//中有一元素A（k）=x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0//globaln,x,A(1:n)case:i>n:return(0):A(i)=x;return(i):else:return(SEARCH(i+1))endcaseendSEARCH2023/5/7第58頁，共67頁，2023年，2月20日，星期四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ī)則的指令來代替。2023/5/7第59頁，共67頁，2023年，2月20日，星期四

處理遞歸調(diào)用語句⑶將所有參數(shù)和局部變量的值存入棧。

棧頂指針可作為一個全程變量來看待。⑷建立第i個新標(biāo)號Li，并將i存入棧。這個標(biāo)號的i值將用來計算返回地址。此標(biāo)號放在規(guī)則⑺所描述的程序段中。⑸計算這次調(diào)用的各實在參數(shù)（可能是表達式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。⑹插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分：gotoL12023/5/7第60頁，共67頁，2023年，2月20日，星期四

對退出一層遞歸調(diào)用后的處理⑺如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將⑷中建立的標(biāo)號附于這條語句上。如果此過程不是函數(shù)，則將⑷中建立的標(biāo)號附于⑹所產(chǎn)生的轉(zhuǎn)移語句后面的那條語句。以上步驟消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return語句進行處理。

（純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）2023/5/7第61頁，共67頁，2023年，2月20日，星期四

對每個有return語句的地方，執(zhí)行下述規(guī)則：⑻如果棧為空，則執(zhí)行正常返回。⑼否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)，out/inout型）的當(dāng)前值賦給棧頂上的那些對應(yīng)的變量。⑽如果棧中有返回地址標(biāo)號的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個下標(biāo)賦給一個未使用的變量。⑾從棧中退出所有局部變量和參數(shù)的值并吧它們賦給對應(yīng)的變量。⑿如果這個過程是函數(shù)，則插入以下指令，這些指令用來計算緊接在return后面的表達式并將結(jié)果值存入棧頂。⒀用返回地址標(biāo)號的下標(biāo)實現(xiàn)對該標(biāo)號的轉(zhuǎn)向。2023/5/7第62頁，共67頁，2023年，2月20日，星期四例1.6遞歸調(diào)用示例求數(shù)組元素中的最大值算法1.10求取數(shù)組元素的最大值（遞歸算法）procedureMAX1(i)//查找數(shù)組A中最大值元素，并返回該元素的最大下標(biāo)。//globalintegern,A(1:n),j,kintegeriifi<nthenj←MAX1(i+1)//遞歸調(diào)用//ifA(i)>A(j)thenk←ielsek←jendifelsek←nendif

return(k)//遞歸調(diào)用的返回//endMAX12023/5/7第63頁，共67頁，2023年，2月20日，星期四消去上例中的遞歸算法1.11使用上述的規(guī)則消去例1.10中的遞歸代碼procedureMAX2(i)localintegerj,k;globali