NOIP基礎(chǔ)算法--枚舉、遞推和遞歸

1、NOIP基礎(chǔ)算法綜合n枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能狀態(tài)，并用問題給定的條件檢驗?zāi)男┦切枰模男┦遣恍枰?。能使命題成立，即為其解。n枚舉結(jié)構(gòu)：循環(huán)+判斷語句。 n 雖然枚舉法本質(zhì)上屬于搜索策略，但是它與后面講的回溯法有所不同。因為適用枚舉法求解的問題必須滿足兩個條件：n 可預(yù)先確定每個狀態(tài)的元素個數(shù)n；n 狀態(tài)元素a1，a2，an的可能值為一個連續(xù)的值域。n設(shè)ai1狀態(tài)元素ai的最小值；aik狀態(tài)元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aiaik，an1anankfor a1a11 to a1k do for a2a21 to a2k do

2、for aiai1 to aik do for anan1 to ank do if 狀態(tài)(a1，ai，an)滿足檢驗條件 then 輸出問題的解；枚舉法的優(yōu)點(diǎn)枚舉法的優(yōu)點(diǎn)n由于枚舉算法一般是現(xiàn)實(shí)生活中問題的“直譯”，因此比較直觀，易于理解；n由于枚舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。枚舉法的缺點(diǎn)枚舉法的缺點(diǎn)n枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個狀態(tài)枚舉的代價，因此效率比較低。四、枚舉法的優(yōu)缺點(diǎn)四、枚舉法的優(yōu)缺點(diǎn)n“直譯”枚舉：直接根據(jù)題意設(shè)定枚舉對象、范圍和約束條件。n 注意認(rèn)真審題，不要疏漏任何條件例題例題1：砝碼稱重：砝碼稱重(noi

3、p1996) 【問題描述問題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重=1000），求用這些砝碼能稱出不同的重量個數(shù)?！疚募斎胛募斎搿枯斎?g、2g、3g、5g、10g、20g的砝碼個數(shù)?！疚募敵鑫募敵觥枯敵瞿芊Q出不同重量的個數(shù)?！緲永斎霕永斎搿? 1 0 0 0 0【樣例輸出樣例輸出】3 【分析分析】根據(jù)輸入的砝碼信息，每種砝碼可用的最大個數(shù)是確定的，而且每種砝碼的個數(shù)是連續(xù)的，能取0到最大個數(shù)，所以符合枚舉法的兩個條件，可以使用枚舉法。枚舉時，重量可以由1g,2g,20g砝碼中的任何一個或者多個構(gòu)成，枚舉對象可以確定為6種重量的砝碼，范圍為每種砝碼的

4、個數(shù)。判定時，只需判斷這次得到的重量是新得到的，還是前一次已經(jīng)得到的，即判重。由于重量=1000g，所以，可以開一個a1001的數(shù)組來判重。readln(a,b,c,d,e,f)for c1:=0 to a do /1g砝碼的個數(shù)砝碼的個數(shù) for c2:=0 to b do /2g砝碼的個數(shù)砝碼的個數(shù) for c3:=0 to c do /3g砝碼的個數(shù)砝碼的個數(shù) for c4:=0 to d do /5g砝碼的個數(shù)砝碼的個數(shù) for c5:=0 to e do /10g砝碼的個數(shù)砝碼的個數(shù) for c6:=0 to f do /20g砝碼的個數(shù)砝碼的個數(shù) begin sum:=0; for

5、 i:=1 to 6 do sum:=sum+ci*wi; asum:=1; /標(biāo)記標(biāo)記 end;for i:=1 to 1000 do if ai=1 then inc(num); /統(tǒng)計不同重量的個數(shù)統(tǒng)計不同重量的個數(shù)Writeln(num);【問題描述】給你n根火柴棍，你可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：注意： 1. 加號與等號各自需要兩根火柴棍 2. 如果AB，則A+B=C與B+A=C視為不同的等式（A、B、C0） 3. n根火柴棍必須全部用上【輸入】輸入文件matches

