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

1、2024/3/17,計算機(jī)算法基礎(chǔ),周中成蘇州科技學(xué)院應(yīng)用數(shù)學(xué)系,2024/3/17,序,先修課：高等數(shù)學(xué)高等代數(shù)程序設(shè)計——使用高級程序語言描述一個 具體算法的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)——為表達(dá)非數(shù)值算法提供了抽 象的運(yùn)算機(jī)制,,,數(shù)學(xué)類,計算機(jī)類,2024/3/17,,如何編寫計算機(jī)程序：數(shù)據(jù)結(jié)構(gòu)+算法 = 程序算法：計算機(jī)軟件的“靈魂”

2、 結(jié)論：算法是計算機(jī)科學(xué)和計算機(jī)應(yīng)用的核心，圖靈獎得主Donald E. Knuth說：”計算機(jī)科學(xué)就是算法的研究“,2024/3/17,教材： 算法分析與設(shè)計 劉任任主編 武漢理工大學(xué)出版社 參考書： 算法設(shè)計技巧與分析 [沙特]M.H.Alsuwaiyel 電子工業(yè)出版社Introduction to The Design & Analysis of Al

3、gorithms(算法設(shè)計與分析基礎(chǔ))（影印版） [美] Anany Levitin 算法設(shè)計與分析 王曉東編著 清華大學(xué)出版社 計算機(jī)算法導(dǎo)引——設(shè)計與分析 盧開澄編著 清華大學(xué)出版社 Introduction To Algorithm 高教出版社，MIT Press 學(xué)時：51學(xué)時,2024/3/17,章節(jié)安排,第一章 導(dǎo)論 √第二章 分治與遞歸

4、 √第三章 貪心算法 √第四章 動態(tài)規(guī)劃 √第五章 回溯法 ⊙第六章 分枝-限界法 ⊙第八章 NP完全問題 ?,2024/3/17,第一章 引論,§1.1 算法的定義及特性1. 什么是算法（algorithm）

5、算法如數(shù)學(xué)、計算一樣，是一個基本概念。 ★ Webster辭典：“algorithm（算法）在有限步驟內(nèi)解一個數(shù)學(xué)問題的過程，步驟中常常包括某一操作的重復(fù)。更廣義地說，一個算法就是為解一個問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程“ ★D.E.Knuth說：一個算法就是一個有窮規(guī)則的集合，其中的規(guī)則規(guī)定了一個解決某一特定類型的問題的運(yùn)算序列。此外，它還具有下面第二部分所述的5個重要特征,2024/3/17,2.

6、算法的五個重要特性 有窮性、確定性、可行性、輸入、輸出,1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：菜譜就不是一個算法，因為菜譜中經(jīng)常有這樣的步驟：“加入食鹽少許”，這種“少許”是不確定的。,2024/3/17,2）可行性 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在“有限”的時間內(nèi)完成。,2024/3/17,3）輸入 每個算法有0個或多個輸入。這

7、些輸入是在算法開始之前給出的量，取自于特定的對象集合——定義域（或值域）,4）輸出 一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關(guān)系的量。,2024/3/17,5）有窮性 一個算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。 3。計算過程與算法 只滿足確定性、能行性、輸入、輸出四個特性的一組規(guī)則。 算法和計算過程的區(qū)別： 計算過程：操作系統(tǒng)(不終止的運(yùn)行過程) 算法是“可以

8、終止的計算過程” 算法的時效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投 入到計算機(jī)上運(yùn)行,2024/3/17,4。程序與算法,二者關(guān)系：程序可以用來描述算法，同一個算法可以用不同語言（c, basic, 匯編）編寫的程序來描述。 程序不一定是算法，因為它不一定符合算法的5條性質(zhì)，如操作系統(tǒng)作為整體是程序，但不是一個算法，因為操作系統(tǒng)是無限循環(huán)的過程,2024/

9、3/17,5. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個方面的內(nèi)容： 1）設(shè)計算法：創(chuàng)造性的活動 2）表示算法：思想的表示形式：類C語言、SPARKS語言（類PASCAL語 言） 3）確認(rèn)算法：證明算法對所有可能的合法輸入都能得出正確的答案。 算法

