NOI導(dǎo)刊-基礎(chǔ)算法課件

枚舉、遞推與遞歸枚舉、遞推與遞歸1第一部分枚舉策略第一部分枚舉策略2枚舉枚舉：是對一個(gè)問題找出所有的可行狀態(tài)，然后從中找出最優(yōu)的狀態(tài)。枚舉的不足：當(dāng)枚舉的狀態(tài)很多時(shí)，所用的時(shí)間會(huì)非常大，效率比較低。枚舉枚舉：是對一個(gè)問題找出所有的可行狀態(tài)，然后從中找出最優(yōu)的31、枚舉對象的確定2、枚舉方法的選取3、局部枚舉1、枚舉對象的確定4例題1圖像分析見文檔例題1圖像分析見文檔5例題2B_station在離著名的國家Berland不遠(yuǎn)的地方，有一個(gè)水下工作站。這個(gè)工作站有N層。已知：是第i層裝有Wi的水，最多可以容納Li的水，恐怖分子炸毀第i層的代價(jià)是Pi。第i層一旦被炸毀，該層所有的水都將傾瀉到第i+1層。如果某一層的水量超過了它的容量(即Li)，那么該層就將自動(dòng)被毀壞，所有的水也會(huì)傾瀉到下一層。Pivland的恐怖分子想要用最少的錢毀掉第N層，現(xiàn)在他雇傭你來計(jì)算，需要炸毀哪些層。

例題2B_station在離著名的國家Berland不遠(yuǎn)6輸入:第一行有一個(gè)自然數(shù)N(1<=n<=15000)。接下來的N行，每行3個(gè)整數(shù)Wi,Li,Pi(0<=Wi,Li,Pi<=15000)。輸出:輸出需要炸毀的層的編號(hào)。樣例Input樣例output311000100012010002210100

輸入:第一行有一個(gè)自然數(shù)N(1<=n<=15000)。接下來7分析令Si=W1+W2+…+Wi（特別的S0=0）。不妨設(shè)恐怖分子炸毀的第高層是第p層（第一層是最高層，第N層是最底層）。因?yàn)榭植婪肿拥哪繕?biāo)是毀滅第N層，所以水必須從第p層一直瀉下去。如果存在一個(gè)i，滿足Wp+Wp+1+…+Wi-1+Wi<=Li，也就是說前面幾層的水全部泄下來也無法把第i層自動(dòng)沖毀，那么就必須要使用炸藥把它炸開了。分析令Si=W1+W2+…+Wi（特別的S0=0）。8所以恐怖分子需要炸毀的層的集合就是Bomb[p]={p}∪{i|i>pSi-Sp-1<=Li}令Qi=Si-Li，那么：Bomb[p]={p}∪{i|i>pQi<=Sp-1}我們枚舉p，然后看哪些層需要炸毀。這樣就得到了一個(gè)O(n2)的算法。

所以恐怖分子需要炸毀的層的集合就是Bomb[p]={p}∪{9優(yōu)化注意到Sp是隨著p的增加而遞增的，觀察兩個(gè)集合：Bomb[p]={p}∪{i|i>pQi<=Sp-1}Bomb[p-1]={p-1}∪{i|i>p-1Qi<=Sp-2}因?yàn)镾p-2<=Sp-1，所以{i|i>p-1Qi<=Sp-2}包含于Bomb[p]，也就是說，Bomb[p-1]是在Bomb[p]的基礎(chǔ)上，通過以下操作得到的：刪除所有的i∈Bomb[p]，Qi>Sp-2。添加p-1。優(yōu)化注意到Sp是隨著p的增加而遞增的，觀察兩個(gè)集合：10針對這兩種操作，我們可以使用大根堆(Heap)。從大到小枚舉p，對于每一個(gè)p，執(zhí)行：Step1.如果堆的根i滿足Qi>Sp-2，那么刪除根；否則轉(zhuǎn)Step3。Step2.轉(zhuǎn)Step1。Step3.添加p-1。每層至多進(jìn)堆一次、出堆一次，所以總的時(shí)間復(fù)雜度是O(nlogn)。對于n<=15000的范圍完全能夠勝任了。

