算法設(shè)計(jì)與分析遞歸

算法設(shè)計(jì)與分析遞歸第一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三第3章遞歸遞歸調(diào)用的內(nèi)部實(shí)現(xiàn)原理遞歸程序的閱讀遞歸轉(zhuǎn)非遞歸遞歸算法的設(shè)計(jì)解遞歸方程第二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三遞歸的定義

在定義一個(gè)過(guò)程或函數(shù)時(shí)出現(xiàn)調(diào)用本過(guò)程或本函數(shù)的成分,稱之為遞歸。若調(diào)用自身,稱之為直接遞歸。若過(guò)程或函數(shù)p調(diào)用過(guò)程或函數(shù)q,而q又調(diào)用p,稱之為間接遞歸。第三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三3.1遞歸調(diào)用的內(nèi)部實(shí)現(xiàn)原理圖3.1子程序調(diào)用的幾種形式第四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三(1)兩次值傳送方式按指定類型為變參設(shè)置相應(yīng)的存儲(chǔ)空間，在執(zhí)行調(diào)用時(shí)，將實(shí)參值傳送給變參，在返回時(shí)將變參的值回傳實(shí)參。(2)地址傳送方式在內(nèi)部將變參設(shè)置成一個(gè)地址，調(diào)用時(shí)首先執(zhí)行地址傳送，將實(shí)參的地址傳送給變參，在子程序執(zhí)行過(guò)程中，對(duì)變參的操作實(shí)際上變成所對(duì)應(yīng)的實(shí)參的操作。值的回傳第五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三①在執(zhí)行調(diào)用時(shí)，系統(tǒng)至少執(zhí)行如下操作：a.返回地址進(jìn)棧，同時(shí)在棧頂為被調(diào)子程序的局部變量開(kāi)辟空間；b.為被調(diào)子程序準(zhǔn)備數(shù)據(jù)：計(jì)算實(shí)參值，并賦給對(duì)應(yīng)的棧頂?shù)男螀?；c.將指令流轉(zhuǎn)入被調(diào)子程序的入口處；②在執(zhí)行返回操作時(shí)，系統(tǒng)至少執(zhí)行如下操作：a.若有變參或是函數(shù)，將其值保存到回傳變量中；b.從棧頂取出返回地址；c.按返回地址返回；d.若有變參或是函數(shù)，從回傳變量中取出保存的值傳送給相應(yīng)的變量或位置上。子程序調(diào)用的內(nèi)部實(shí)現(xiàn)第六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三3.2.1模擬系統(tǒng)棧方式例3.1求m，n(m>n)的最大公因子的遞歸過(guò)程。procedureGCD(m，n∶int；varh∶int)begin1∶ifn=02∶thenbeginh←m；write(h)；end3∶elsecallGCD(n，mmodn，h)；4∶endp；3.2遞歸程序的閱讀第七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三callGCD(28，6，X)執(zhí)行過(guò)程第八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三指令流方式GCD(100，18，x)執(zhí)行write(x)的運(yùn)行過(guò)程，指令流方式第九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三指令流方式例3.3對(duì)下面的遞歸過(guò)程，寫(xiě)出調(diào)用P(3)的運(yùn)行結(jié)果。procedureP(w∶int)；beginifw>0thenbegincallP(w-1)；

write(w)；