10、證明：證明算法的正確性，與語言無關(guān) 程序證明：證明程序的正確性 4）分析算法：對算法的時、空特性做定量分析，以了解算法的好壞 5）測試程序： 調(diào)試：“調(diào)試只能指出有錯誤，而不能指出它們不存在錯誤”

11、 作時空分布圖：驗證分析結(jié)論，優(yōu)化算法設(shè)計 本課程集中于學(xué)習(xí)算法的設(shè)計與分析。通過學(xué)習(xí)，掌握計算機(jī)算法設(shè)計和分析基本策略與方法，為設(shè)計更復(fù)雜、更有效的算法奠定基礎(chǔ),2024/3/17,6. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計語言：結(jié)構(gòu)化設(shè)計 數(shù)學(xué)基礎(chǔ) 非數(shù)值計算領(lǐng)域的基本知識,2024/3/17,§1.2 分析算法,分析算法的目的及歷史背景目的：通過對算法的分析，在把算法變成程序

12、實(shí)際運(yùn)行前，就知道為完成一項任務(wù)所設(shè)計的算法（主要在時空效率方面）的好壞，從而選擇好的算法，改進(jìn)差的算法。歷史背景：算法分析是計算機(jī)領(lǐng)域的“古老”而“前沿”的課題。稱為計算復(fù)雜性問題，屬于計算理論的一個重要領(lǐng)域，它是由于對有效算法的需求而發(fā)展起來的，產(chǎn)生于二十世紀(jì)六十年代，繁榮于七、八十年代。,2024/3/17,算法分析的標(biāo)準(zhǔn),1。正確性(Correctness)2。簡潔、清晰(Simplicity) 一般而言（并

13、不必然如此），最簡單、思路最直接的解決方法效率往往不是最佳的。然而，簡潔性也是一個算法值得追求的目標(biāo)。它可以使驗證算法的正確性相對容易，它也使我們編寫、調(diào)試、修改程序更為容易。當(dāng)然，若程序使用頻率很高，算法的效率還是選擇算法的決定性因素。3。優(yōu)化性(Optimality)符合優(yōu)化性的算法不是已知中最好的（the best known），而是解決問題的一切可能算法中最好的(the best possible)。4。空間復(fù)雜度(Spa

14、ce Complexity)5。時間復(fù)雜性,2024/3/17,如何衡量時間復(fù)雜性,算法（程序）實(shí)際執(zhí)行時間,程序中的指令或語句的執(zhí)行次數(shù)（頻率計數(shù)）,受運(yùn)行機(jī)器性能的影響,——缺陷：,——缺陷：,高度依賴于編程語言及程序員的編程風(fēng)格，并要首先編寫調(diào)試程序（也要花費(fèi)精力）。,課堂問題,2024/3/17,頻率計數(shù),頻率計數(shù)：算法中語句或運(yùn)算的執(zhí)行次數(shù)。 例： x←x+y for i ←1 to n

15、do for i ←1 to n do x ← x + y for j ←1 to n do repeat x ← x +y x=x2

16、 repeat repeat x=x2 (a) (b)

17、 (c) 分析： (a)： x←x+y執(zhí)行了1次 (b)： x←x+y執(zhí)行了n次，x=x2 ，執(zhí)行一次 (c)： x←x+y執(zhí)行了n2次，x=x2 ，執(zhí)行一次 一條語句在整個程序運(yùn)行時實(shí)際執(zhí)行時間=頻率計數(shù) * 每執(zhí)行一次該語句所需的時間,2024/3/17,如何克服上述辦法的缺陷？,我們需要的是衡量一個算法所使用方法、策略的效率的度量，我們要求：a、這個

18、度量要獨(dú)立于機(jī)器；b、編程語言、程序員，c、我們主要不是關(guān)心小規(guī)模輸入量的情況，而是關(guān)心大輸入量時的算法運(yùn)行情況。,2024/3/17,正確的解決辦法,因此，我們實(shí)際上只計算算法中的特定基本操作而省略初始化操作、循環(huán)控制及其他操作。這種基本操作一般同實(shí)際運(yùn)行時間是成比例的。,2024/3/17,一些基本操作的合理選擇,問題1 在數(shù)組中查找元素x,基本操作選擇：,X與數(shù)組中元素的比較,問題2 矩陣相乘,基本操作選擇：,兩個實(shí)數(shù)相乘