6、.in共一行，又一個整數(shù)n（n24）?！据敵觥枯敵鑫募atches.out共一行，表示能拼成的不同等式的數(shù)目。 例題例題2：火柴棒等式（：火柴棒等式（NOIP2008）例題例題2：火柴棒等式（：火柴棒等式（NOIP2008） 【問題簡述問題簡述】給你n(n=A，滿足條件的A的最大取值為1111。所以枚舉A和B的范圍是從01111。n為了加快速度，可以將為了加快速度，可以將0到到2222的所有整數(shù)需的所有整數(shù)需要的火柴棒數(shù)目提前算好保存在數(shù)組中。要的火柴棒數(shù)目提前算好保存在數(shù)組中。五、枚舉算法的優(yōu)化枚舉算法的優(yōu)化 枚舉算法的時間復(fù)雜度：狀態(tài)總數(shù)*單個狀態(tài)的耗時。n 提取有效信息；n 減少重復(fù)計

7、算；n 將原問題化為更小的問題；n 根據(jù)問題的性質(zhì)進(jìn)行截枝；n 引進(jìn)其他算法【例題例題3】給你給你n(n=105)個整數(shù)，然后要有個整數(shù)，然后要有m (m=105)個詢問。每個詢問兩個整數(shù)個詢問。每個詢問兩個整數(shù)i和和j，問第，問第i個個數(shù)字到第數(shù)字到第j個數(shù)字所有數(shù)字之和。個數(shù)字所有數(shù)字之和?！緲闼厮惴闼厮惴ā?readln(n); for i:=1 to n do read(ai); for i:=1 to m do begin read(x,y); sum:=0; for j:=x to y do sum:=sum+aj; writeln(sum); end;時間復(fù)雜度為：時間復(fù)雜度為

8、：O(nm)【優(yōu)化算法優(yōu)化算法】先遞推計算出先遞推計算出si=si-1+ai，再回答詢問情況，再回答詢問情況; readln(n); for i:=1 to n do統(tǒng)計求和統(tǒng)計求和 begin read(ai); si:=si-1+ai; end; for i:=1 to m do begin read(x,y); writeln(sy-sx-1); end;【例題例題4】對于給定的對于給定的N*M的矩形，在其中找一個的矩形，在其中找一個R*C的權(quán)值最大的區(qū)域的權(quán)值最大的區(qū)域, 1=N,M=1,000?！舅惴ㄒ凰惴ㄒ弧浚阂悦恳粋€格子為左上角枚舉：以每一個格子為左上角枚舉R*C的區(qū)的區(qū)域，并求

9、出它的權(quán)值之和。最后取其中的最大值。域，并求出它的權(quán)值之和。最后取其中的最大值。此算法包含此算法包含4重循環(huán)。重循環(huán)。 時間復(fù)雜度：時間復(fù)雜度：O(N4) 【算法二算法二】：我們設(shè)：我們設(shè)Si,j表示以表示以(1,1)為左上角，為左上角，(i,j)為右為右下角區(qū)域的權(quán)值之和，那么我們以下角區(qū)域的權(quán)值之和，那么我們以(i,j)為右下角的為右下角的R*C區(qū)區(qū)域權(quán)值之和的計算公式為：域權(quán)值之和的計算公式為： Areai,j=Si,j+Si-R,j-C-Si-R,j-Si,j-C其中其中Si,j的計算公式為：的計算公式為： Si,j=valuei,j+Si-1,j+Si,j-1-Si-1,j-1 你可

10、以隨手畫圖出來，很容易即可證明上面兩個式你可以隨手畫圖出來，很容易即可證明上面兩個式子。最后取子。最后取Area 中的最大值即可。中的最大值即可。 時間復(fù)雜度：時間復(fù)雜度：O(N2) 【例題例題5】最大連續(xù)子序列的和最大連續(xù)子序列的和 【問題描述】給你一個有n(nmaxx then maxx:=sum; end;【算法算法2：優(yōu)化的枚舉：優(yōu)化的枚舉O(n2) s0:=0; for i:=1 to n do si:=si-1+ai;/初始化求和初始化求和 maxx:=a1; for i:=1 to n do for j:=i to n do if sj-si-1maxx then maxx:=s

11、j-si-1;時間復(fù)雜度：預(yù)處理+主程序=O(n+n2)=O(n2)，n=5000 【算法3】分治分治O(nlogn)、 最大連續(xù)子序列的位置有三種可能： 完全處于序列的左半； 完全處于序列的右半； 跨越序列中間； 【算法算法4】DPO(n) 1、階段和狀態(tài)、階段和狀態(tài)： 以第i個數(shù)結(jié)尾的最大連續(xù)子序列的和，只存在兩種選擇： 情形1：只包含ai 情形2：包含ai和以ai-1結(jié)尾的最大連續(xù)和序列 故設(shè)fi表示以ai結(jié)尾的最大連續(xù)子序列的和 2、狀態(tài)轉(zhuǎn)移方程：、狀態(tài)轉(zhuǎn)移方程： 轉(zhuǎn)移方程：fi=maxai,fi-1+ai(2=i=n) 初始化：f1=a1 Answer=maxfi|1=ibest t

12、hen best:=sum；/調(diào)整最優(yōu)解調(diào)整最優(yōu)解 end;n這個算法相當(dāng)粗糙，枚舉狀態(tài)的費(fèi)用為這個算法相當(dāng)粗糙，枚舉狀態(tài)的費(fèi)用為O(n6)(x1,y1)(x2,y2)2 2、從減少重復(fù)計算入手、從減少重復(fù)計算入手 n有剛才一維情況可以推廣到二維，在統(tǒng)計左上角為有剛才一維情況可以推廣到二維，在統(tǒng)計左上角為(x1,y1)右下角右下角為為(x2,y2)內(nèi)矩形的元素之和時，我們同樣可以先初始化，計算出左內(nèi)矩形的元素之和時，我們同樣可以先初始化，計算出左上角為上角為(1,1)，右下角為，右下角為(x,y)內(nèi)矩形的元素之和內(nèi)矩形的元素之和sxy。 for i:=1 to n do /枚舉矩形右下角，求和

13、枚舉矩形右下角，求和 for j:=1 to n do begin read(ai,j); si,j:=si-1,j+si,j-1-si-1,j-1+ai,j; end;n對于狀態(tài)左上角為對于狀態(tài)左上角為(x1,y1),右下角為右下角為(x2,y2)內(nèi)矩形的元素之和，可內(nèi)矩形的元素之和，可以改為：以改為： sum:=sx2,y2-sx1-1,y2-sx2,y1-1+sx1-1,y1-1; if sumbest then best:=sum； /調(diào)整最優(yōu)解調(diào)整最優(yōu)解n由于先進(jìn)行了由于先進(jìn)行了，整個算法的時間復(fù)雜度降為，整個算法的時間復(fù)雜度降為O(n4)3、提取恰當(dāng)?shù)男畔ⅰ⑻崛∏‘?dāng)?shù)男畔容易觀察