針對這兩種操作，我們可以使用大根堆(Heap)。從大到小枚11例題3：圖形周長給定N（<=5000）個(gè)矩形，每個(gè)矩形均垂直或水平放置，它們可以重疊。求最終被覆蓋部分的周長。例題3：圖形周長給定N（<=5000）個(gè)矩形，每個(gè)矩形均垂直12例題3分析見文檔例題3分析見文檔13例題4數(shù)字游戲見文檔例題4數(shù)字游戲見文檔14例題5排列問題見文檔例題5排列問題見文檔15第二部分遞推策略第二部分遞推策略16例題1kod給定26個(gè)英文字母中的前k(<=19)個(gè)，由這k個(gè)結(jié)點(diǎn)組成二叉排序樹，將所有的二叉排序樹進(jìn)行先序遍歷，然后按字典序排序，輸出第n個(gè)序列。例題1kod給定26個(gè)英文字母中的前k(<=19)個(gè)，由這17分析見文檔分析見文檔18例題2開關(guān)問題見文檔例題2開關(guān)問題見文檔19例題3losttemple例題3losttemple20第三部分遞歸策略第三部分遞歸策略21遞歸的概念與基本思想一個(gè)函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。在程序設(shè)計(jì)中，過程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。遞歸的概念與基本思想一個(gè)函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其22遞歸的概念與基本思想遞歸過程是借助于一個(gè)遞歸工作棧來實(shí)現(xiàn)的問題向一極推進(jìn)，這一過程叫做遞推；而問題逐一解決，最后回到原問題，這一過程叫做回歸。遞歸的過程正是由遞推和回歸兩個(gè)過程組成。遞歸的概念與基本思想遞歸過程是借助于一個(gè)遞歸工作棧來實(shí)現(xiàn)的23遞歸的概念與基本思想用遞歸算法求n!定義：函數(shù)fact(n)=n! fact(n-1)=(n-1)! 則有 fact(n)=nfact(n-1) 已知 fact(1)=1遞歸的概念與基本思想用遞歸算法求n!2425下面畫出了調(diào)用和返回的遞歸示意圖25下面畫出了調(diào)用和返回的遞歸示意圖25遞歸的概念與基本思想遞歸實(shí)現(xiàn)的代價(jià)是巨大的棧空間的耗費(fèi)，那是因?yàn)檫^程每向前遞推一次，程序?qū)⒈緦拥膶?shí)在變量（值參和變參）、局部變量構(gòu)成一個(gè)“工作記錄”壓入工作棧的棧頂，只有退出該層遞歸時(shí)，才將這一工作記錄從棧頂彈出釋放部分空間。由此可以想到，減少每個(gè)“工作記錄”的大小便可節(jié)省部分空間。例如某些變參可以轉(zhuǎn)換為全局變量，某些值參可以省略以及過程內(nèi)部的精簡。遞歸的概念與基本思想遞歸實(shí)現(xiàn)的代價(jià)是巨大的?？臻g的耗26遞歸的概念與基本思想示例：求a[1..n]的最大者。有如下過程：Procedurefindmax(i:integer;varmax:integer);varj:integer;beginmax:=a[i];ifi=nthenexitelsebeginfindmax(i+1,j);ifj>maxthenmax:=j;end;end;

遞歸的概念與基本思想示例：求a[1..n]的最大者。27遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1,max),而像上述過程中的變參max完全可以省略。將上述方法修改可得下面的算法：Procedurefindmax(i:integer);beginifi=nthenexitelsebeginfindmax(i+1);ifa[i]>maxthenmax:=a[i];end;end;

遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1,ma28遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1)，max為全局變量，同時(shí)還減少了一個(gè)局部變量的使用。盡管這只是一個(gè)很簡單的例子，在本例中不做精簡，程序也還是能通過，但它精簡的原則對其它使用遞歸的程序而言卻是同樣適用的。特別是在遞歸過程出現(xiàn)堆棧溢出情況時(shí)就應(yīng)該考慮這一問題。遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1)，29遞歸的概念與基本思想采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計(jì)比非遞歸算法的設(shè)計(jì)往往要容易一些，所以當(dāng)問題本身是遞歸定義的，或者問題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問題的解決方法是遞歸形式的時(shí)候，往往采用遞歸算法來解決。遞歸的概念與基本思想采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清30遞歸的應(yīng)用解決搜索問題處理遞歸定義或解決方法為遞歸方式的問題實(shí)現(xiàn)分治思想用于輸出動(dòng)態(tài)規(guī)劃的中間過程遞歸的應(yīng)用解決搜索問題31遞歸的應(yīng)用（搜索樹）樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問題時(shí)，常?？梢圆捎眠f歸的方法。因?yàn)樗阉鳟a(chǎn)生的節(jié)點(diǎn)成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N后”問題，哈密頓回路，圖的可著色性等等。遞歸的應(yīng)用（搜索樹）樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有32遞歸的應(yīng)用例題：鋼板分割問題。設(shè)有一塊正方形的鋼板，現(xiàn)需將它分成n個(gè)小正方形。例如，當(dāng)：n=2不可能有解。n=3不可能有解。n=4 可分成4個(gè)小正方形鋼板。n=5不可能有解。n=6即一個(gè)大的加五個(gè)小的。n=7即三個(gè)較大的加四個(gè)小的。n=8 即一個(gè)大的加七個(gè)小的。問題為任給n，求出分成n個(gè)小正方形的方法。遞歸的應(yīng)用例題：鋼板分割問題。設(shè)有一塊正方形的鋼板，現(xiàn)需將它33遞歸的應(yīng)用【分析】經(jīng)過分析就可以得出：（1）按n=4的方法將1個(gè)小正方形分成4個(gè)，則增加了3個(gè)正方形。（2）以n=6為基礎(chǔ)，由（1）可以得出n=9，12，15，。（3）以n=7為基礎(chǔ)，由（1）可以得出n=10，13，16，。（4）以n=8為基礎(chǔ)，由（1）可以得出n=11，14，17，。由此可以得出如下的遞歸算法：遞歸的應(yīng)用【分析】經(jīng)過分析就可以得出：34遞歸的應(yīng)用proceduredevide(i:integer);Beginifn>8thenbegin分解成四小塊；對于其中一塊devide(n-3)endelsecasenof6:按n=6分割；7:按n=7分割；8:按n=8分割；end;End;遞歸的應(yīng)用proceduredevide(i:intege35遞歸的應(yīng)用（實(shí)現(xiàn)分治思想）不難發(fā)現(xiàn)，在各種時(shí)間復(fù)雜度為nlogn排序方法中，大都采用了遞歸的形式。因?yàn)闊o論是分治合并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸。其實(shí)進(jìn)行分治，也是一個(gè)建樹的過程。遞歸的應(yīng)用（實(shí)現(xiàn)分治思想）不難發(fā)現(xiàn)，在各種時(shí)間復(fù)雜度36遞歸的應(yīng)用（例題分析）例題2：剔除多余括號(hào)鍵盤輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所有多余括號(hào)，原表達(dá)式中所有變量和運(yùn)算符相對位置保持不變，并保持原表達(dá)式等價(jià)。分析： 首先考慮人處理這個(gè)問題的方法，就是依靠符號(hào)來判斷是否可以去括號(hào)。括號(hào)的前后，以及括號(hào)內(nèi)的符號(hào)，都需要考慮。因此，可以按照人的處理方法，從最外層處理起，一層一層的去掉括號(hào)，這便是分治的思想。而由于每次分治的處理過程基本相同，用遞歸最為合適。遞歸的應(yīng)用（例題分析）例題2：剔除多余括號(hào)37遞歸的應(yīng)用（例題分析）在遞歸過程中，對于正在處理的表達(dá)式s，如果s本身最外層就是多余括號(hào)，則去括號(hào)，并處理括號(hào)內(nèi)的表達(dá)式（遞歸調(diào)用）；否則，可沿該表達(dá)式中的最低級(jí)運(yùn)算符p，將其拆為兩個(gè)表達(dá)式，分別進(jìn)行處理（遞歸調(diào)用），并獲得左右兩表達(dá)式中的最低級(jí)運(yùn)算符c1,c2，通過與p的比較，確定是否應(yīng)添加括號(hào)。遞歸的終止條件為：s是變量。遞歸的應(yīng)用（例題分析）在遞歸過程中，對38遞歸的應(yīng)用（例題分析）例如，處理表達(dá)式‘((a+b)*f)-(i/j)’,過程如下：‘((a+b)*f)-(i/j)’,‘-’