19、,問題3 排序,基本操作選擇：,兩個元素的比較,課堂問題,2024/3/17,問題：需要精確計算運(yùn)算次數(shù)嗎？,解決方法：由于我們只對大輸入量時的運(yùn)行情況感興趣且沒必要非常精確地計算運(yùn)算次數(shù)或運(yùn)算時間，可以只討論運(yùn)行時間的增長率或增長的階。常見的階有：logn<n<nlogn<n2<n3<2n,我們分析算法的時間復(fù)雜性時，我們的主要目的是將此算法同解決同一問題的其他算法或不同的問題的算法相比較，時間復(fù)雜度是

20、相對的而不是絕對的。要精確計算所有運(yùn)算的次數(shù)，如果不是不可能的話，也是非常麻煩的，實(shí)際上對于我們的算法分析的實(shí)際目的而言也是不必要的。,2024/3/17,示例 有解決同一問題的兩個算法A和B，其時間復(fù)雜度分別為10n2和n3，當(dāng)n比較大時，系數(shù)10根本不起作用。,2024/3/17,算法C時間復(fù)雜度為100n2,2024/3/17,,這一點(diǎn)可以從如下數(shù)學(xué)分析結(jié)果看出：,同樣的道理可以用于函數(shù)f(n)=n3+2n2+5n中（假定是算法

21、D的時間復(fù)雜度）的低階項上。容易看出，隨著n的增大，低階項的影響越來越小。因此，可以說，算法A、B、C、D的時間復(fù)雜度分別為n2、n3、n2、n3階的。,2024/3/17,典型的計算時間函數(shù)曲線,2024/3/17,,計算時間函數(shù)值比較,3,2024/3/17,典型的函數(shù)階,2024/3/17,三個形式化表達(dá)時間復(fù)雜性的數(shù)學(xué)符號,,2024/3/17,1）上界函數(shù),定義1 如果存在兩個正常數(shù)c和n0，對于所有的n≥n0，有

22、 |f(n)| ≤ c|g(n)| 則記作f(n) = Ο(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個上界函數(shù)。 f(n)的數(shù)量級就是g(n)。一般試圖求出最小的g(n)，使得f(n) = Ο(g(n))。,即從n0及以后項，不等式成立。,2024/3/17,定義1.2 如果存在兩個正常

23、數(shù)c和n0，對于所有的n≥n0， 有 |f(n)| ≥ c|g(n)| 則記作f(n) = Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間總是不小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個下界函數(shù)。一般試圖求出“最大”的g(n)，使得f(n) = Ω(g(n))。,2）下界函數(shù),即從n0及以后項，不等式成立。

24、,2024/3/17,定義1.3 如果存在正常數(shù)c1，c2和n0，對于所有的n≥n0，有 c1|g(n)| ≤|f(n)| ≤ c2|g(n)| 則記作含義：算法在最好和最壞情況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎?既有 f(n) = Ω(g(n))，又有f(n) = Ο(g(n)),3）“平均情況”限界函數(shù),為有助于理解，可以認(rèn)為O類似于≤ ； Ω類似于≥ ，而,2024/

25、3/17,例 設(shè)f(n)=10n2+20n,顯然， f(n)=10n2+20n>n2,n>1,所以有f(n)= Ω(n2)。因為f(n)=10n2+20n2,所以有f(n)=O(n2)。由以上兩點(diǎn)可以推出,2024/3/17,例 一般地，對一般多項式f(n)=c1nk+c2n(k-1)+…+ckn+ck+1(c1≠0),f(n)=Ω (nk)。f(n)=O(nk)。由以上兩點(diǎn)可以推出,2024/3/17,最壞情

26、形復(fù)雜度 與 平均情形復(fù)雜度,即使輸入量大小相同，不同的輸入數(shù)據(jù)會導(dǎo)致基本運(yùn)算執(zhí)行次數(shù)也不同，有時候還差別很大?？紤]一個簡單的問題，即在無序數(shù)組a[1:n]中查找元素x，我們采用從前向后順序查找法。（假定x必在數(shù)組中）若x在數(shù)組開頭a[1]，則只需一次比較運(yùn)算；若x在數(shù)組末尾a[n]，則要n次比較運(yùn)算；很明顯，同樣的輸入規(guī)模（都有n個輸入量），但不同情況下要用的運(yùn)算次數(shù)明顯差異很大，上述問題中最壞情形下要用n次比較運(yùn)算。當(dāng)然（這是