14、到，最大子矩陣問題是最大連續(xù)子序列和問題的提升，即將一條線換成一個面，將一維問題提升到二維問題。所以我們計算最大子矩陣的方法就是將一行行的數(shù)進(jìn)行累加以求得最大值。n但是還有一個問題，那就是應(yīng)該如何高效地存儲矩陣？n我們可以想到：在一個一維的數(shù)列中，設(shè)數(shù)組bi表示從第1個元素到第i個元素的和，則如果想要求第i個元素到第j個元素的和，只需要計算bj-bi-1的值就行了。由此推廣到二維矩陣，設(shè)bi,j表示矩陣第j列前i個元素的和，ai,j表示元素數(shù)據(jù)，則壓縮存儲： for i:=1 to n do for j:=1 to n do begin read(ai,j);bi,j:=bi-1,j+ai,j

15、;n因此，我們可以使用三重循環(huán)求出所有的矩形值，即枚舉起始行枚舉起始行i和終和終止行止行j，壓縮子矩形成為一行，變成一維求最大子段和問題，壓縮子矩形成為一行，變成一維求最大子段和問題。 即tk=max(tk-1,0)+bj,k-bi-1,k;n時間復(fù)雜度為O(n3)0 -2 -7 0 2 -6 2-4 1 -4 1-1 8 0 -20 -2 -7 0 0 -13 25 1 -17 34 9 -17 1核心代碼核心代碼 sum:=-99999999; /置初值置初值 for i:=1 to n do /階段階段:起始行起始行 begin for j:=i to n do /狀態(tài)狀態(tài):結(jié)束行結(jié)束行

16、 begin t1:=bj,1-bi-1,1; /初始化第初始化第1列的值列的值 for k:=2 to n do /決策決策:第幾列第幾列 begin if tk-10 then tk:=tk-1+bj,k-bi-1,k else tk:=bj,k-bi-1,k; if tksum then sum:=tk; end; end; end; writeln(sum);例題例題7：求第一、第二、第三最短路問題：求第一、第二、第三最短路問題n 重慶城里有重慶城里有n個車站，個車站，m條雙向公路連接其中的某些車站。條雙向公路連接其中的某些車站。每兩個車站最多用一條公路直接相連，從任何一個車站出每兩個

17、車站最多用一條公路直接相連，從任何一個車站出發(fā)都可以經(jīng)過一條或多條公路到達(dá)其他車站，但不同的路發(fā)都可以經(jīng)過一條或多條公路到達(dá)其他車站，但不同的路徑需要花費(fèi)的時間可能不同。在一條路上花費(fèi)的時間等于徑需要花費(fèi)的時間可能不同。在一條路上花費(fèi)的時間等于路徑上所有公路需要的時間之和。路徑上所有公路需要的時間之和。n 佳佳的家在車站佳佳的家在車站1，他有五個親戚，分別住在車站，他有五個親戚，分別住在車站a,b,c,d,e。過年了，他需要從自己的家出發(fā)，拜訪每個親戚（順序任過年了，他需要從自己的家出發(fā)，拜訪每個親戚（順序任意），給他們送去節(jié)日的祝福。怎樣走，才需要最少的時意），給他們送去節(jié)日的祝福。怎樣走，

