Unit03遞歸算法RecursiveAlgorithm一般而言，兔子在出生兩個月后，就擁有了繁殖能力，一對兔子每個月能生出一對小兔子。如果所有兔子都不死，那么一年以后這對兔子及其后代一共有多少呢？我們的任務(wù)就是設(shè)計算法求解這一問題。①理解和使用線性表、順序表、鏈表和棧等。②認(rèn)識、理解和運用遞歸算法解決問題。③運用大O表示法分析遞歸算法的時間復(fù)雜度棧（Stack）棧是限定只能在一端進(jìn)行插入和刪除的線性表，也稱為“后進(jìn)先出”（LastInFirstOut，LIFO）表，允許插入和刪除的一端稱為棧頂（Top），不允許插入和刪除的一端稱為棧底（Bottom）。向棧中存入數(shù)據(jù)元素稱為進(jìn)棧（Push），或者稱為入棧、壓棧；從棧中取出數(shù)據(jù)元素稱為出棧（Pop），或者稱為彈棧。不含任何數(shù)據(jù)元素的棧稱為空棧（EmptyStack）。圖中所示，棧中有2個數(shù)據(jù)元素，插入1個A3（進(jìn)棧）后順序是A1、A2，A3；出棧時，只能從棧頂依次取出，也即出棧的次序是A3、A2、A1。棧的順序存儲結(jié)構(gòu)——順序棧（SequentialStack）順序棧是指利用順序存儲結(jié)構(gòu)實現(xiàn)的棧。采用地址連續(xù)的存儲空間（數(shù)組）依次存儲棧中數(shù)據(jù)元素，通常將棧底位置設(shè)置在數(shù)組空間的起始處，用一個整型變量top來記錄隨進(jìn)棧和出棧操作而變化的棧頂位置。圖中所示，當(dāng)top=-1時，棧空；當(dāng)top=5，等于定義的最大值時，棧滿。例題03-01建立數(shù)據(jù)元素關(guān)鍵字序列為{24，35，16，73，82，95，46，57}的順序棧。然后按照以下操作：關(guān)鍵字為88的數(shù)據(jù)元素進(jìn)棧；出棧；取出棧頂元素，求此時棧長度；最后清空棧，求此時棧長度。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)——鏈棧（Chainstack）棧中數(shù)據(jù)元素獨立存儲，依靠指針鏈接建立其邏輯次序，這種方式稱為棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，采用這種存儲結(jié)構(gòu)的棧稱為鏈棧。鏈棧通常采用單鏈表表示，其結(jié)構(gòu)特點與單鏈表的節(jié)點結(jié)構(gòu)相同。以單鏈表的頭部做棧頂，鏈棧頭節(jié)點的指針域指向棧頂節(jié)點，若值為空，則是空棧，鏈棧沒有棧滿的問題。鏈棧的進(jìn)、出棧示意圖例題03-02建立數(shù)據(jù)元素關(guān)鍵字序列為{24，35，16，73，82，95，46，57}的鏈棧。然后按照以下操作：關(guān)鍵字為88的數(shù)據(jù)元素進(jìn)棧；出棧；再取出棧頂元素，求此時棧長度；最后清空棧，求此時棧長度。遞歸算法（RecursiveAlgorithm）遞歸算法是通過重復(fù)將問題分解為同類的子問題而解決問題的方法。遞歸方法用于解決很多的計算機(jī)科學(xué)問題，因此它是計算機(jī)科學(xué)中十分重要的一個概念。絕大多數(shù)編程語言支持函數(shù)的自我調(diào)用來進(jìn)行遞歸。使用遞歸解決問題，思路清晰，代碼少。但是在主流高級語言中（如C語言、Pascal語言等），使用遞歸算法要耗用更多的?？臻g，所以在堆棧尺寸受限制時（如嵌入式系統(tǒng)、內(nèi)核態(tài)編程等），應(yīng)避免采用。所有的遞歸算法都可以改寫成與之等價的非遞歸算法。遞歸算法的關(guān)鍵：將規(guī)模較大的問題分解為一個或多個規(guī)模更小、但具有類似于原問題特性的子問題。即較大的問題遞歸地用較小的問題來描述，解原問題的方法同樣可以解這些子問題，也稱為遞歸條件（RecursiveCase）。確定一個或多個無須分解、可直接求解的最小問題。即遞歸調(diào)用的終結(jié)條件，避免形成無限循環(huán)，也稱為基線條件（BaseCase）。例題03-03非負(fù)整數(shù)n的階乘可遞歸定義如下：