27、最壞情形復(fù)雜度），我們可能對平均情況下的比較次數(shù)更感興趣（這是平均情形復(fù)雜度）。,2024/3/17,最壞情形復(fù)雜度與平均情形復(fù)雜度的形式化定義,符號的約定 Dn是對于所考慮問題來說輸入大小為n的輸入集合；I是Dn的一個元素，p(I)為I出現(xiàn)的概率，t(I)是算法在輸入I時所執(zhí)行的基本運(yùn)算次數(shù)。,例如：在無序數(shù)組中查找查找元素問題中，Dn即表示有n個元素的所有可能情形。,2024/3/17,算法的平均情形復(fù)雜度,A（n）=∑

28、 p(I) t(I) (I屬于Dn),算法的最壞情形復(fù)雜度,W（n）=max{ t(I)} (I屬于Dn),描述算法的一般情況下的表現(xiàn)，但必須要首先知道輸入數(shù)據(jù)的出現(xiàn)概率，可能要經(jīng)過大規(guī)模的統(tǒng)計，不一定容易得到，另外，平均情形復(fù)雜度的計算也可能是個數(shù)學(xué)難題,描述算法在最壞情況下的表現(xiàn)，相對容易計算，在無法計算平均情形復(fù)雜度時，只能計算最壞情形復(fù)雜度，并以之作為度量算法效率的表準(zhǔn),2024/3/17,例 順序搜索無序表,輸入E(含n個元

29、素的序列)n（序列E中元素個數(shù)）K（搜索元素，設(shè)為整數(shù)，E[i]也設(shè)為整數(shù)）輸出K在序列E中位序，若找不到返回-1,2024/3/17,算法,int seqSearch(int[] E,int n,int K){int ans,index;ans=-1;for(index=0;index<n;index++) if(K==E(index)) { ans=index; break; }

30、return ans;},基本操作：K同E中元素的比較,2024/3/17,最壞情形復(fù)雜度,顯然，當(dāng)K在序列末尾或不在序列中，需要比較n次，所以W（n）=n,2024/3/17,平均情形復(fù)雜度,假定序列中元素互不相同；若K在此序列中，假定K在序列中的位置是等可能的。Ii：代表K在位置i的所有輸入A1(n)= = =,在查找成功的情形下，平均比較次數(shù)約為序列長度的一半，這同

31、我們的直覺是相符的。,2024/3/17,元素不在序列中的情形,顯然，此時平均情形復(fù)雜度為A2(n)=n,綜合上述兩種情形（K在序列與不在序列中）,,A(n)=Pr(查找成功時)A1(n)+Pr(查找不成功時)A2(n),設(shè)查找成功的概率為q，而查找不成功的概率顯然為1-q，,2024/3/17,a.q=1(K必在序列中) A(n)=（n+1）/2 b.q=0(K必不在序列中) A(n)= nc.q=1/2(K在序列中概率

32、為一半) A(n)= n3/4+1/4,,2024/3/17,§ 1.3 關(guān)于類c語言與類Pascal語言——SPARKS語言,SPARKS語言類PASCAL語言結(jié)構(gòu)化設(shè)計經(jīng)常作為教學(xué)用語言,類c語言見教材（此處略）,2024/3/17,1. 基本語法成分,1）數(shù)據(jù)類型 整型 integer 實(shí)型 float 布爾型 boolean 字符型 c