18、才需要最少的時間？間？n 數(shù)據(jù)范圍：數(shù)據(jù)范圍：n(n=50,000),m(mn0時時,可以用等號可以用等號(或大于號、小于號或大于號、小于號)將將Hn與其前面的某些項與其前面的某些項Hi(0in)聯(lián)系起來，這樣的式聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。子就叫做遞推關(guān)系。如何建立遞推關(guān)系如何建立遞推關(guān)系遞推關(guān)系有何性質(zhì)遞推關(guān)系有何性質(zhì)如何求解遞推關(guān)系如何求解遞推關(guān)系 n 建立遞推關(guān)系式建立遞推關(guān)系式n 確定邊界條件確定邊界條件n 遞推求解遞推求解 n 一般遞推問題一般遞推問題n 組合計數(shù)類問題組合計數(shù)類問題n 一類博弈問題的求解一類博弈問題的求解n 動態(tài)規(guī)劃問題的遞推關(guān)系動態(tài)規(guī)劃問題的遞推關(guān)系例題

19、例題1：faibonacci數(shù)列數(shù)列 【問題描述問題描述】已知faibonacci數(shù)列的前幾個數(shù)分別為0，1，1，2，3，5，編程求出此數(shù)列的第n項。（n=60） 例題例題2：輸出楊輝三角的前：輸出楊輝三角的前N行行 【問題描述問題描述】輸出楊輝三角的前N行(N10)?！疚募斎胛募斎搿枯斎胫挥幸恍?，包括1個整數(shù)N(N2)個盤子時，我們可以利用下列步驟：n 第一步：先借助3柱把1柱上面的n-1個盤子移動到2柱上，所需的 移動次數(shù)為f(n-1)。n 第二步：然后再把1柱最下面的一個盤子移動到3柱上，只需要1 次盤子。n 第三步：再借助1柱把2柱上的n-1個盤子移動到3上，所需的移動 次數(shù)為f(

20、n-1)。n 由以上3步得出總共移動盤子的次數(shù)為：f(n-1)+1+ f(n-1)。n 所以：f(n)=2 f(n-1)+1 hn=2hn-1+1 =2n-1 邊界條件：h1=1【擴(kuò)展擴(kuò)展2】：四塔問題：四塔問題【問題分析問題分析】令令fi表示四個柱子時，把表示四個柱子時，把i個盤子從原柱移動到目標(biāo)柱所需的個盤子從原柱移動到目標(biāo)柱所需的最少移動次數(shù)。最少移動次數(shù)。 jn第一步：先把1柱上的前j個盤子移動到另外其中一個非目標(biāo)柱（2或3柱均可，假設(shè)移到2柱）上，此時3和4柱可以作為中間柱。移動次數(shù)為：fj。n第二步：再把原1柱上剩下的i-j個盤子在3根柱子（1、3、4）之間移動，最后移動到目標(biāo)柱4

21、上，因為此時2柱不能作為中間柱子使用，根據(jù)三柱問題可知，移動次數(shù)為：2(i-j)-1。n第三步：最后把非目標(biāo)柱2柱上的j個盤子移動到目標(biāo)柱上，次數(shù)為：fj。 in通過以上步驟我們可以初步得出：通過以上步驟我們可以初步得出： fi = 2*fj+2(i-j)-1nj可取的范圍是可取的范圍是1=ji，所以對于不同的，所以對于不同的j，得到的，得到的fi可能可能是不同的，本題要求最少的移動次數(shù)。是不同的，本題要求最少的移動次數(shù)。 fi=min2*fj+2(i-j)-1，其中1=ji【擴(kuò)展擴(kuò)展3】：m塔問題塔問題【問題分析問題分析】 設(shè)F(m,n)為m根柱子,n個盤子時移動的最少次數(shù)：n 1、先把1柱

22、上的前j個盤子移動到另外其中一個除m柱以外的非目標(biāo)柱上，移動次數(shù)為：fm, j； n 2、再把原1柱上剩下的n-j個盤子在m-1根柱子之間移動，最后移動到目標(biāo)柱m上，移動次數(shù)為：fm-1, n-j；n 3、最后把非目標(biāo)柱上的j個盤子移動到目標(biāo)柱沒柱上，移動次數(shù)為：fm, j。F(m,n)=min2*F(m,j)+F(m-1,n-j) (1=jn)j 例題例題4:數(shù)的計數(shù)數(shù)的計數(shù) 【問題描述】我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n)，先輸入一個自然數(shù)n(n1000)，然后對此自然數(shù)按照如下方法進(jìn)行處理： (1)、不作任何處理； (2)、在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原

23、數(shù)的一半； (3)、加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止； 方法方法1：用遞推用遞推n 用hn表示自然數(shù)n所能擴(kuò)展的數(shù)據(jù)個數(shù)，則： h1=1,h2=2,h3=2,h4=4,h5=4, h6=6,h7=6,h8=10,h9=10。n 分析上數(shù)據(jù)，可得遞推公式： hi=1+h1+h2+hi/2。n 時間復(fù)雜度O(n2)。 方法方法2：是對方法：是對方法1的改進(jìn)的改進(jìn)。我們定義數(shù)組s。 s(x)=h(1)+h(2)+h(x) =s(x-1)+h(x) =s(x-1)+s(x/2) h(x)=s(x)-s(x-1)=s(x/2) 此算法的時間復(fù)雜度可降到O(n)。方法方法3：還是用遞