callP(w-1)；end；endp；第十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三遞歸算法的程序設(shè)計(jì)存在兩個(gè)問(wèn)題：①并不是所有語(yǔ)言都支持遞歸；②遞歸程序比非遞歸程序要花費(fèi)更多的時(shí)間，當(dāng)遞歸層數(shù)太多時(shí)，會(huì)出現(xiàn)棧溢出。3.3遞歸轉(zhuǎn)非遞歸第十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三①系統(tǒng)自動(dòng)地為遞歸設(shè)置了一個(gè)棧，因此，在等價(jià)的非遞歸程序中，需要設(shè)置棧S，初始為空②調(diào)用的c操作是將程序的執(zhí)行流程轉(zhuǎn)入到子程序的入口處，所以等價(jià)程序中，用無(wú)條件的轉(zhuǎn)移語(yǔ)句實(shí)現(xiàn)，并在入口處設(shè)置一個(gè)標(biāo)號(hào)L0。③對(duì)程序中的每個(gè)遞歸調(diào)用，用以下幾個(gè)等價(jià)操作替換：a.保留現(xiàn)場(chǎng)：開(kāi)辟棧頂存儲(chǔ)空間，用于保存返回地址(不妨用Li，i=1，2，…)和調(diào)用層的形參和局部變量的值(最外層調(diào)用不必考慮)；遞歸轉(zhuǎn)非遞歸方法第十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三b.準(zhǔn)備數(shù)據(jù)：為被調(diào)子程序準(zhǔn)備數(shù)據(jù)，計(jì)算實(shí)參值，并賦給對(duì)應(yīng)的形參；c.執(zhí)行g(shù)otoL0；d.在返回處設(shè)一個(gè)標(biāo)號(hào)Li(i=1，2，3，…)，并根據(jù)需要設(shè)置以下語(yǔ)句：若有變參或是函數(shù)，從回傳變量中取出所保存的值，并傳送到相應(yīng)的實(shí)參或位置。④對(duì)返回語(yǔ)句，如果棧不空，則依次執(zhí)行如下操作，否則結(jié)束本子程序，返回。a.回傳數(shù)據(jù)：若有變參或是函數(shù)，將其值保存到回傳變量中；b.恢復(fù)現(xiàn)場(chǎng)：從棧頂取出返址(不妨設(shè)保存到X中)及各變量、形參的值，并退棧；c.返回，執(zhí)行g(shù)otoX；d.對(duì)其中的非遞歸調(diào)用和返回操作可照搬。第十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.4將下面的遞歸程序轉(zhuǎn)化成等價(jià)的非遞歸程序。procedureP(w∶int)；beginifw>0thenbegincallP(w-1)；

write(w)；

end；endp；第十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三解按轉(zhuǎn)化規(guī)則可得

procedureP1(w∶int)；

begininit(S)；l0∶ifw>0thenbeginpush(S，w，l1)；

ww-1gotol0；l1∶write(w)；

end；

ifnotempty(S)thenbeginpop(S，w，X)；

gotoX；

end；

endp；簡(jiǎn)化規(guī)則1如果遞歸程序中只有一次遞歸調(diào)用，則在轉(zhuǎn)換時(shí)，返回地址不入棧。第十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三

圖3.4例3.4的流程圖第十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三procedureP1(w∶int)；begininit(S)；

whilew>0dobeginpush(S，w)；

ww-1；end；whilenotempty(S)dobeginpop(S，w)；

write(w)；

end；endp；修改后的程序第十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.5將下面遞歸程序改為等價(jià)的非遞歸程序。procedureP(w∶int)；beginifw>0thenbeginwrite(w)；

callP(w-1)；end；endp；第十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三procedureP1(w∶int)；begininit(S)；l0∶ifw>0thenbeginwrite(w)；

push(S，w)；

ww-1；

gotol0；l1∶end；

ifnotempty(s)thenbeginpop(S，w)；

gotol1；

end；endp；簡(jiǎn)化規(guī)則2在尾遞歸調(diào)用時(shí)，不必執(zhí)行入棧操作。注意：如果有變參或是函數(shù)，則在返回后還要執(zhí)行賦值操作，所以不能算尾遞歸。第十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三圖3.5例3.5流程圖第二十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三procedureP1(w∶int)；beginl0∶ifw>0thenbeginwrite(w);ww-1;gotol0end;endp;修改后的程序第二十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.6將例3.1轉(zhuǎn)換成等價(jià)的非遞歸程序。

procedureGCD(m,n∶int;varh∶int);vartemp,backvar∶int;begininit(S);l0∶ifn=0thenbeginhm;write(h);endelsebeginpush(S,m,n,h);tempm;mn;ntempmodn;gotol0;l1∶hbackvar;end;ifnotempty(S)thenbeginbackvarh;pop(S,m,n,h);gotol1;end;endp;第二十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三圖3.6例3.6的流程圖第二十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三procedureGCD(m,n∶int;varh∶int);vartemp,backvar∶int;begininit(S);whilen≠0dobeginpush(S,m,n,h);tempm;mn;ntempmodn;end;