33、har,2）變量聲明 類型說明符 變量； integer i,j; boolean b; char c3）數(shù)組 任意整數(shù)下標(biāo) integer A(1:5,7:20) integer B(5,7:20),2024/3/17,4）賦值運(yùn)算 （變量）←（表達(dá)式） x ← 2 + x;5）邏輯運(yùn)算：and or not6）關(guān)系運(yùn)算：＜

34、 ≤ ＝ ≠ ≥ ＞,2024/3/17,7）控制結(jié)構(gòu)： 順序:（略） 分支: · if condition then S1 else S2 endif · case :cond1:S1;

35、 :cond2:S2; … :condn:Sn :else:Sn+1 endcase,循環(huán): ·while cond do S repeat ·loop S until cond repeat

36、·for vble←start to finish by increment do S repeat,2024/3/17,8) 函數(shù)的定義與調(diào)用 過程定義 procedure NAME((參數(shù)表)) （說明部分） S

37、 end NAME 過程的調(diào)用： CALL 過程名 函數(shù)定義 類型名 procedure NAME((參數(shù)表)) （說明部分） S return (表達(dá)式) end NAME

38、 函數(shù)的引用：x ← function（參數(shù)）；,2024/3/17,9) 變量的分類 a）根據(jù)數(shù)據(jù)類型分類 整型、實(shí)型、字符型等 b）根據(jù)作用域分類： 全程變量、局部變量、形式參數(shù) c）根據(jù)是否帶入、帶出數(shù)據(jù)值/結(jié)果分類： in型變量 out型變量 inout型變量

39、 邊界效應(yīng)：改變了參變量或全程變量的值 函數(shù)：通過函數(shù)值返回輸出結(jié)果，沒有邊界效應(yīng) 純過程：沒有函數(shù)值返回，只通過邊界效應(yīng)帶出輸出結(jié)果,2024/3/17,10) 特殊語句 a）exit 退出當(dāng)前一層的循環(huán) b）return 退出過程 return(表達(dá)式) : 函數(shù)返回

40、結(jié)果 c）goto 無條件轉(zhuǎn)向語句 goto label 11) 遞歸 a）直接遞歸：過程中包含對自身的調(diào)用 b）間接遞歸：間接調(diào)用自身12) 輸入輸出 read、print13）注釋 //注釋//,2024/3/17,1.4 基本數(shù)據(jù)結(jié)構(gòu),1. 棧和隊列線性表： n個元素的有序表棧和隊列：特殊的線性表利用動態(tài)數(shù)據(jù)結(jié)構(gòu)——鏈表實(shí)現(xiàn)?；蜿犃欣渺o

41、態(tài)數(shù)據(jù)結(jié)構(gòu)——數(shù)組實(shí)現(xiàn)?；蜿犃谢谝陨蟽煞N表示形式的棧和隊列上的基本運(yùn)算,2024/3/17,2. 樹 定義1.4 樹（tree）是一個或多個結(jié)點(diǎn)的有限集合，它使得：有一個指定為根（root）的結(jié)點(diǎn)剩余結(jié)點(diǎn)被劃分成m≥0個不相交的集合： T1，…，Tm 這些集合的每一個又都是一棵樹，并稱T1，…，Tm為根的子樹。,2024/3/17,關(guān)于樹的重要概念結(jié)點(diǎn)的度（degree）：一個結(jié)點(diǎn)的子樹數(shù)樹的度

42、：樹中結(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)森林：m≥0個不相交樹的集合。,2024/3/17,3 二元樹 定義1.5 二元樹（binary tree）是結(jié)點(diǎn)的有限集合，它或者為空，或者由一個根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。 二元

43、樹與度為2的樹的區(qū)別二元樹性質(zhì)： 引理1.1 一棵二元樹第 i級的最大結(jié)點(diǎn)數(shù)是2i-1。深度為k的二元樹的最大結(jié)點(diǎn)數(shù)為2k-1,k>0。,2024/3/17,2024/3/17,特殊形態(tài)的二元樹 ① 滿二元樹：深度為k且有2k-1個結(jié)點(diǎn)的二元樹,,,,,,,,2024/3/17,② 完全二元樹：一棵有n個結(jié)點(diǎn)深度為k的二元樹，當(dāng)它的 結(jié)點(diǎn)相當(dāng)于深度為k的滿二元樹