在式中，當(dāng)n=0時，fact(0)=1，即基線條件；當(dāng)n>0時，fact(n)可以分解為n乘以fact(n-1)，而fact(n-1)還可以繼續(xù)分解為n-1乘以fact(n-2)，持續(xù)分解下去直到滿足基線條件為止，即遞歸條件。試用遞歸算法編程求5的階乘。5的階乘遞歸調(diào)用棧示意圖分治策略（DivideandConquer，D&C）遞歸算法采用了把一個復(fù)雜的算法問題按一定的“分解”方法分為等價的規(guī)模較小的若干部分，然后逐個解決，分別找出各部分的解，把各部分的解組成整個問題的解。設(shè)計思想：將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。其策略：對于一個規(guī)模為n的問題，若該問題可以容易地解決（如規(guī)模n較小）則直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫作分治策略，或者叫作分治法（分治術(shù)）。使用分而治之解決問題的關(guān)鍵:找出基線條件，這個條件必須足夠簡單。不斷把原問題分成兩個或多個更小的問題（或縮小問題的規(guī)模），直到符合基線條件,也即找出遞歸條件。把各小問題的解組合起來，即可得到原問題的解。漢諾塔（TowerofHanoi）問題是一個古老的益智游戲。有三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64個黃金圓盤。請把圓盤按大小順序重新擺放在另一根柱子上，并且規(guī)定：（1）在三根柱子之間一次只能移動一個圓盤；（2）擺放過程中小圓盤上不能放大圓盤。算法分析（以3個圓盤為例）設(shè)要移動的圓盤為n個，盤片由小到大依次從①開始編號，A、B、C分別代表三根柱子。按照一次只能移動一個圓盤且小圓盤不能放在大圓盤上的規(guī)定，將n個圓盤從A柱搬運到C柱上，B柱作為輔助。漢諾塔搬運拆解過程如下圖中所示move(A,3,C)hanoi(1,A,B,C)move(A,2,B)hanoi(1,C,A,B)hanoi(1,B,C,A)move(B,2,C)hanoi(1,A,B,C)hanoi(2,A,C,B)hanoi(2,B,A,C)move(A,1,C)move(A,2,B)move(C,1,B)move(B,1,A)move(B,2,C)move(A,1,C)move(A,3,C)hanoi(3,A,B,C)通過分析，不難得出以下結(jié)論：把n個圓盤從A柱搬運到C柱上，B柱作為輔助的遞歸方法如下：（1）當(dāng)n=1時，直接將n號盤從出發(fā)柱移動至目標(biāo)柱即可。（基線條件）（2）當(dāng)n>1時，n個圓盤搬運過程可以拆解為以下3部分。（遞歸條件）將小于n號圓盤的n-1個盤子從A柱搬運至B柱，C柱輔助。將編號為n的盤子從A柱移至C柱。將B柱上的n-1個盤子從B柱搬運至C柱，A柱輔助。1、根據(jù)任務(wù)要求和算法分析設(shè)計程序；2、編碼、調(diào)試、運行；3、做好記錄；4、總結(jié)。遞歸指的是調(diào)用自己的函數(shù)。每一個遞歸函數(shù)都有兩個條件：基線條件和遞歸條件。棧有兩種操作：壓入和彈出。所有的函數(shù)調(diào)用都進(jìn)入調(diào)用棧。調(diào)用?？赡芎荛L，這將占用大量的內(nèi)存。單元數(shù)據(jù)結(jié)構(gòu)算法講解實操01線性表順序表數(shù)組順序查找二分查找二分查找02順序表數(shù)組鏈表簡單選擇排序簡單選擇排序03線性表順序表鏈表棧遞歸算法遞歸算法04線性表順序表數(shù)組鏈表快速排序快速排序05線性表順序表數(shù)組鏈表散列表散列表查找算法散列表查找06順序表鏈表數(shù)組串堆

BF算法KMP算法KMP算法07順序表鏈表數(shù)組樹二叉樹哈夫曼樹建立哈夫曼編碼哈夫曼編碼0