hm;write(h);whilenotempty(S)dobeginbackvarh;pop(S,m,n,h);hbackvar;end;endp;修改后的程序第二十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三適宜于用遞歸算法求解的問(wèn)題的充分必要條件是：①問(wèn)題P的描述涉及規(guī)模，即P(size)；②規(guī)模發(fā)生變化后，問(wèn)題的性質(zhì)不發(fā)生變③問(wèn)題的解決有出口。

表現(xiàn)形式procedureP(參數(shù)表)；beginif遞歸出口

then簡(jiǎn)單操作elsebegin簡(jiǎn)單操作；callP;簡(jiǎn)單操作end;endp;3.4遞歸算法的設(shè)計(jì)第二十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.7簡(jiǎn)單的0/1背包問(wèn)題。設(shè)一背包可容物品的最大質(zhì)量為m，現(xiàn)有n個(gè)物品，質(zhì)量為(w1,w2,…,wn)，wi均為正整數(shù)，從n件物品中挑選若干件，使放入背包的質(zhì)量之和正好為m。第二十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三第二十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.9棋子移動(dòng)。有2n

個(gè)棋子(n≥4)排成一行，白子用0代表，黑子用1代表，n=5的初始狀態(tài)為：0000011111__(右邊至少有兩個(gè)空位)移動(dòng)規(guī)則是每次必須同時(shí)移動(dòng)相鄰兩個(gè)棋子，顏色不限，移動(dòng)方向不限，每次移動(dòng)必須跳過(guò)若干棋子，不能調(diào)換兩個(gè)棋子的位置，最后成為：0101010101第二十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三下面用不完全歸納法找出口和遞推關(guān)系。n=400001111__

第一步000__11101(4,5)(9,10)第二步0001011__1(8,9)(4,5)第三步0__1011001(2,3)(8,9)第四步010101__01(7,8)(2,3)第五步__01010101(1,2)(7,8)第二十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三n=50000011111__第一步0000__111101(5,6)(11,12)第二步00001111__01(9,10)(5,6)這時(shí)前8枚棋子是n=4的情況，移法如n=4的第一步到第五步即可完成n=5時(shí)的移子。n=6000000111111__第一步00000__1111101(6,7)(13,14)第二步0000011111__01(11,12)(6,7)前10枚棋子為n=5的情況。第三十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三由此歸納出：n=4時(shí)是遞歸的出口，在退出時(shí)作5個(gè)移動(dòng)操作：move(4,5)(9,10)move(8,9)(4,5)move(2,3)(8,9)move(7,8)(2,3)move(1,2)(7,8)如果2n個(gè)棋子的移動(dòng)用chess(n)表示，則遞推關(guān)系是：Move(n,n+1)(2n+1,2n+2);move(2n-1,2n)(n,n+1);callchess(n-1);第三十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三第三十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.10求n個(gè)元素的全排列。分析：n=1輸出：a1;n=2輸出：a1a2a2a1;n=3輸出：

a1a2a3a1a3a2a2a1a3a2a3a1a3a1a2a3a1a2第三十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三分析n=3，全部排列分成三類：①a1類：a1之后跟a2

，a3的所有全排列。②a2類：a2之后跟a1

，a3的所有全排列。③a3類：a3之后跟a2，a1的所有全排列。將①中a1

，a2的互換位置，得到②；將①中a1

，a3的互換位置，得到③。它說(shuō)明可以用循環(huán)的方式重復(fù)執(zhí)行交換位置，后面跟隨剩余序列的所有排列，對(duì)剩余序列再使用這個(gè)方法，這就是遞歸調(diào)用，當(dāng)后跟的元素沒(méi)有時(shí)就得到遞歸的邊界。第三十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三第三十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例3.11自然數(shù)拆分。任何一個(gè)大于1的自然數(shù)n，總可以拆分成若干個(gè)小于n

的自然數(shù)之和，試求n

的所有拆分。第三十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三n=2可拆分成2=1+1n=3可拆分成3=1+2=1+1+1n=4可拆分成4=1+3=1+1+2=1+1+1+1=2+2……第三十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三