‘((a+b)*f),’*’‘(i/j),’/’

‘(a+b)*f),’*’ ‘i/j’,’/’

‘(a+b)’,’+’ ‘f’,’‘‘i’,’‘ ‘j’,’‘

‘a(chǎn)+b’,’+’‘a(chǎn)’,’‘‘b’,’‘

最后得出結(jié)果：‘(a+b)*f-i/j’。遞歸的應(yīng)用（例題分析）例如，處理表達(dá)式‘((a+b)*f)-39遞歸的應(yīng)用（輸出動(dòng)態(tài)規(guī)劃的中間過程）動(dòng)態(tài)規(guī)劃對空間要求較高，若要保存中間過程用于輸出，則可能要增加一倍的空間需求。此時(shí)，如果采用遞歸輸出，就完全不需要浪費(fèi)這寶貴的空間。遞歸的應(yīng)用（輸出動(dòng)態(tài)規(guī)劃的中間過程）動(dòng)態(tài)規(guī)劃對空間要40例題：最佳航線問題你在加拿大航空公司組織的一次競賽中獲獎(jiǎng)，獎(jiǎng)品是一張免費(fèi)機(jī)票，可在加拿大旅行，從最西的一個(gè)城市出發(fā)，單方向從西向東經(jīng)若干城市到達(dá)最后一個(gè)城市（必須到達(dá)最東的城市），然后在單方向從東向西飛回起點(diǎn)（可途徑若干城市）。除起點(diǎn)城市外，任何城市只能訪問一次。起點(diǎn)城市被訪問兩次：出發(fā)一次，返回一次。除指定的航線外，不允許乘其他航線，也不允許使用其他交通工具。求解的問題是：給定城市表列及兩城市之間的直通航線，請找出一條旅行航線，在滿足上述限制條件下，使訪問的城市盡可能多。例題：最佳航線問題你在加拿大航空公司組41例題分析：最佳航線問題

對這一問題，我們采用了動(dòng)態(tài)規(guī)劃的方法。假設(shè)城市已按從西到東編號(hào)，數(shù)組dist[i,j]表示城市i到城市n,再到城市j的所有可行方案中，最多能夠訪問的城市數(shù)目。逆推關(guān)系式為：dist[n,n]=1;dist[i,j]=dist[j,i];dist[i,j]=max(dist[i,k])+1;(j<i,j<k<=n,且存在航線k─j)

如果要記錄中間過程，就必須再開辟一個(gè)二維數(shù)組，就會(huì)導(dǎo)致程序可完成的數(shù)據(jù)規(guī)模降低。而采用遞歸求出路徑后再輸出，編程并未增加多少難度，而可處理的數(shù)據(jù)量卻大大增加了。求路徑的過程完全按照倒推的方法，利用dist數(shù)組得出往返的路線。。例題分析：最佳航線問題 對這一問題，我們采用了動(dòng)態(tài)規(guī)劃的方法42枚舉、遞推與遞歸枚舉、遞推與遞歸43第一部分枚舉策略第一部分枚舉策略44枚舉枚舉：是對一個(gè)問題找出所有的可行狀態(tài)，然后從中找出最優(yōu)的狀態(tài)。枚舉的不足：當(dāng)枚舉的狀態(tài)很多時(shí)，所用的時(shí)間會(huì)非常大，效率比較低。枚舉枚舉：是對一個(gè)問題找出所有的可行狀態(tài)，然后從中找出最優(yōu)的451、枚舉對象的確定2、枚舉方法的選取3、局部枚舉1、枚舉對象的確定46例題1圖像分析見文檔例題1圖像分析見文檔47例題2B_station在離著名的國家Berland不遠(yuǎn)的地方，有一個(gè)水下工作站。這個(gè)工作站有N層。已知：是第i層裝有Wi的水，最多可以容納Li的水，恐怖分子炸毀第i層的代價(jià)是Pi。第i層一旦被炸毀，該層所有的水都將傾瀉到第i+1層。如果某一層的水量超過了它的容量(即Li)，那么該層就將自動(dòng)被毀壞，所有的水也會(huì)傾瀉到下一層。Pivland的恐怖分子想要用最少的錢毀掉第N層，現(xiàn)在他雇傭你來計(jì)算，需要炸毀哪些層。