24、推：還是用遞推。n只要做仔細(xì)分析，其實(shí)我們還可以得到以下的遞推公式： (1)當(dāng)i為奇數(shù)時,h(i)=h(i-1); (2) 當(dāng)i為偶數(shù)時,h(i)=h(i-1)+h(i/2);【思考思考】 1.若若n=10000怎么計算；怎么計算； 2.若若n=3000000怎么計算；怎么計算；n例題例題5：猴子吃桃問題：猴子吃桃問題1538n 【問題描述問題描述】猴子摘了一堆桃，第一天吃了一半，猴子摘了一堆桃，第一天吃了一半，還嫌不過癮，又吃了一個；第二天又吃了剩下的還嫌不過癮，又吃了一個；第二天又吃了剩下的一半零一個；以后每天如此。到第一半零一個；以后每天如此。到第n天，猴子一天，猴子一看只剩下一個了。問

25、最初有多少個桃子？看只剩下一個了。問最初有多少個桃子？ 【擴(kuò)展練習(xí)擴(kuò)展練習(xí)】猴子分桃猴子分桃 【問題描述問題描述】有一堆桃子和N只猴子，第一只猴子將桃子平均分成了M堆后，還剩了1個，它吃了剩下的一個，并拿走一堆。后面的猴子也和第1只進(jìn)行了同樣的做法，請問N只猴子進(jìn)行了同樣做法后這一堆桃子至少還剩了多少個桃子(假設(shè)剩下的每堆中至少有一個桃子)？而最初時的那堆桃子至少有多少個？ 【文件輸入文件輸入】輸入包含二個數(shù)據(jù)，數(shù)據(jù)間用空格隔開。第一個數(shù)據(jù)為猴子的只數(shù)N(1N10)，第二個數(shù)據(jù)為桃子分成的堆數(shù)M(2M7)。 【文件輸出文件輸出】輸出包含兩行數(shù)據(jù)，第一行數(shù)據(jù)為剩下的桃子數(shù)，第二行數(shù)據(jù)為原來的桃子

26、數(shù)。 【樣例輸入樣例輸入】3 2 【樣例輸出樣例輸出】 1 15【例題例題6】傳球游戲（傳球游戲（NOIP2008普及）普及）【問題描述問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。 游戲規(guī)則是這樣的：n（3=n=30）個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個球，當(dāng)老師吹哨子時開始傳球，每個同學(xué)可以把球傳給自己左右的兩個同學(xué)中的一個（左右任意），當(dāng)老師再吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學(xué)就是敗者，要給大家表演一個節(jié)目。 聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m（3=m2-3

27、-1和1-3-2-1，共兩種。 分析n 設(shè)fi,k表示經(jīng)過k次傳到編號為i的人手中的方案數(shù)，傳到i號同學(xué)的球只能來自于i的左邊一個同學(xué)和右邊一個同學(xué)，這兩個同學(xué)的編號分別是i-1和i+1，所以可以得到以下的遞推公式： fi,k=fi-1,k-1+fi+1,k-1 f1,k=fn,k-1+f2,k-1, 當(dāng)i=1時 fn,k=fn-1,k-1+f1,k-1, 當(dāng)i=n時 邊界條件：f1,0=1； answer=f1,m參考代碼 readln(n,m); f1,0:=1; for k:=1 to m do begin f1,k:=f2,k-1+fn,k-1; for i:=2 to n-1 do

28、fi,k:=fi-1,k-1+fi+1,k-1; fn,k:=fn-1,k-1+f1,k-1; end; writeln(f1,m);n 例題例題7：凸：凸n邊形的三角形剖分邊形的三角形剖分n 在一個凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用f(n)表之，f(n)即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故f(5)=5。求對于一個任意的凸n邊形相應(yīng)的f(n)。分析:設(shè)f(n)表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個凸n邊形的任意一條邊都必然是一個三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在同一直線上的三點(diǎn)可以確定一個三角形”，

