算法分析與設(shè)計(jì)第一二三章4(遞歸和消去遞歸)

1、第一章 數(shù)學(xué)預(yù)備知識(shí) 第二章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)第三章 遞歸算法武漢科技大學(xué)理學(xué)院信息與計(jì)算科學(xué)系楊 波cookie_2008年9月2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 遞歸遞歸是一種強(qiáng)有力的設(shè)計(jì)方法遞歸的效率問(wèn)題遞歸的實(shí)現(xiàn)機(jī)制執(zhí)行調(diào)用時(shí)將返回地址進(jìn)棧為遞歸子程序準(zhǔn)備數(shù)據(jù)：實(shí)參形參值將指令流轉(zhuǎn)入新一級(jí)子程序入口處2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 執(zhí)行返回時(shí)保存中間計(jì)算結(jié)果數(shù)據(jù)從棧頂取出返回地址值按返回地址返回若有變參或函數(shù)，進(jìn)行參數(shù)或函數(shù)回傳遞歸的滿足要求問(wèn)題P的描述涉及到規(guī)模規(guī)模發(fā)生變化時(shí)，問(wèn)題的性質(zhì)不發(fā)生變化問(wèn)題的解決有出口，即遞歸有結(jié)束的條件200

2、8-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 遞歸的表現(xiàn)int P(參數(shù)表) if (遞歸出口) 簡(jiǎn)單操作 else 簡(jiǎn)單操作; P; 簡(jiǎn)單操作; 初始情況遞歸部分2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 階乘函數(shù)階乘函數(shù)定義為：public int Factorial(int n) if(n=0) return 1; return n*Factorial(n-1); 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 斐波那契（Fibonacci）數(shù)列 無(wú)窮數(shù)列1,1,2,3,5,8,13,稱為Fibonacci數(shù)列，遞歸定義為： public int F(int n)