例題2B_station在離著名的國家Berland不遠(yuǎn)48輸入:第一行有一個(gè)自然數(shù)N(1<=n<=15000)。接下來的N行，每行3個(gè)整數(shù)Wi,Li,Pi(0<=Wi,Li,Pi<=15000)。輸出:輸出需要炸毀的層的編號(hào)。樣例Input樣例output311000100012010002210100

輸入:第一行有一個(gè)自然數(shù)N(1<=n<=15000)。接下來49分析令Si=W1+W2+…+Wi（特別的S0=0）。不妨設(shè)恐怖分子炸毀的第高層是第p層（第一層是最高層，第N層是最底層）。因?yàn)榭植婪肿拥哪繕?biāo)是毀滅第N層，所以水必須從第p層一直瀉下去。如果存在一個(gè)i，滿足Wp+Wp+1+…+Wi-1+Wi<=Li，也就是說前面幾層的水全部泄下來也無法把第i層自動(dòng)沖毀，那么就必須要使用炸藥把它炸開了。分析令Si=W1+W2+…+Wi（特別的S0=0）。50所以恐怖分子需要炸毀的層的集合就是Bomb[p]={p}∪{i|i>pSi-Sp-1<=Li}令Qi=Si-Li，那么：Bomb[p]={p}∪{i|i>pQi<=Sp-1}我們枚舉p，然后看哪些層需要炸毀。這樣就得到了一個(gè)O(n2)的算法。

所以恐怖分子需要炸毀的層的集合就是Bomb[p]={p}∪{51優(yōu)化注意到Sp是隨著p的增加而遞增的，觀察兩個(gè)集合：Bomb[p]={p}∪{i|i>pQi<=Sp-1}Bomb[p-1]={p-1}∪{i|i>p-1Qi<=Sp-2}因?yàn)镾p-2<=Sp-1，所以{i|i>p-1Qi<=Sp-2}包含于Bomb[p]，也就是說，Bomb[p-1]是在Bomb[p]的基礎(chǔ)上，通過以下操作得到的：刪除所有的i∈Bomb[p]，Qi>Sp-2。添加p-1。優(yōu)化注意到Sp是隨著p的增加而遞增的，觀察兩個(gè)集合：52針對這兩種操作，我們可以使用大根堆(Heap)。從大到小枚舉p，對于每一個(gè)p，執(zhí)行：Step1.如果堆的根i滿足Qi>Sp-2，那么刪除根；否則轉(zhuǎn)Step3。Step2.轉(zhuǎn)Step1。Step3.添加p-1。每層至多進(jìn)堆一次、出堆一次，所以總的時(shí)間復(fù)雜度是O(nlogn)。對于n<=15000的范圍完全能夠勝任了。