n=7可拆分成7=1+6=1+1+5=1+1+1+4=1+1+1+1+3=1+1+1+1+1+2=1+1+1+1+1+1+1=1+1+1+2+2=1+1+2+3=1+2+4=1+2+2+2=1+3+3=2+5=2+2+3=3+4第三十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三第三十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三遞推法公式解法解遞歸方程40第四十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三對(duì)于某些遞歸關(guān)系，可以通過(guò)逐次遞推求得遞歸方程的解。例1.4Hanoi塔問(wèn)題1.3.1遞推法41第四十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Hanoi塔問(wèn)題的遞歸算法的時(shí)間復(fù)雜性，由下面遞歸方程給出：42第四十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三所以，Hanoi塔問(wèn)題的遞歸算法的時(shí)間復(fù)雜性為T(n)=O(2n)。將3個(gè)盤子從A座移到C座需要移7次，如果將64個(gè)盤子從A座移到C座需要移多少時(shí)間？需要移18446744073709551615次，假設(shè)和尚每次移動(dòng)1個(gè)盤子用1秒鐘，則移動(dòng)8446744073709551615次需要18446744073709551615秒，大約相當(dāng)于6×10e11年，即大約600億年，所以有人戲稱，當(dāng)老和尚移完64個(gè)盤子之時(shí)，“世界末日”也到了。

43第四十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1.5第6章介紹分治法。這里舉一個(gè)分治法的例子。設(shè)n表示問(wèn)題的尺寸，n/b表示將這個(gè)問(wèn)題分成a個(gè)子問(wèn)題后，每個(gè)子問(wèn)題的尺寸，其中a，b為常數(shù)。d(n)表示在分解或合成子問(wèn)題而得到整個(gè)問(wèn)題解決時(shí)的時(shí)間耗費(fèi)。則整個(gè)問(wèn)題的時(shí)間耗費(fèi)由下面遞歸方程給出，求解遞歸方程。44第四十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Master定理

45第四十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1

例2例346第四十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三1.常系數(shù)線性齊次遞推方程的求解標(biāo)準(zhǔn)形式：k階求解步驟：（1）求出特征方程的k個(gè)根（2）如果沒(méi)有重根，則該遞推方程的通解為

如果有重根，如果q是e重特征根，通解對(duì)應(yīng)于根q的部分為整個(gè)通解為各個(gè)不等的特征根的對(duì)應(yīng)部分之和（3）代入初值確定待定常數(shù)。47第四十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例6Fibonacci數(shù)列

解：x2-x-1=0的根為

，遞推方程的通解為

帶入初值得

解得

48第四十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例7H(n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4)=0H(0)=1,H(1)=0,H(2)=1,H(3)=2特征方程x4+x3-3x2-5x-2=0,特征根-1，-1，-1，2，通解為

解得解為

49第四十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三

常系數(shù)線性非齊次遞推方程求解標(biāo)準(zhǔn)形

通解為對(duì)應(yīng)的齊次通解加上特解

特解的函數(shù)形式依賴于f(n)求解的關(guān)鍵是用待定系數(shù)法確定一個(gè)特解H*(n）50第五十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三f(n)為n的t次多項(xiàng)式，一般H*(n)也為n的t次多項(xiàng)式例1求an+5an-1+6an-2=3n2

的通解設(shè)an*=P1n2+P2n+P3,代入得

P1n2+P2n+P3+5[P1(n-1)2+P2(n-1)+P3]+6[P1(n-2)2+P2(n-2)+P3]=3n2從而得到方程組

12P1=3-34P1+12P2=029P1

–17P2+12P3=0

通解為51第五十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例2Hanoi塔

H(n)=2H(n-1)+1設(shè)H*(n)=PP=2P+1,P=-1H(n)=A2n

–1代入初值

H(1)=1得A=1解為H(n)=2n

–152第五十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三f(n)為指數(shù)函數(shù)n，特解也為指數(shù)形式若不是特征根，則特解為H*(n)=Pn

若是e重特征根，則特解為Pnen

例3H(n)+5H(n-1)+6H(n-2)=424n令H*(n)=P4n,代入得

P4n+5P4n-1+6P4n-2=424n

42P=4216,P=16通解為H(n)=C1(-2)n+C2(-3)n+4n+2

53第五十三頁(yè)，共五十八頁(yè)，編輯