44、中編號為1到 n的結(jié)點(diǎn)時，稱該二元樹是完全的。 完全二元樹的葉子結(jié)點(diǎn)至多出現(xiàn)在相鄰的兩級上。 完全二元樹的結(jié)點(diǎn)可以緊湊地存放在一個一維數(shù)組中（性質(zhì)見引理1.2）。,2024/3/17,③ 堆：堆是一棵完全二元樹，它的每個結(jié)點(diǎn)的值至少和 該結(jié)點(diǎn)的兒子們（如果存在的話）的值一樣大 （ max-堆）（或小， min-堆）。?、堋《謾z索樹：二分檢索

45、樹Ｔ是一棵二元樹，它或者為空， 或者每個結(jié)點(diǎn)含有一個可以比較大小的數(shù)據(jù)元素，且 有：　　　·Ｔ的左子樹的所有元素比根結(jié)點(diǎn)中的元素??；　　　·Ｔ的右子樹的所有元素比根結(jié)點(diǎn)中的元素大；　　　·Ｔ的左子樹和右子樹也是二分檢索樹。　　注：二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異,2024/3/17,3. 圖,圖Ｇ由稱之為結(jié)點(diǎn)Ｖ和邊Ｅ的兩個集合組成，記為

46、 G=（V，E） 其中，Ｖ是一個有限非空的結(jié)點(diǎn)集合；Ｅ是結(jié)點(diǎn)對偶的集合，Ｅ的每一對偶表示Ｇ的一條邊。,2024/3/17,有關(guān)圖的的重要概念,無向圖：邊表示為（ｉ，ｊ）有向圖：邊表示為〈ｉ，ｊ〉成本：帶有成本的圖稱為網(wǎng)絡(luò)（帶權(quán)圖）鄰接結(jié)點(diǎn)的度（出度／入度）路徑：由結(jié)點(diǎn)vp到vq的一條路（path）是結(jié)點(diǎn) vp ， vi1 ， vi2 ， … ， vim ， vq的一個

47、序列，它使得 ( vp ， vi1 ) ，( vi1 ，vi2 ) ， … ，( vim ， vq ) 是E（G）的邊。路的長度：組成路的邊數(shù)。,2024/3/17,簡單路徑：除了第一和最后一個結(jié)點(diǎn)可以相同以外，其它 所有結(jié)點(diǎn)都不同。環(huán)：第一個和最后一個結(jié)點(diǎn)相同的簡單路。連通圖：在無向圖中，如果每對結(jié)點(diǎn)之間都存在一條路徑，則

48、 稱該圖是連通的。子圖：是由G的結(jié)點(diǎn)集V的子集（記為VB）和邊集E中連接VB 中結(jié)點(diǎn)的邊的子集所組成的圖。連通分圖：一個圖的最大連通子圖。有向圖的強(qiáng)連通性：在有向圖中，如果對于每一對結(jié)點(diǎn)i和j， 既存在一條從i到j(luò)的路，又存在一條從j

49、 到i的路，則稱該有向圖是強(qiáng)連通的。,2024/3/17,圖的表示方法,鄰接矩陣 鄰接表,2024/3/17,1.5 遞歸和消去遞歸,1. 遞歸 遞歸是一種強(qiáng)有力的設(shè)計方法 遞歸的效率問題,2024/3/17,例1.3 斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 +

50、Fi-2 （i>1)算法1.7 求斐波那契數(shù) procedure F(n) //返回第n個斐波那契數(shù)// integer n if n<= 1 then return(1) else return(F(n-1) + F(n-2)) end if

51、 end F算法效率：對F(n-1) 、F(n-2)存在大量的重復(fù)計算改 進(jìn)：保存中間結(jié)果,2024/3/17,例1.4 歐幾里得算法 已知兩個非負(fù)整數(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ù) procedure GCD(a,

52、b) // 約定a>b // if b=0 then 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;,2024/3/17,例1.5 用遞歸策略設(shè)計的檢索算法 已

53、知元素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 :i>n: return(0) :A(i) =