29、只要在P2，P3，Pn-1點(diǎn)中找一個點(diǎn)Pk(1kn)，與P1、Pn 共同構(gòu)成一個三角形的三個頂點(diǎn)，就將n邊形分成了三個不相交的部分(如圖)，我們分別稱之為區(qū)域、區(qū)域、區(qū)域，其中區(qū)域必定是一個三角形，區(qū)域是一個凸k邊形，區(qū)域是一個凸n-k+1邊形，區(qū)域的拆分方案總數(shù)是f(k)，區(qū)域的拆分方案數(shù)為f(n-k+1)，故包含P1PkPn的n 邊形的拆分方案數(shù)為f(k)*f(n-k+1)種，而Pk可以是P2，P3，Pn-1種任一點(diǎn)，根據(jù)加法原理，凸n邊形的三角拆分方案總數(shù)為:12) 1(*)()(niinfifnf邊界條件：f(2)=1【擴(kuò)展擴(kuò)展1 1】：二叉樹數(shù)目：二叉樹數(shù)目【問題描述問題描述】：求：

30、求n n個結(jié)點(diǎn)能構(gòu)成不同二叉數(shù)的數(shù)目。個結(jié)點(diǎn)能構(gòu)成不同二叉數(shù)的數(shù)目?！締栴}分析】： 設(shè)F(n)為n個結(jié)點(diǎn)組成二叉樹的數(shù)目。 容易知道：f(1)=1;f(2)=2,f(3)=5 選定1個結(jié)點(diǎn)為根，左子樹結(jié)點(diǎn)的個數(shù)為i，二叉樹數(shù)目f(i)種；右子樹結(jié)點(diǎn)數(shù)目為n-i-1，二叉樹數(shù)目f(n-i-1)種，i的可取范圍0，n-1。所以有： 為了計算的方便：約定f(0)=110) 1(*)()(niinfifnf【擴(kuò)展擴(kuò)展2】：出棧序列：出棧序列【問題描述問題描述】：N個不同元素按一定的順序入棧，求不同的個不同元素按一定的順序入棧，求不同的出棧序列數(shù)目。出棧序列數(shù)目。【問題分析】設(shè)f(n)為n個元素的不同出

31、棧序列數(shù)目。 容易得出：f(1)=1；f(2)=2。 第n個元素可以第i(1=i=n)個出棧，前面已出棧有i-1個元素，出棧方法：f(i-1)；后面出棧n-i 個元素，出棧方法為：f(n-i)。所以有： 初始條件： F(0)=1 ni 1i)-f(n *1)-f(iniinfifnf1)(*) 1()(例題例題10：錯排問題（經(jīng)典問題）：錯排問題（經(jīng)典問題）n n個數(shù)，分別為1n，排成一個長度為n的排列。若每一個數(shù)的位置都與數(shù)的本身不相等，則稱這個排列是一個錯排。例如，n=3，則錯排有2 3 1、3 1 2。編寫程序，求n的錯排個數(shù)分析我們設(shè)k個元素的錯位全排列的個數(shù)記做：f(k)。四個元素的

32、錯位排列f(4)我們用窮舉法可以找到如下9個： (4,3,2,1);(3,4,1,2);(2,1,4,3) (4,3,1,2);(2,4,1,3);(2,3,4,1) (4,1,2,3);(3,4,2,1);(3,1,4,2)它們有什么規(guī)律呢？n通過反復(fù)的試驗，我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生錯位排列： A、將k與(1，2，k-1)的某一個數(shù)互換，其他k-2個數(shù)進(jìn)行錯排，這樣可以得到(k-1)f(k-2)個錯位排列。 B、另一部分是將前k-1個元素的每一個錯位排列(有f(k-1)個)中的每一個數(shù)與k互換，這樣可以得到剩下的(k-1)f(k-1) 個錯位排列。n根據(jù)加法原理，我們得到求錯位排列的遞推

33、公式f(k):f(k)=(k-1)*(f(k1)+f(k2)例題例題11：編碼問題：編碼問題n 【問題描述問題描述】編碼工作常被運(yùn)用于密文或壓縮傳編碼工作常被運(yùn)用于密文或壓縮傳輸。這里我們用一種最簡單的編碼方式進(jìn)行編碼：輸。這里我們用一種最簡單的編碼方式進(jìn)行編碼：把一些有規(guī)律的單詞編成數(shù)字。字母表中共有把一些有規(guī)律的單詞編成數(shù)字。字母表中共有26個小寫字母個小寫字母a,b,c.,z。這些特殊的單詞長度不。這些特殊的單詞長度不超過超過6且字母按照升序排列。把所有這樣的單詞且字母按照升序排列。把所有這樣的單詞放在一起，按字典順序排列，一個單詞的編碼就放在一起，按字典順序排列，一個單詞的編碼就對應(yīng)著

34、它在字典中的位置，例如：對應(yīng)著它在字典中的位置，例如：a-1;b-2;z-26;ab-27;ac-28;你的任務(wù)就是對于所給的單詞，你的任務(wù)就是對于所給的單詞，求出它的編碼。求出它的編碼。 例題例題12：2k進(jìn)制數(shù)（進(jìn)制數(shù)（NOIP2006） 見見word文檔文檔有如下所示的一個編號為到的方格： 現(xiàn)由計算機(jī)和人進(jìn)行人機(jī)對奕，從到，每次可以走個方格，其中為集=a1,a2, a3,.am中的元素(m=4)，規(guī)定誰最先走到第n格為勝，試設(shè)計一個人機(jī)對奕方案，摸擬整個游戲過程的情況并力求計算機(jī)盡量不敗。12345 N-1 N分析n 題設(shè)條件：若誰先走到第N格誰將獲勝，例如，假設(shè)S=1,2，從第N格往前

35、倒推，則走到第N-1格或第N-2格的一方必敗，而走到第N-3格者必定獲勝，因此在N，S確定后，棋格中每個方格的勝、負(fù)或和態(tài)（雙方都不能到達(dá)第N格）都是可以事先確定的。將目標(biāo)格置為必勝態(tài)，由后往前倒推每一格的勝負(fù)狀態(tài)，規(guī)定在自己所處的當(dāng)前格后，若對方無論走到哪兒都必定失敗，則當(dāng)前格為勝態(tài)，若走后有任一格為勝格，則當(dāng)前格為輸態(tài)，否則為和態(tài)。 設(shè)1表示必勝態(tài)，-1表示必敗態(tài)，0表示和態(tài)或表示無法到達(dá)的棋格。 例如，設(shè)N10，S1,2，則可確定其每個棋格的狀態(tài)如下所示： 而N10，S2,3時，其每格的狀態(tài)將會如下所示： 有了棋格的狀態(tài)圖后，程序應(yīng)能判斷讓誰先走，計算機(jī)選擇必勝策略或雙方和（雙方均不能到

36、達(dá)目標(biāo)格）的策略下棋，這樣就能保證計算機(jī)盡可能不敗。n 例題例題14：最小傷害：最小傷害 n 把兒站在一個N x N的方陣中最左上角的格子里。他可以從一個格子走到它右邊和下邊的格子里。每一個格子都有一個傷害值。他想在受傷害最小的情況下走到方陣的最右下角。nFi,j：設(shè)走到(i,j) 這格的最小傷害值,aij表示(i,j)這格的傷害值。nFi,j=min(fi-1,j,fi,j-1)+ai,jn邊界條件：f1,1=a1,1 fi,1=fi-1,1+ai,1(2=i=n) f1,i=f1,i-1+a1,i(2=imax then max:=j; end;end; n起始狀態(tài)就是調(diào)用起始狀態(tài)就是調(diào)用

37、findmax(1,max),而像上述過程而像上述過程中的變參中的變參max完全可以省略。將上述方法修改可得下完全可以省略。將上述方法修改可得下面的算法：面的算法：Procedure findmax(i:integer);begin if i=n then exit else begin findmax(i+1); if aimax then max:=ai; end;end;n起始狀態(tài)就是調(diào)用起始狀態(tài)就是調(diào)用findmax(1) ，max為全局為全局變量，同時還減少了一個局部變量的使用。盡管變量，同時還減少了一個局部變量的使用。盡管這只是一個很簡單的例子，在本例中不做精簡，這只是一個很簡單的

38、例子，在本例中不做精簡，程序也還是能通過，但它精簡的原則對其它使用程序也還是能通過，但它精簡的原則對其它使用遞歸的程序而言卻是同樣適用的。特別是在遞歸遞歸的程序而言卻是同樣適用的。特別是在遞歸過程出現(xiàn)過程出現(xiàn)堆棧溢出情況時堆棧溢出情況時就應(yīng)該考慮這一問題。就應(yīng)該考慮這一問題。n 優(yōu)點(diǎn)：采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計比非遞歸算法的設(shè)計往往要容易一些，所以當(dāng)問題本身是遞歸定義的，或者問題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問題的解決方法是遞歸形式的時候，往往采用遞歸算法來解決。n 缺點(diǎn)：執(zhí)行的效率很低，尤其在邊界條件設(shè)置不當(dāng)?shù)那闆r下，極有可能陷入死循

39、環(huán)或者內(nèi)存溢出的窘境。五、遞歸的應(yīng)用五、遞歸的應(yīng)用n 處理遞歸定義或解決方法為遞歸方式的問題n 解決搜索問題和組合計數(shù)n 實(shí)現(xiàn)分治思想n 用于輸出動態(tài)規(guī)劃的中間過程n樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問題時，常?？梢圆捎眠f歸的方法。n 因為搜索產(chǎn)生的節(jié)點(diǎn)成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N皇后”問題，全排列，哈密頓回路，圖的可著色性等搜索問題。例題例題3：全排列：全排列 【問題描述問題描述】編程列舉出編程列舉出1、2、n的全排列，要的全排列，要求產(chǎn)生的任一個數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。求產(chǎn)生的任一個數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字?！疚募斎胛募斎搿枯斎胼斎雗

40、(1=n=9)【文件輸出文件輸出】有有1到到n組成的所有不重復(fù)數(shù)字的序列，組成的所有不重復(fù)數(shù)字的序列，每行一個序列每行一個序列n 我們假設(shè)n=3時，如下圖：位置1可以放置數(shù)字1、2、3；位置2可以放置數(shù)字1、2、3；位置3可以放置數(shù)字1、2、3，但是當(dāng)位置1放了數(shù)字1后位置2和位置3都不能在放1，因此畫樹的約束條件是：各位置的數(shù)字不能相同。 n 我們畫“解答樹”時，根結(jié)點(diǎn)一般是一個空結(jié)點(diǎn)，根結(jié)點(diǎn)下面的第1、2、3三層分別對應(yīng)位置1、位置2、位置3，用“”標(biāo)示的分支表示該結(jié)點(diǎn)不滿足約束條件，不能被擴(kuò)展出來：procedure f(k:integer) /搜索第搜索第k層結(jié)點(diǎn)（向第層結(jié)點(diǎn)（向第k個

41、位置放數(shù)）個位置放數(shù)）begin var i:integer; if k=n+1 then begin for i:=1 to n do write(ai);writeln;end / 如果搜索到一條路徑，則輸出一種解如果搜索到一條路徑，則輸出一種解 else for i:=1 to n do/每一個結(jié)點(diǎn)可以分解出每一個結(jié)點(diǎn)可以分解出n個子結(jié)點(diǎn)；個子結(jié)點(diǎn)； if bi=0 then /如果能生成第如果能生成第k層的第層的第i個結(jié)點(diǎn)；個結(jié)點(diǎn)； begin ak:=i; /第第k個位置為數(shù)字個位置為數(shù)字i； bi:=1; /標(biāo)記數(shù)字標(biāo)記數(shù)字i已用已用 f(k+1); /擴(kuò)展第擴(kuò)展第k層的第層的第i

42、個結(jié)點(diǎn)個結(jié)點(diǎn)(向第向第k+1個位置放數(shù)個位置放數(shù)) bi:=0; /向上回溯，并恢復(fù)數(shù)據(jù)向上回溯，并恢復(fù)數(shù)據(jù) end;end;n 不難發(fā)現(xiàn)，在各種時間復(fù)雜度為nlogn排序方法中，大都采用了遞歸的形式。n 因此無論是歸并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸處理。其實(shí)進(jìn)行分治，也是一個建樹的過程。n 如下圖中歸并排序的過程：例題例題4：表達(dá)式求值：表達(dá)式求值 u由鍵盤輸入一個算術(shù)表達(dá)式，該表達(dá)式由數(shù)字，加(+)、減(-)、乘(*)、求商(/)運(yùn)算符及小括號組成。 u例如：6*(8-1)+(5-(12-7)/5)/2u請編寫一個程序，計算輸入表達(dá)式的值。 【

43、問題描述問題描述】假設(shè)有m本書（編號為1,2,m），想將每本復(fù)制一份，m本書的頁數(shù)可能不同（分別是p1,p2,pm）。任務(wù)是將這m本書分給k個抄寫員（k=m），每本書只能分配給一個抄寫員進(jìn)行復(fù)制，而每個抄寫員所分配到的書必須是連續(xù)順序的。 復(fù)制工作是同時開始進(jìn)行的，并且每個抄寫員復(fù)制的速度都是一樣的。所以，復(fù)制完所有書稿所需時間取決于分配得到最多工作的那個抄寫員的復(fù)制時間。n試找一個最優(yōu)分配方案，使分配給每一個抄寫員的頁數(shù)的最大值盡可能?。ㄈ绱嬖诙鄠€最優(yōu)方案，輸出結(jié)果排序最小的一種）。 n 該題中m本書是順序排列的，k個抄寫員選擇數(shù)也是順序且連續(xù)的。不管以書的編號，還是以抄寫員標(biāo)號作為參變量劃

44、分階段，都符合策略的最優(yōu)化原理和無后效性?？紤]到k=m，以抄寫員編號來劃分階段會方便些。 n 設(shè)fi,j為前i個抄寫員復(fù)制前j本書的最小“頁數(shù)最大數(shù)”。Si=a1+a2+ai，則狀態(tài)轉(zhuǎn)移方程為：n fi,j=minmax(fi-1,k,Sj-Sk)(i-1=k=j-1)n di,j=k；記錄第i個人的最佳位置n 邊界條件 f1,i=Si。n輸出方案，則遞歸輸出；輸出方案，則遞歸輸出；procedure Print(i,j:integer)begin if i=1 then begin writeln(1, ,j);exit;end; Print(i-1,di,j); writeln(di,j+

45、1, ,j);endn歸納法的基本思想：歸納法的基本思想：是通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。n從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出有用的結(jié)論或解決問題的有效途徑。 n 細(xì)心的觀察；細(xì)心的觀察；n 豐富的聯(lián)想；豐富的聯(lián)想；n 繼續(xù)嘗試；繼續(xù)嘗試；n 總結(jié)歸納出結(jié)論?？偨Y(jié)歸納出結(jié)論。n 歸納是一種抽象，即從特殊現(xiàn)象中找出一般關(guān)系。n 由于在歸納的過程中不可能對所有的可能情況進(jìn)行枚舉，因而最后得到的結(jié)論還只是一種猜測(即歸納假設(shè))。所以，嚴(yán)格說來對于歸納假設(shè)還必須加以嚴(yán)格的證明。n 從問題的簡單具體狀態(tài)分析入手，目的是去尋求可以推廣的一般性規(guī)律，因此應(yīng)考慮簡單狀態(tài)與一般性狀態(tài)之間的聯(lián)系。n 從簡單狀態(tài)中分析出來的規(guī)律特征應(yīng)能夠被驗證是正確的，不能想當(dāng)然或任意地提出猜想，否則歸納出來的結(jié)論是錯誤的，必然導(dǎo)致整個問題的解是錯解。：求前n個自然數(shù)的平方之和