3、 if(n=1) return 1; return F(n-1)+F(n-2);時(shí)間復(fù)雜度：指數(shù)階F(5)= F(4) + F(3) = (F(3) + F(2) + (F(2) + F(1) = (F(2) + F(1) + (F(1) + F(0) + (F(1) + F(0) +1) = (F(1) + F(0) + 1) + (1 +1) +(1 + 1) +1) 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 歐幾里德算法求最大公因子算法定義為： public static int GCD(int a,int b) if(b=0) /遞歸結(jié)束條件 return a; retu

4、rn GCD(b,a%b); /遞歸執(zhí)行部分GCD(22,8)=GCD(8,22%8)=GCD(8,6)=GCD(6,8%6)=GCD(6,2)=GCD(2,6%2)=GCD(2,0)=22008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 已知元素x，判斷x是否在a1:n中 public static void main(String argv) int x; int a; a=new int5; for(int i=1;in) return 0; else if(aj=x) return j; else return Search(j+1,x,a); 2008-09-01版權(quán)所有：楊波，

5、武漢科技大學(xué)理學(xué)院 整數(shù)劃分問(wèn)題將正整數(shù)n表示成一系列正整數(shù)之和，n=n1+n2+nk，其中n1n2nk1，k1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。正整數(shù)n的不同劃分個(gè)數(shù)稱為正整數(shù)n的劃分?jǐn)?shù)，記作p(n)。 例如：正整數(shù)6有如下11中不同的劃分，所以p(6)=11。6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 在正整數(shù)n的所有不同的劃分中，將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。 q(n,1)=

6、1, n11q(n,m)=q(n,n), mn q(n,n)=1+q(n,n-1) q(n,m)=q(n,m-1)+q(n-m,m), nm1 當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即 1+1+1+1最大數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成 正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1m-1的劃分組成 6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 pu

7、blic static int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q(n,n); if(n=m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 消去遞歸直接遞歸消去規(guī)則（包括兩方面）將遞歸過(guò)程中出現(xiàn)遞歸的地方，用等價(jià)的非遞歸代碼來(lái)代替（后面將給出的規(guī)則1-7）對(duì)return語(yǔ)句做適當(dāng)處理（后面將給出的規(guī)則8-13）2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 消去規(guī)則消去

8、遞歸調(diào)用過(guò)程的開(kāi)始部分，插入說(shuō)明為棧的代碼并將其初始化為空。（在一般情況下，棧用來(lái)存放參數(shù)、局部變量、函數(shù)的值，和每次遞歸調(diào)用的返回地址。） 將標(biāo)號(hào)Li附于第一條可執(zhí)行語(yǔ)句。然后，對(duì)于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來(lái)代替。 將所有參數(shù)和局部變量的值存入棧。棧頂指針可作為一個(gè)全局變量來(lái)看待。 建立第i個(gè)新標(biāo)號(hào)Li，并將i存入棧。這個(gè)標(biāo)號(hào)的i值將用來(lái)計(jì)算返回地址。此標(biāo)號(hào)放在規(guī)則7所描述的程序段中。 計(jì)算本次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并將這些值賦給相應(yīng)的形式參數(shù)。 插入一條無(wú)條件轉(zhuǎn)向語(yǔ)句轉(zhuǎn)向過(guò)程的開(kāi)始部分。 如果這過(guò)程是函數(shù)，則對(duì)遞歸過(guò)程中含有此次函數(shù)調(diào)用的那條語(yǔ)句作如下處理：

9、將該語(yǔ)句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來(lái)代替，其余部分的代碼按原描述方法照抄，并將4中建立的標(biāo)號(hào)附于這條語(yǔ)句上。如果此過(guò)程不是函數(shù)，則將4建立的標(biāo)號(hào)附于6所產(chǎn)生的轉(zhuǎn)移語(yǔ)句后面的那條語(yǔ)句。 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 對(duì)return語(yǔ)句的處理如果棧為空，則執(zhí)行正常返回。 否則，將所有輸出參數(shù)的當(dāng)前值賦給棧頂上的那些對(duì)應(yīng)的變量。 棧中有返回地址標(biāo)號(hào)的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個(gè)下標(biāo)賦給一個(gè)未使用的變量。 從棧中退出所有局部變量和參數(shù)的值并把它們賦給對(duì)應(yīng)的變量。 如果這個(gè)過(guò)程是函數(shù)，則插入以下指令，這些指令用來(lái)計(jì)算緊接在return后面的

10、表達(dá)式并將結(jié)果值存入棧頂。 用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 求數(shù)組中的最大元素A1:n2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 int Max1(int i) int j,k; if(iaj) k=i; else k=j; else k=a.length-1; return k;public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數(shù)組a中存放了待查詢的元素 stack=new int2*n+1; /規(guī)則1 to

11、p=0; /規(guī)則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規(guī)則8 else /規(guī)則9 addr=stacktop;top=top-1; /規(guī)則10 i=stacktop;top=top-1; /規(guī)則11 top=top+1;stacktop=k; /規(guī)則12 if(addr=2) go to L2 /規(guī)則13 規(guī)則1：過(guò)程的開(kāi)始部分，插入說(shuō)明為棧的代碼并將其初始化為空。（在一般情況下，棧用來(lái)存放參數(shù)、局部變量、函數(shù)的值，和每次遞歸調(diào)用的返回地址。）規(guī)則2：將標(biāo)號(hào)Li附于第一條可執(zhí)行語(yǔ)句。然后，對(duì)于每一處遞歸調(diào)用都用一組

12、執(zhí)行下列規(guī)則的指令來(lái)代替。規(guī)則3：將所有參數(shù)和局部變量的值存入棧。棧頂指針可作為一個(gè)全局變量來(lái)看待。 規(guī)則4：建立第i個(gè)新標(biāo)號(hào)Li，并將i存入棧。這個(gè)標(biāo)號(hào)的i值將用來(lái)計(jì)算返回地址。此標(biāo)號(hào)放在規(guī)則7所描述的程序段中。 規(guī)則5：計(jì)算本次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并將這些值賦給相應(yīng)的形式參數(shù)。 規(guī)則6：插入一條無(wú)條件轉(zhuǎn)向語(yǔ)句轉(zhuǎn)向過(guò)程的開(kāi)始部分。 規(guī)則7：如果這過(guò)程是函數(shù)，則對(duì)遞歸過(guò)程中含有此次函數(shù)調(diào)用的那條語(yǔ)句作如下處理：將該語(yǔ)句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來(lái)代替，其余部分的代碼按原描述方法照抄，并將4中建立的標(biāo)號(hào)附于這條語(yǔ)句上。如果此過(guò)程不是函數(shù)，則將4建立的標(biāo)號(hào)附于6

13、所產(chǎn)生的轉(zhuǎn)移語(yǔ)句后面的那條語(yǔ)句。 規(guī)則8：如果棧為空，則執(zhí)行正常返回。 規(guī)則10：棧中有返回地址標(biāo)號(hào)的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個(gè)下標(biāo)賦給一個(gè)未使用的變量。 規(guī)則11：從棧中退出所有局部變量和參數(shù)的值并把它們賦給對(duì)應(yīng)的變量。 規(guī)則12：如果這個(gè)過(guò)程是函數(shù)，則插入以下指令，這些指令用來(lái)計(jì)算緊接在return后面的表達(dá)式并將結(jié)果值存入棧頂。 規(guī)則13：用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。 規(guī)則9：否則，將所有輸出參數(shù)的當(dāng)前值賦給棧頂上對(duì)應(yīng)的那些變量2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 012345678910public int Max2(int i) /

14、java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數(shù)組a中存放了待查詢的元素 stack=new int2*n+1; /規(guī)則1 top=0; /規(guī)則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規(guī)則8 else addr=stacktop;top=top-1; /規(guī)則10 i=stacktop;top=top-1; /規(guī)則11 top=top+1;stacktop=k; /規(guī)則12 if(addr=2) go to L2 /規(guī)則13 例：求數(shù)組a1:5中最大元素

15、的算法，a1=3，a2=10，a3=8，a4=9，a5=412223224k=5addr=2i=45j=5k=4i=34j=4i=24k=2i=12j=22008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 改進(jìn)1上述算法只是為了說(shuō)明一般方法。 對(duì)于棧的處理實(shí)際上可以采用結(jié)構(gòu)體或類的方式實(shí)現(xiàn)，上述stack中分別存放了參數(shù)值或者函數(shù)返回值和每次函數(shù)調(diào)用的返回地址（實(shí)際為標(biāo)號(hào)的下標(biāo)，在此均為2）?？梢允褂枚S數(shù)組來(lái)實(shí)現(xiàn)堆棧。 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n

16、,top; n=a.length()-1; /數(shù)組a中存放了待查詢的元素 stack=new intn+12; /規(guī)則1 top=0; /規(guī)則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規(guī)則8 else addr=stacktop1; /規(guī)則10 i=stacktop0; /規(guī)則11 stacktop0=k; /規(guī)則12 if(addr=2) go to L2 /規(guī)則13 public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()

17、-1; /數(shù)組a中存放了待查詢的元素 stack=new int2*n+1; /規(guī)則1 top=0; /規(guī)則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規(guī)則8 else addr=stacktop;top=top-1; /規(guī)則10 i=stacktop;top=top-1; /規(guī)則11 top=top+1;stacktop=k; /規(guī)則12 if(addr=2) go to L2 /規(guī)則13 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 改進(jìn)2由于過(guò)程只返回一個(gè)地方，所以不必重復(fù)存放返回地址。也不需要轉(zhuǎn)向語(yǔ)句。

18、 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數(shù)組a中存放了待查詢的元素 stack=new intn+1; top=0; while(iaj) k=i; else k=j; return k; public int Max2(int i) /java偽代碼 int stack; int j,k,addr,n,top; n=a.length()-1; /數(shù)組a中存放了待查詢的元素 stack=new int2*n+1; /規(guī)則1 top=0; /規(guī)則1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /規(guī)則8 else addr=stacktop;top=top-1; /規(guī)則10 i=stacktop;to