針對這兩種操作，我們可以使用大根堆(Heap)。從大到小枚53例題3：圖形周長給定N（<=5000）個(gè)矩形，每個(gè)矩形均垂直或水平放置，它們可以重疊。求最終被覆蓋部分的周長。例題3：圖形周長給定N（<=5000）個(gè)矩形，每個(gè)矩形均垂直54例題3分析見文檔例題3分析見文檔55例題4數(shù)字游戲見文檔例題4數(shù)字游戲見文檔56例題5排列問題見文檔例題5排列問題見文檔57第二部分遞推策略第二部分遞推策略58例題1kod給定26個(gè)英文字母中的前k(<=19)個(gè)，由這k個(gè)結(jié)點(diǎn)組成二叉排序樹，將所有的二叉排序樹進(jìn)行先序遍歷，然后按字典序排序，輸出第n個(gè)序列。例題1kod給定26個(gè)英文字母中的前k(<=19)個(gè)，由這59分析見文檔分析見文檔60例題2開關(guān)問題見文檔例題2開關(guān)問題見文檔61例題3losttemple例題3losttemple62第三部分遞歸策略第三部分遞歸策略63遞歸的概念與基本思想一個(gè)函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。在程序設(shè)計(jì)中，過程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。遞歸的概念與基本思想一個(gè)函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其64遞歸的概念與基本思想遞歸過程是借助于一個(gè)遞歸工作棧來實(shí)現(xiàn)的問題向一極推進(jìn)，這一過程叫做遞推；而問題逐一解決，最后回到原問題，這一過程叫做回歸。遞歸的過程正是由遞推和回歸兩個(gè)過程組成。遞歸的概念與基本思想遞歸過程是借助于一個(gè)遞歸工作棧來實(shí)現(xiàn)的65遞歸的概念與基本思想用遞歸算法求n!定義：函數(shù)fact(n)=n! fact(n-1)=(n-1)! 則有 fact(n)=nfact(n-1) 已知 fact(1)=1遞歸的概念與基本思想用遞歸算法求n!6667下面畫出了調(diào)用和返回的遞歸示意圖25下面畫出了調(diào)用和返回的遞歸示意圖67遞歸的概念與基本思想遞歸實(shí)現(xiàn)的代價(jià)是巨大的?？臻g的耗費(fèi)，那是因?yàn)檫^程每向前遞推一次，程序?qū)⒈緦拥膶?shí)在變量（值參和變參）、局部變量構(gòu)成一個(gè)“工作記錄”壓入工作棧的棧頂，只有退出該層遞歸時(shí)，才將這一工作記錄從棧頂彈出釋放部分空間。由此可以想到，減少每個(gè)“工作記錄”的大小便可節(jié)省部分空間。例如某些變參可以轉(zhuǎn)換為全局變量，某些值參可以省略以及過程內(nèi)部的精簡。遞歸的概念與基本思想遞歸實(shí)現(xiàn)的代價(jià)是巨大的?？臻g的耗68遞歸的概念與基本思想示例：求a[1..n]的最大者。有如下過程：Procedurefindmax(i:integer;varmax:integer);varj:integer;beginmax:=a[i];ifi=nthenexitelsebeginfindmax(i+1,j);ifj>maxthenmax:=j;end;end;

遞歸的概念與基本思想示例：求a[1..n]的最大者。69遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1,max),而像上述過程中的變參max完全可以省略。將上述方法修改可得下面的算法：Procedurefindmax(i:integer);beginifi=nthenexitelsebeginfindmax(i+1);ifa[i]>maxthenmax:=a[i];end;end;

遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1,ma70遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1)，max為全局變量，同時(shí)還減少了一個(gè)局部變量的使用。盡管這只是一個(gè)很簡單的例子，在本例中不做精簡，程序也還是能通過，但它精簡的原則對其它使用遞歸的程序而言卻是同樣適用的。特別是在遞歸過程出現(xiàn)堆棧溢出情況時(shí)就應(yīng)該考慮這一問題。遞歸的概念與基本思想起始狀態(tài)就是調(diào)用findmax(1)，71遞歸的概念與基本思想采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計(jì)比非遞歸算法的設(shè)計(jì)往往要容易一些，所以當(dāng)問題本身是遞歸定義的，或者問題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問題的解決方法是遞歸形式的時(shí)候，往往采用遞歸算法來解決。遞歸的概念與基本思想采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清72遞歸的應(yīng)用解決搜索問題處理遞歸定義或解決方法為遞歸方式的問題實(shí)現(xiàn)分治思想用于輸出動(dòng)態(tài)規(guī)劃的中間過程遞歸的應(yīng)用解決搜索問題73遞歸的應(yīng)用（搜索樹）樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問題時(shí)，常?？梢圆捎眠f歸的方法。因?yàn)樗阉鳟a(chǎn)生的節(jié)點(diǎn)成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N后”問題，哈密頓回路，圖的可著色性等等。遞歸的應(yīng)用（搜索樹）樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有74遞歸的應(yīng)用例題：鋼板分割問題。設(shè)有一塊正方形的鋼板，現(xiàn)需將它分成n個(gè)小正方形。例如，當(dāng)：n=2不可能有解。n=3不可能有解。n=4 可分成4個(gè)小正方形鋼板。n=5不可能有解。n=6即一個(gè)大的加五個(gè)小的。n=7即三個(gè)較大的加四個(gè)小的。n=8 即一個(gè)大的加七個(gè)小的。問題為任給n，求出分成n個(gè)小正方形的方法。遞歸的應(yīng)用例題：鋼板分割問題。設(shè)有一塊正方形的鋼板，現(xiàn)需將它75遞歸的應(yīng)用【分析】經(jīng)過分析就可以得出：（1）按n=4的方法將1個(gè)小正方形分成4個(gè)，則增加了3個(gè)正方形。（2）以n=6為基礎(chǔ)，由（1）可以得出n=9，12，15，。（3）以n=7為基礎(chǔ)，由（1）可以得出n=10，13，16，。（4）以n=8為基礎(chǔ)，由（1）可以得出n=11，14，17，。由此可以得出如下的遞歸算法：遞歸的應(yīng)用【分析】經(jīng)過分析就可以得出：76遞歸的應(yīng)用proceduredevide(i:integer);Beginifn>8thenbegin分解成四小塊；對于其中一塊devide(n-3)endelsecasenof6:按n=6分割；7:按n=7分割；8:按n=8分割；end;End;遞歸的應(yīng)用proceduredevide(i:intege77遞歸的應(yīng)用（實(shí)現(xiàn)分治思想）不難發(fā)現(xiàn)，在各種時(shí)間復(fù)雜度為nlogn排序方法中，大都采用了遞歸的形式。因?yàn)闊o論是分治合并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸。其實(shí)進(jìn)行分治，也是一個(gè)建樹的過程。遞歸的應(yīng)用（實(shí)現(xiàn)分治思想）不難發(fā)現(xiàn)，在各種時(shí)間復(fù)雜度78遞歸的應(yīng)用（例題分析）例題2：剔除多余括號(hào)鍵盤輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所有多余括號(hào)，原表達(dá)式中所有變量和運(yùn)算符相對位置保持不變，并保持原表達(dá)式等價(jià)。分析： 首先考慮人處理這個(gè)問題的方法，就是依靠符號(hào)來判斷是否可以去括號(hào)。括號(hào)的前后，以及括號(hào)內(nèi)的符號(hào)，都需要考慮。因此，可以按照人的處理方法，從最外層處理起，一層一層的去掉括號(hào)，這便是分治的思想。而由于每次分治的處理過程基本相同，用遞歸最為合適。遞歸的應(yīng)用（例題分析）例題2：剔除多余括號(hào)79遞歸的應(yīng)用（例題分析）在遞歸過程中，對于正在處理的表達(dá)式s，如果s本身最外層就是多余括號(hào)，則去括號(hào)，并處理括號(hào)內(nèi)的表達(dá)式（遞歸調(diào)用）；否則，可沿該表達(dá)式中的最低級(jí)運(yùn)算符p，將其拆為兩個(gè)表達(dá)式，分別進(jìn)行處理（遞歸調(diào)用），并獲得左右兩表達(dá)式中的最低級(jí)運(yùn)算符c1,c2，通過與p的比較，確定是否應(yīng)添加括號(hào)。遞歸的終止條件為