54、 x; return(i) :else: return(SEARCH(i+1)) endcase end SEARCH,2024/3/17,2. 消去遞歸,直接遞歸的消去規(guī)則： 基本思路：將遞歸調(diào)用的地方用等價的非遞歸代碼來代替，并對return語句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用和return語句，將之轉(zhuǎn)換成等價的迭代代碼。 初始化 ⑴ 在過程的開

55、始部分，插入說明為棧的代碼并將其初始化為空。在一般情況下，這個棧用來存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 ⑵ 將標(biāo)號L1附于第一條可執(zhí)行語句。然后對于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來代替。,2024/3/17,處理遞歸調(diào)用語句 ⑶ 將所有參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個全程變量來看待。 ⑷ 建立第i個新標(biāo)號Li，并將i存入棧。這個標(biāo)號的i值將用來計算返回地址。

56、此標(biāo)號放在規(guī)則⑺所描述的程序段中。 ⑸ 計算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 ⑹ 插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分： goto L1,2024/3/17,對退出一層遞歸調(diào)用后的處理 ⑺ 如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將⑷中建立的

57、標(biāo)號附于這條語句上。 如果此過程不是函數(shù)，則將⑷中建立的標(biāo)號附于⑹所產(chǎn)生的轉(zhuǎn)移語句后面的那條語句。 以上步驟消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return語句進(jìn)行處理。 （純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）,2024/3/17,對每個有return語句的地方，執(zhí)行下述規(guī)則： ⑻ 如果棧為空，則執(zhí)行正常返回。 ⑼ 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)，out/ i

58、nout型）的當(dāng)前值賦給棧頂上的那些對應(yīng)的變量。 ⑽ 如果棧中有返回地址標(biāo)號的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個下標(biāo)賦給一個未使用的變量。 ⑾ 從棧中退出所有局部變量和參數(shù)的值并吧它們賦給對應(yīng)的變量。 ⑿ 如果這個過程是函數(shù)，則插入以下指令，這些指令用來計算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 ⒀ 用返回地址標(biāo)號的下標(biāo)實(shí)現(xiàn)對該標(biāo)號的轉(zhuǎn)向。,2024/3/17,例1.6 遞歸調(diào)用示例

59、 求數(shù)組元素中的最大值算法1.10 求取數(shù)組元素的最大值（遞歸算法） procedure MAX1(i) // 查找數(shù)組A中最大值元素，并返回該元素的最大下標(biāo)。// global integer n,A(1:n),j,k integer i if i A(j) then k←i else k←j

60、endif else k←n endif return(k) //遞歸調(diào)用的返回// end MAX1,2024/3/17,消去上例中的遞歸算法1.11 使用上述的規(guī)則消去例1.10中的遞歸代碼 procedure MAX2(i) local integer j,k; global integer n

61、, A(1:n) integer I integer STACK(1:2*n) top←0 //規(guī)則1，聲明棧的代碼，并初始化為空// L1: if i<n //規(guī)則2，將標(biāo)號L1賦于第一條可執(zhí)行語句前// then top ←top + 1; STACK(top)←i; // 規(guī)則3，參數(shù)或局

62、 部變量的值入棧// top ←top +1; STACK(top)←2; // 規(guī)則4，建立新 標(biāo)號2，并入棧/

63、/,2024/3/17,i ←i+1 // 規(guī)則5， 計算參數(shù)值// goto L1 //規(guī)則6， 無條件轉(zhuǎn)向算法的開始部分// L2: j ←STACK(top); top ←top-1; // 規(guī)則7， 處理函數(shù)調(diào)用，

64、 并將標(biāo)號2賦于該語句上// if A(i) > A(j) then k ←I else k ←j endif else k ←n endif,2024/3/17,if top = 0 then return(k) // 規(guī)則8， 如果棧空，則正常返回// else addr ←STACK(top

65、);top ←top-1; // 規(guī)則10， 從 棧中退出返回標(biāo)號// i ←STACK(top);top ←top-1; // 規(guī)則11， 從棧中退

66、 出局部變量和參數(shù)的值// top ←top+1;STACK(top) ←k; // 規(guī)則12， 計算返 回值