算法與結構課件第二章遞歸(華北電力大學科技學院).ppt

《算法與結構課件第二章遞歸(華北電力大學科技學院).ppt》由會員分享，可在線閱讀，更多相關《算法與結構課件第二章遞歸(華北電力大學科技學院).ppt（58頁珍藏版）》請在裝配圖網(wǎng)上搜索。

計算機算法設計與分析,NorthChinaElectricPowerUniversity,ComputerAlgorithmsDesignreturnn*Factorial(n-1);},2遞歸算法的應用和實現(xiàn),如果問題的數(shù)據(jù)結構是遞歸的，問題的定義是遞歸的，問題的解法是遞歸的，可以考慮用遞歸算法。,看下面的數(shù)據(jù)結構：,,,,,Head,^,…,,,,Head,,,這是單鏈表，每個結點有兩個域：數(shù)據(jù)域和指針域。它是一種遞歸的結構，可定義為：1)一個結點，其指針域為null，是一個單鏈表；2)一個結點，其指針域為有效指針指向一個單鏈表，仍是一個單鏈表。,1)問題的數(shù)據(jù)結構是遞歸的,NorthChinaElectricPowerUniversity,若存在如上定義的一個單鏈表，現(xiàn)要實現(xiàn)打印最后一個結點的數(shù)據(jù)域的值，可用下面遞歸過程：,templateclasslink_list{Typedata;link_list*next;};templatevoidsearch1(link_list*h){if(h->next==null)coutdata;elsesearch1(h->next);},NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,二叉樹(BinaryTree)也是一種遞歸的數(shù)據(jù)結構，其遞歸定義為：1)它是一棵空樹；2)它是由一個根結點和兩棵分別稱為左右子樹的二叉樹構成。,要遍歷一棵二叉樹可以采用下面的遞歸算法：,voidTraverse(Bitptr*t){if(t!=null){coutdata;Traverse(t->lchild);Traverse(t->rchild);}},NorthChinaElectricPowerUniversity,例：Fibonacci數(shù)列無窮數(shù)列1,1,2,3,5,8,13,21,34,55,…,稱為Fibonacci數(shù)列。它可以遞歸地定義為：,Fib(n)=,,1n=0,1n=1,Fib(n-1)+Fib(n-2)n>1,第n個Fibonacci數(shù)可遞歸地計算如下：intFibonacci(intn){if(nm>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤m-1的劃分組成。以上的關系實際上給出了計算q(n,m)的遞歸式如下：,q(n,m)=,,1m=1,q(n,n)nm>1,0n<1或m<1,遞歸算法的設計方法,,遞歸算法既是一種有效的算法設計方法，也是一種有效的分析問題的方法。遞歸算法求解問題的基本思想是：對于一個較為復雜的問題，把原問題分解成若干個相對簡單且類同的子問題,這樣，原問題就可遞推得到解。適宜于用遞歸算法求解的問題的充分必要條件是：（1）問題具有某種可借用的類同自身的子問題描述的性質(zhì)；（2）某一有限步的子問題（也稱作本原問題）有直接的解存在。當一個問題存在上述兩個基本要素時，該問題的遞歸算法的設計方法是：（1）把對原問題的求解設計成包含有對子問題求解的形式。（2）設計遞歸出口。,,例設計模擬漢諾塔問題求解過程的算法。漢諾塔問題的描述是：設有3根標號為A，B，C的柱子，在A柱上放著n個盤子，每一個都比下面的略小一點，要求把A柱上的盤子全部移到C柱上，移動的規(guī)則是：（1）一次只能移動一個盤子；（2）移動過程中大盤子不能放在小盤子上面；（3）在移動過程中盤子可以放在A，B，C的任意一個柱子上。,問題分析：可以用遞歸方法求解n個盤子的漢諾塔問題。,,基本思想：1個盤子的漢諾塔問題可直接移動。n個盤子的漢諾塔問題可遞歸表示為，首先把上邊的n-1個盤子從A柱移到B柱，然后把最下邊的一個盤子從A柱移到C柱，最后把移到B柱的n-1個盤子再移到C柱。4個盤子漢諾塔問題的遞歸求解示意圖如圖6-4所示。,,圖6-4漢諾塔問題的遞歸求解示意圖,,,,,,,,,,,,,,,,,,,,,,,,,,Y,X,Z,以三個盤為例：,A,B,C,,算法設計：首先，盤子的個數(shù)n是必須的一個輸入?yún)?shù)，對n個盤子,我們可從上至下依次編號為1,2,…,n；其次，輸入?yún)?shù)還需有3個柱子的代號,我們令3個柱子的參數(shù)名分別為fromPeg，auxPeg和toPeg；最后，漢諾塔問題的求解是一個處理過程，因此算法的輸出是n個盤子從柱子fromPeg借助柱子auxPeg移動到柱子toPeg的移動步驟，我們設計每一步的移動為屏幕顯示如下形式的信息：MoveDiskifromPegXtoPegY這樣，漢諾塔問題的遞歸算法可設計如下：,voidtowers(intn,charfromPeg,chartoPeg,charauxPeg){if(n==1)//遞歸出口{printf("%s%c%s%c\n","movedisk1frompeg",fromPeg,"topeg",toPeg);return;}//把n-1個圓盤從fromPeg借助toPeg移至auxPegtowers(n-1,fromPeg,auxPeg,toPeg);//把圓盤n由fromPeg直接移至toPegprintf("%s%d%s%c%s%c\n","movedisk",n,"frompeg",fromPeg,"topeg",toPeg);//把n-1個圓盤從auxPeg借助fromPeg移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);},測試主函數(shù)如下：#includevoidmain(void){Towers(4,A,C,B);}程序運行的輸出信息如下：,MoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk3fromPegAtoPegBMoveDisk1fromPegCtoPegAMoveDisk2fromPegCtoPegBMoveDisk1fromPegAtoPegBMoveDisk4fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk2fromPegBtoPegAMoveDisk1fromPegCtoPegAMoveDisk3fromPegBtoPegCMoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegC,總結如下：遞歸算法的執(zhí)行過程是不斷地自調(diào)用，直到到達遞歸出口才結束自調(diào)用過程；到達遞歸出口后，遞歸算法開始按最后調(diào)用的過程最先返回的次序返回；返回到最外層的調(diào)用語句時遞歸算法執(zhí)行過程結束。,代碼,,遞歸過程的實現(xiàn),,對于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要保存以下兩類信息：（1）調(diào)用函數(shù)的返回地址；（2）調(diào)用函數(shù)的局部變量值。當執(zhí)行完被調(diào)用函數(shù)，返回調(diào)用函數(shù)前，系統(tǒng)首先要恢復調(diào)用函數(shù)的局部變量值，然后返回調(diào)用函數(shù)的返回地址。遞歸函數(shù)被調(diào)用時，系統(tǒng)要作的工作和非遞歸函數(shù)被調(diào)用時系統(tǒng)要作的工作在形式上類同，但保存信息的方法不同。,遞歸函數(shù)被調(diào)用時，系統(tǒng)的運行時棧也要保存上述兩類信息。每一層遞歸調(diào)用所需保存的信息構成運行時棧的一個工作記錄，在每進入下一層遞歸調(diào)用時，系統(tǒng)就建立一個新的工作記錄，并把這個工作記錄進棧成為運行時棧新的棧頂；每返回一層遞歸調(diào)用，就退棧一個工作記錄。因為棧頂?shù)墓ぷ饔涗洷囟ㄊ钱斍罢谶\行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動記錄。,設計舉例,一般遞歸算法設計舉例,例1設計一個輸出如下形式數(shù)值的遞歸算法。nnn...n......333221,問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問題的子問題，其參數(shù)為n-1。當參數(shù)減到0時不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當參數(shù)n≤0時空語句返回。算法設計：遞歸算法設計如下：voidDisplay(intn){inti;for(i=1;i0)Display(n-1);//遞歸//n<=0為遞歸出口，遞歸出口為空語句},代碼,例6-6設計求解委員會問題的算法。委員會問題是：從一個有n個人的團體中抽出k(k≤n)個人組成一個委員會，計算共有多少種構成方法。問題分析：從n個人中抽出k(k≤n)個人的問題是一個組合問題。把n個人固定位置后，從n個人中抽出k個人的問題可分解為兩部分之和：第一部分是第一個人包括在k個人中，第二部分是第一個人不包括在k個人中。對于第一部分，則問題簡化為從n-1個人中抽出k-1個人的問題；對于第二部分，則問題簡化為從n-1個人中抽出k個人的問題。圖6-7給出了n=5,k=2時問題的分解示意圖。,圖6-7委員會問題分解示意圖,當n=k或k=0時，該問題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會問題的遞推定義式為：,intComm(intn,intk){if(nn)return0;if(k==0)return1;if(n==k)return1;returnComm(n-1,k-1)+Comm(n-1,k);},例6-7求兩個正整數(shù)n和m最大公約數(shù)的遞推定義式為：,要求：（1）編寫求解該問題的遞歸算法；（2）分析當調(diào)用語句為Gcd(30,4)時算法的執(zhí)行過程和執(zhí)行結果；（3）分析當調(diào)用語句為Gcd(97,5)時算法的執(zhí)行過程和執(zhí)行結果；（4）編寫求解該問題的循環(huán)結構算法。,,解：（1）遞歸算法如下：intGcd(intn,intm){if(nn)returnGcd(m,n);elsereturnGcd(m,n%m);}（2）調(diào)用語句為Gcd(30,4)時，因m1,0n<1或m1),NorthChinaElectricPowerUniversity,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(2),Fib(1),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),將遞歸算法轉(zhuǎn)化成非遞歸算法的方法：,1)設計迭代算法：如果一個函數(shù)既有遞歸形式的定義又有非遞歸的迭代形式的定義，則可以用循環(huán)結構設計出迭代算法。一般說來，如果在一個函數(shù)或過程中只遞歸調(diào)用它一次，那么它的計算或執(zhí)行過程可以看成是線性變化的。,n!,,(n-1)!,,(n-2)!,,,,1!,,0!,,,從頂?shù)降走f歸,從底到頂返回,NorthChinaElectricPowerUniversity,intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}intFact2(intn){x=1;for(i=1;i<=n;i++)x=i*x;returnx;},以Fibnaocci數(shù)列為例，看非遞歸算法的轉(zhuǎn)化,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(1),Fib(2),Fib(1),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),Fib(0),,,,,,,,,,,,,,,Fib(5),Fib(4),Fib(3),Fib(2),Fib(0),Fib(1),NorthChinaElectricPowerUniversity,,intFib2(intn){if(n<2)return(n);else{inty=0;intx=1;intz;for(inti=2;i<=n;i++){z=y;y=x;x=z+y;}return(x);}},2)消除尾遞歸：遞歸調(diào)用是最后一步操作,可以用循環(huán)結構通過設置一些工作單元，把遞歸算法轉(zhuǎn)化為非遞歸算法。開始令工作單元等于外層的實際參數(shù)，以后隨著循環(huán)的執(zhí)行，不斷向里層變化，直到原遞歸調(diào)用的最里層的情況。循環(huán)結束后，執(zhí)行原屬于最里層的操作，而后整個算法結束。,NorthChinaElectricPowerUniversity,例:尋找單鏈表的最后一個結點并打印其數(shù)據(jù)域的值的過程search就是一個尾遞歸過程。,templateclasslink_list{Typedata;link_list*next;};voidsearch(h:link_list){if(h.next==null)cout<rchild)對應）。其中，①與②的連接沒問題。但②與③如何連接需要考慮。為了做③，必須“知道”XR的“根指針”即結點X的右指針t->rchild:可是X的左子樹XL上沒有這個指針。因此，應該在做②之前便將指針t->rchild保存起來;并當任務②完成之后“取出”該指針以便執(zhí)行任務③。在這以后，指針t->rchild就沒有保存價值了。對于先根遍歷來說，完成了任務③也就完成了對以X為根的整個子樹的遍歷，可以直接退回到X的父結點。,NorthChinaElectricPowerUniversity,根據(jù)以上分析，先根遍歷的非遞歸算法需引入任務棧以保存每個結點的右指針。這樣，非遞歸算法在二叉鏈表的任一結點X上的主要操作步驟可歸納如下：,①訪問結點X；②結點X的右指針進棧;③若XL不空，沿X的左指針遍歷XL；④從棧中取出X的右指針并將其退棧；⑤若XR不空，沿X右指針遍歷XR。,需要特別考慮的是，在二叉鏈表上，對任一結點X的任何操作都必須借助于指向它的指針的指引才能進行，而這一指針存在于X的父結點的某個指針域中。唯一的例外是根結點，指向它的指針是根指針。為了統(tǒng)一處理這兩種情況，可在算法的初始化中先將指針進棧，而在循環(huán)體的開頭做取棧頂操作。這樣，第一次從棧中取出的正是根指針；而以后棧中存儲（并取出）的是各個結點的右指針。,NorthChinaElectricPowerUniversity,綜合以上考慮，先根遍歷非遞歸算法的非形式描述如下：根指針進棧；while(棧不空){s=棧頂元素；退棧；while(s!=NULL)/*根或左、右子樹不空時繼續(xù)遍歷*/{visit(s);s->rchild進棧;/*保存右指針*/s=s->lchild;/*準備遍歷左子樹*/}},NorthChinaElectricPowerUniversity,voidpreorder1(bitreptrt)/*先根遍歷根結點為t的二叉樹*/{bitreptrstack[stacksize];/*工作棧*/inttop;top=0;stack[top]=t;/*根指針進棧*/while(top>=0){s=stack[top];/*讀棧頂元素到S中*/top--;/*退棧*/while(s!=NULL){visit(s);top++;stack[top]=s->rchild;/*右指針進棧保存*/s=s->lchild;/*修改s以便繼續(xù)遍歷左子樹*/}}},通過上面的例子可以看出，工作棧在消除遞歸中的基本作用是提供一種控制機構。在非遞歸算法執(zhí)行過程中的某些“關鍵”時刻，用棧頂元素來“引導”下一步操作的“走向”。為了達到這一目的，必須提前將這些有用的信息進棧保存。在上面的例子中，工作棧保存的是各個結點的右指針，這些指針也就是二叉樹上各結點的右子樹的根指針。顯然，這些根指針正是先根遍歷遞歸算法中包含的一些遞歸調(diào)用的實參；這些實參在非遞歸算法中若不及時保存就會丟失。因此，遞歸算法中的調(diào)用一返回控制被工作棧的作用所取代，從而將遞歸算法轉(zhuǎn)換成非遞歸算法。,NorthChinaElectricPowerUniversity,2.n!的非遞歸實現(xiàn),首先設定一個工作記錄棧S,其類型定義如下：#definemaxsize100structsqlStack{intElem[maxsize];inttop;}intFact1(intn){InitStack(S);PushStack(S,n);while(S.Elem[S.top]>1)PushStack(S,n-1);f=1;while(EmptyStack(S)!=True){f=f*S.Elem[S.top];PopStack(S);}},intFactorial(intn){if(n==0)return1;returnn*Factorial(n-1);},NorthChinaElectricPowerUniversity,4遞歸方程解的漸近階的求法,解遞歸方程：,T(n)=,,1若n=2,2T(n/2)+2若n>2,可以用疊代法來求解，設n=2k，且k為大于1的整數(shù)。,T(n)=2T(n/2)+2=2T(2k-1)+2=2(2T(2k-2)+2)+2=22T(k-2)+22+2=…=2k-1T(2k-(k-1))+2k-1+2k-2+…+22+2=2k-1T(2)+2k-2=2k-1+2k-2=(3/2)2k-2,代入n=2k，得T(n)=(3/2)n-2,NorthChinaElectricPowerUniversity,定理：設a,b,c是非負常數(shù)，n是c的整冪，則遞歸方程：,T(n)=,,b若n=1,aT(n/c)+bn若n>1,的解是,T(n)=,,O(n)若ac,證明：因為n是c的整冪，可得,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,5生成函數(shù),NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,例2求斐波那契數(shù)列的通項Fib(n)的解析表達式。解設{Fib(n)}的生成函數(shù)為G(x)=Fib(0)+Fib(1)x+Fib(2)x2++Fib(n)xn+1)xG(x)=Fib(0)x+Fib(1)x2+Fib(2)x3++Fib(n)xn+1+2)x2G(x)=Fib(0)x2+Fib(1)x3++Fib(n)xn+2+3)1)-2)-3)得：G(x)(1-x-x2)=Fib(0)+x(Fib(1)-Fib(0))+x2(Fib(2)-Fib(1)-Fib(0)+∵Fib(0)=1,Fib(1)=1∴G(x)(1-x-x2)=x,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,求一個遞歸式的非遞歸表示的一般步驟可概括為：1）設生成函數(shù)H(x)=h1x+h2x2++hnxn+使數(shù)列{hn}與要求解的遞歸式對應。2）解H(x)為一解析式H(x)=解析表達式3）重新展開H(x)H(x)=a1x+a2x2++anxn+4）求出H(x)展開式的通項H(x)=這里的an就是我們要的遞歸式的非遞歸表示。,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,6遞歸樹,結點形式,size:表示結點中T的實際參數(shù),nonrec.cost:表示結點的非遞歸耗費,結點擴展：確定一個不完全結點的子結點和非遞歸耗費域的過程。,結點的擴展方法：遞歸方程中所有含T的項成為它的子結點；2.剩余的項為該結點的非遞歸耗費域的值。,NorthChinaElectricPowerUniversity,T(n)=T(n/2)+T(n/2)+n,T(n/2)n/2,,T(n/2)n/2,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,,,,,,,,,,,,,,,,,,,,,,,對于遞歸樹的任意一棵子樹，滿足下面的關系：,sizefieldofroot=∑nonrec.Costsofexpandednodes,+∑sizefieldsofincompletenodes.,通過遞歸樹解遞歸方程的方法：,1.首先計算遞歸樹中同一層的所有結點的非遞歸耗費域之和；,2.再將剛才計算出的每一層的非遞歸耗費域之和求和。,T(n/2)n/2,,T(n/2)n/2,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,T(n/4)n/4,,,,,,,,,,,,,,,,,,,,,,,,n,n,n,n,,……,Θ(nlogn),NorthChinaElectricPowerUniversity,T(n-c)1,,T(n-c)1,,T(n-2c)1,,T(n-2c)1,,T(n-2c)1,,T(n-2c)1,,,,,,,,,,,,,,,,,,,,,,,,1,2,4,8,,……,Θ(2n/c),T(n)=2T(n-c)+1,NorthChinaElectricPowerUniversity,