NOIP基礎(chǔ)算法綜合

1、NOIP基礎(chǔ)算法綜合第一節(jié)第一節(jié) 枚舉算法枚舉算法一、枚舉法的基本思想 枚舉法的基本思想：枚舉法的基本思想：根據(jù)實(shí)際問(wèn)題設(shè)計(jì)多重循環(huán)，一一一一枚舉所有可能的狀態(tài)，并用問(wèn)題給定的約束條件檢驗(yàn)?zāi)男顟B(tài)是需要的，哪些狀態(tài)是不需要的。能使命題成立的狀態(tài)，即為其解。雖然枚舉法本質(zhì)上屬于搜索策略，但是它與后面講的回溯法或?qū)挾葍?yōu)先搜索有所不同。 二、枚舉法的條件: 可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n。如百錢買百雞問(wèn)題，3文錢一只雞的狀態(tài)元素個(gè)數(shù)可預(yù)先確定； 可預(yù)先確定每個(gè)狀態(tài)元素a1,a2,an的值域。三、枚舉法的框架結(jié)構(gòu) 設(shè)a11為狀態(tài)元素ai的最小值；aik為狀態(tài)元素ai的最大值(1=i=n),即狀態(tài)元素a

2、1,a2,an的值域分別為a11=a1=a1k, a21=a2=a2k,ai1=ai=aik, an1=an=ank。 for(a1=a11;a1=a1k;a1+) for(a2=a21;a2=a2k;a2+) . for(ai=ai1;ai=aik;ai+) . for(an=an1;an=ank;an+) if(狀態(tài)狀態(tài)(a1,.,ai.,an)滿足檢驗(yàn)條件滿足檢驗(yàn)條件)輸出問(wèn)題的解輸出問(wèn)題的解;四、枚舉法的優(yōu)缺點(diǎn) 枚舉法的優(yōu)點(diǎn)：枚舉法的優(yōu)點(diǎn)：由于枚舉算法一般是現(xiàn)實(shí)問(wèn)題的“直譯”，且是建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)之上的，因此比較直觀，易于理解，其算法的正確性也比較容易證明。

3、 枚舉法的缺點(diǎn)：枚舉法的缺點(diǎn)：枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)，因此效率比較低。例題1：砝碼稱重砝碼稱重 【問(wèn)題描述問(wèn)題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重=1000），求用這些砝碼能稱出不同的重量個(gè)數(shù)。【文件輸入文件輸入】輸入1g、2g、3g、5g、10g、20g的砝碼個(gè)數(shù)?！疚募敵鑫募敵觥枯敵瞿芊Q出不同重量的個(gè)數(shù)?！緲永斎霕永斎搿? 1 0 0 0 0【樣例輸出樣例輸出】3例題1：砝碼稱重砝碼稱重 【思路點(diǎn)撥思路點(diǎn)撥】根據(jù)輸入的砝碼信息，每種砝碼可用的最大個(gè)數(shù)是確定的，而且每種砝碼的個(gè)數(shù)是連續(xù)的，能取0到最大個(gè)數(shù)，所以符合枚

4、舉法的兩個(gè)條件，可以使用枚舉法。枚舉時(shí)，重量可以由1g,2g,20g砝碼中的任何一個(gè)或者多個(gè)構(gòu)成，枚舉對(duì)象可以確定為6種重量的砝碼，范圍為每種砝碼的個(gè)數(shù)。判定時(shí)，只需判斷這次得到的重量是新得到的，還是前一次已經(jīng)得到的，即判重。由于重量=1000g，所以，可以開(kāi)一個(gè)a1001的數(shù)組來(lái)判重 例題1：砝碼稱重砝碼稱重偽代碼如下：memset(a,0,sizeof(a); for(c1=0;c1=a;c1+) /1g砝碼的個(gè)數(shù)砝碼的個(gè)數(shù) for(c2=0;c2=b;c2+) /2g砝碼的個(gè)數(shù)砝碼的個(gè)數(shù)for(c3=0;c3=c;c3+) /3g砝碼的個(gè)數(shù)砝碼的個(gè)數(shù) for(c4=0;c4=d;c4+)

5、 /5g砝碼的個(gè)數(shù)砝碼的個(gè)數(shù) for(c5=0;c5=e;c5+) /10g砝碼的個(gè)數(shù)砝碼的個(gè)數(shù) for(c6=0;c6=f;c6+) /20g砝碼的個(gè)數(shù)砝碼的個(gè)數(shù) sum=0; for(i=1;i=6;i+)sum=sum+ci*wi; asum=1; /標(biāo)記標(biāo)記 for(i=1;i=1000;i+)if(ai)num+; /統(tǒng)計(jì)不同重量的個(gè)數(shù)統(tǒng)計(jì)不同重量的個(gè)數(shù)coutnum=0） 3.n(n=24)根火柴棍必須全部用上 例題2：火柴棒等式（火柴棒等式（NOIP2008） 【問(wèn)題簡(jiǎn)述問(wèn)題簡(jiǎn)述】給你n(n=A，滿足條件的A的最大取值為1111。所以枚舉A和B的范圍是從01111。為了加快速度，

6、可以將0到2222的所有整數(shù)需要的火柴棒數(shù)目提前算好保存在數(shù)組中。五、枚舉算法的優(yōu)化枚舉算法的優(yōu)化 枚舉算法的時(shí)間復(fù)雜度：狀態(tài)總數(shù)枚舉算法的時(shí)間復(fù)雜度：狀態(tài)總數(shù)*單個(gè)狀態(tài)的耗時(shí)單個(gè)狀態(tài)的耗時(shí) 主要優(yōu)化方法：主要優(yōu)化方法： 減少狀態(tài)總數(shù)減少狀態(tài)總數(shù) 降低單個(gè)狀態(tài)的考察代價(jià)降低單個(gè)狀態(tài)的考察代價(jià) 優(yōu)化過(guò)程從以下幾個(gè)方面考慮：優(yōu)化過(guò)程從以下幾個(gè)方面考慮： 枚舉對(duì)象的選取枚舉對(duì)象的選取 枚舉方法的確定枚舉方法的確定 采用局部枚舉或引進(jìn)其他算法采用局部枚舉或引進(jìn)其他算法【例題例題3】給你給你n個(gè)整數(shù)，然后要有個(gè)整數(shù)，然后要有m個(gè)詢問(wèn)。問(wèn)第個(gè)詢問(wèn)。問(wèn)第i個(gè)數(shù)字到第個(gè)數(shù)字到第j個(gè)數(shù)字所有數(shù)字之和。個(gè)數(shù)字所有

7、數(shù)字之和。【樸素算法樸素算法】 cinn; for(i=1;iai; for(i=1;ixy; sum=0; for(j=x;j=y;j+)sum+=aj; coutsumn; for(i=1;iai;si=si-1+ai; for(i=1;ixy; coutsy-sx-1endl; 【例題例題4】最大子矩陣問(wèn)題最大子矩陣問(wèn)題 【問(wèn)題描述問(wèn)題描述】給定一個(gè)二維的數(shù)組（含正數(shù)或負(fù)數(shù)），請(qǐng)從中找出和最大的子矩陣。例如：【例題例題4】最大子矩陣問(wèn)題最大子矩陣問(wèn)題1、“直譯直譯”枚舉過(guò)程枚舉過(guò)程for(x1=1;x1=n;x1+)/枚舉矩形左上角枚舉矩形左上角(x1,y1) for(y1=1;y1=n

8、;y1+) for(x2=1;X2=n;X2+)/枚舉矩形右下角枚舉矩形右下角(x2,y2) for(y2=1;y2=n;y2+) 考察狀態(tài)左上角為考察狀態(tài)左上角為(x1,y1)右下角為右下角為(x2,y2)內(nèi)矩形的元素之和；內(nèi)矩形的元素之和；設(shè)設(shè)map為數(shù)字矩陣；為數(shù)字矩陣；sum為當(dāng)前矩形內(nèi)元素的和；為當(dāng)前矩形內(nèi)元素的和；best為最優(yōu)解。考察過(guò)為最優(yōu)解。考察過(guò)程如下：程如下：sum=0；for(x=x1;x=x2;x+)/計(jì)算當(dāng)前矩形內(nèi)元素的和計(jì)算當(dāng)前矩形內(nèi)元素的和 for(y=y1;ybest)best=sum；/調(diào)整最優(yōu)解調(diào)整最優(yōu)解這個(gè)算法相當(dāng)粗糙，枚舉狀態(tài)的費(fèi)用為這個(gè)算法相當(dāng)粗糙，

9、枚舉狀態(tài)的費(fèi)用為O(n6)2、從減少重復(fù)計(jì)算入手、從減少重復(fù)計(jì)算入手有剛才一維情況可以推廣到二維，在統(tǒng)計(jì)左上角為有剛才一維情況可以推廣到二維，在統(tǒng)計(jì)左上角為(x1,y1)右下角為右下角為(x2,y2)內(nèi)矩形的元素之和時(shí)，我們同樣可以先初始化，計(jì)算出左上角為內(nèi)矩形的元素之和時(shí)，我們同樣可以先初始化，計(jì)算出左上角為(1,1)右下角為右下角為(x,y)內(nèi)矩形的元素之和內(nèi)矩形的元素之和sxy。 for(x1=1;x1=n;x1+)/枚舉矩形左上角枚舉矩形左上角(x1,y1) for(y1=1;y1mapij; sij=si-1j+sij-1-si-1j-1+mapij; 對(duì)于狀態(tài)左上角為對(duì)于狀態(tài)左上角

10、為(x1,y1)右下角為右下角為(x2,y2)內(nèi)矩形的元素之和，可以改為：內(nèi)矩形的元素之和，可以改為： sum=sx2y2-sx1-1y2-sx2y1-1+sx1-1y1-1; if(sumbest)best=sum；/調(diào)整最優(yōu)解調(diào)整最優(yōu)解由于利用了計(jì)算出的結(jié)果，整個(gè)算法的時(shí)間復(fù)雜度降為由于利用了計(jì)算出的結(jié)果，整個(gè)算法的時(shí)間復(fù)雜度降為O(n4)【例題例題4】最大子矩陣問(wèn)題最大子矩陣問(wèn)題3、提取恰當(dāng)?shù)男畔?、提取恰?dāng)?shù)男畔?容易觀察到，最大子矩陣問(wèn)題是最大連續(xù)子序列和問(wèn)題的提升，即將一條線換成一個(gè)面，將一維問(wèn)題提升到二維問(wèn)題。所以我們計(jì)算最大子矩陣的方法就是將一行行的數(shù)進(jìn)行累加以求得最大值。 但是

11、還有一個(gè)問(wèn)題，那就是應(yīng)該如何高效地存儲(chǔ)矩陣？ 我們可以想到：在一個(gè)一維的數(shù)列中，設(shè)數(shù)組bi表示從第1個(gè)元素到第i個(gè)元素的和，則如果想要求第i個(gè)元素到第j個(gè)元素的和，只需要計(jì)算bj-bi-1的值就行了。由此推廣到二維矩陣，設(shè)bij表示矩陣第j列前i個(gè)元素的和，aij表示元素?cái)?shù)據(jù)，則壓縮存儲(chǔ)：for(i=1;i=n;i+) for(j=1;jaij;bij=bi-1j+aij; 因此，我們可以使用三重循環(huán)求出所有的矩形值，即枚舉起始行i和終止行j，壓縮子矩形成為一行，變成一維求最大字段和問(wèn)題。 即tk=max(tk-1,0)+bjk-bi-1k; 時(shí)間復(fù)雜度為O(n3)【例題例題4】最大子矩陣問(wèn)題

12、最大子矩陣問(wèn)題核心代碼核心代碼 sum=-0 x7fffffff; for(i=1;i=n;i+) /階段階段:起始行起始行 for(j=i;j=n;j+) /狀態(tài)狀態(tài):結(jié)束行結(jié)束行 t1=bj1-bi-11; /初始化第初始化第1列的值列的值 for(k=2;ksum)sum=tk; coutsumn0時(shí)時(shí),可以用等號(hào)可以用等號(hào)(或大于號(hào)、或大于號(hào)、小于號(hào)小于號(hào))將將Hn與其前面的某些項(xiàng)與其前面的某些項(xiàng)Hi(0in)聯(lián)聯(lián)系起來(lái)，這樣的式子就叫做遞推關(guān)系。系起來(lái)，這樣的式子就叫做遞推關(guān)系。n 建立遞推關(guān)系式建立遞推關(guān)系式n確定邊界條件確定邊界條件n遞推求解遞推求解 l順推法和倒推法順推法和倒推

13、法l 一般遞推問(wèn)題一般遞推問(wèn)題l 組合計(jì)數(shù)類問(wèn)題組合計(jì)數(shù)類問(wèn)題l 一類博弈問(wèn)題的求解一類博弈問(wèn)題的求解l 動(dòng)態(tài)規(guī)劃問(wèn)題的遞推關(guān)系動(dòng)態(tài)規(guī)劃問(wèn)題的遞推關(guān)系例題例題1：faibonacci數(shù)列數(shù)列 【問(wèn)題描述問(wèn)題描述】已知faibonacci數(shù)列的前幾個(gè)數(shù)分別為0，1，1，2，3，5，編程求出此數(shù)列的第n項(xiàng)。（ n=60）【例題例題2】輸出楊輝三角的前輸出楊輝三角的前N行行 【問(wèn)題描述問(wèn)題描述】輸出楊輝三角的前N行(N10)。【文件輸入文件輸入】輸入只有一行，包括1個(gè)整數(shù)N(N=2)個(gè)盤(pán)子時(shí)，總是先借助c柱把上面的n-1個(gè)盤(pán)子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤(pán)子移動(dòng)到c柱上；再借助a柱把b柱上的n-

14、1個(gè)盤(pán)子移動(dòng)到c柱上；總共移動(dòng)hn-1+1+hn-1個(gè)盤(pán)次。hn=2hn-1+1 邊界條件：h1=1【例題例題4】數(shù)的計(jì)數(shù)數(shù)的計(jì)數(shù) 【問(wèn)題描述問(wèn)題描述】我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸包含輸入的自然數(shù)入的自然數(shù)n)，先輸入一個(gè)自然數(shù)，先輸入一個(gè)自然數(shù)n(n1000)，然后對(duì)此，然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理：自然數(shù)按照如下方法進(jìn)行處理： l.不作任何處理；不作任何處理； 2.在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過(guò)在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過(guò)原數(shù)的一半；原數(shù)的一半； 3.加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再而加上數(shù)后，繼續(xù)按

15、此規(guī)則進(jìn)行處理，直到不能再而 自然數(shù)為止；自然數(shù)為止； 方法方法1：用遞推用遞推。用hn表示自然數(shù)n所能擴(kuò)展的數(shù)據(jù)個(gè)數(shù)，則：h1=1,h2=2,h3=2,h4=4,h5=4,h6=6,h7=6,h8=10,h9=10。分析上數(shù)據(jù)，可得遞推公式：hi=1+h1+h2+hi/2。時(shí)間復(fù)雜度O(n2)。 方法方法2：是對(duì)方法：是對(duì)方法1的改進(jìn)的改進(jìn)。我們定義數(shù)組s. s(x)=h(1)+h(2)+h(x), h(x)=s(x)-s(x-1) 此算法的時(shí)間復(fù)雜度可降到O(n)。 方法方法3：還是用遞推：還是用遞推。 只要做仔細(xì)分析，其實(shí)我們還可以得到以下的遞推公式： (1)當(dāng)i為奇數(shù)時(shí),h(i)=h(

16、i-1); (2) 當(dāng)i為偶數(shù)時(shí),h(i)=h(i-1)+h(i/2); 【思考思考】1.若若n=10000怎么計(jì)算；怎么計(jì)算； 2.若若n=3000000怎么計(jì)算；怎么計(jì)算； 例題例題5：猴子吃桃問(wèn)題：猴子吃桃問(wèn)題1538 猴子吃桃問(wèn)題。猴子摘了一堆桃，第一天吃了一猴子吃桃問(wèn)題。猴子摘了一堆桃，第一天吃了一半，還嫌不過(guò)癮，又吃了一個(gè)；第二天又吃了剩半，還嫌不過(guò)癮，又吃了一個(gè)；第二天又吃了剩下的一半零一個(gè)；以后每天如此。到第下的一半零一個(gè)；以后每天如此。到第n天，猴天，猴子一看只剩下一個(gè)了。問(wèn)最初有多少個(gè)桃子？子一看只剩下一個(gè)了。問(wèn)最初有多少個(gè)桃子？ 【擴(kuò)展練習(xí)擴(kuò)展練習(xí)】猴子分桃猴子分桃 【問(wèn)

17、題描述問(wèn)題描述】有一堆桃子和N只猴子，第一只猴子將桃子平均分成了M堆后，還剩了1個(gè)，它吃了剩下的一個(gè)，并拿走一堆。后面的猴子也和第1只進(jìn)行了同樣的做法，請(qǐng)問(wèn)N只猴子進(jìn)行了同樣做法后這一堆桃子至少還剩了多少個(gè)桃子(假設(shè)剩下的每堆中至少有一個(gè)桃子)？而最初時(shí)的那堆桃子至少有多少個(gè)？ 【文件輸入文件輸入】輸入包含二個(gè)數(shù)據(jù)，數(shù)據(jù)間用空格隔開(kāi)。第一個(gè)數(shù)據(jù)為猴子的只數(shù)N(1N10)，第二個(gè)數(shù)據(jù)為桃子分成的堆數(shù)M(2M7)。 【文件輸出文件輸出】輸出包含兩行數(shù)據(jù)，第一行數(shù)據(jù)為剩下的桃子數(shù)，第二行數(shù)據(jù)為原來(lái)的桃子數(shù)。 【樣例輸入樣例輸入】3 2 【樣例輸出樣例輸出】 1 15【例題例題6】傳球游戲（傳球游戲（

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

19、為i的人手中的方案數(shù)，傳到i號(hào)同學(xué)的球只能來(lái)自于i的左邊一個(gè)同學(xué)和右邊一個(gè)同學(xué)，這兩個(gè)同學(xué)的編號(hào)分別是i-1和i+1，所以可以得到以下的遞推公式： fik=fi-1k-1+fi+1k-1 f1k=fnk-1+f2k-1, 當(dāng)i=1時(shí) fnk=fn-1k-1+f1k-1, 當(dāng)i=n時(shí) 邊界條件：f10=1；結(jié)果在f1m中。參考代碼 cinnm; memset(f,0,sizeof(f); f10=1; for(k=1;k=m;k+) f1k=f2k-1+fnk-1; for(i=2;i=n-1;i+) fik=fi-1k-1+fi+1k-1; fnk=fn-1k-1+f1k-1; coutf1m

20、endl; 樣例輸入 3 3 樣例輸出 2 具體過(guò)程 見(jiàn)右圖 數(shù)組的填充過(guò)程 按列 Catalan數(shù) 定義：Cn=n+2條邊的多邊形，能被分割成三角形的方案數(shù)，例如5邊型的分割方案有： 如圖，有一個(gè)正n+2邊形。任取一邊，從這邊的端點(diǎn)開(kāi)始，依次給頂點(diǎn)編號(hào)為：0,1,2,3,.,n,n+1(所取的邊端點(diǎn)編號(hào)為:0,n+1)。這樣，除線段所在頂點(diǎn)外，還有n個(gè)頂點(diǎn)：1,2,3,n。我們以該線段為三角形的一條邊，另一個(gè)頂點(diǎn)為i(1=i=n)。 我們?cè)O(shè)題意要求的三角形剖分方案數(shù)為H(n)，即除線段頂點(diǎn)(編號(hào)0與n+1)外，還有n個(gè)頂點(diǎn)時(shí)的三角形剖分方案為H(n)。則以頂點(diǎn)0,i為指定線段(上面還有1,2

21、,i-1，共i-1個(gè)頂點(diǎn))的剖分?jǐn)?shù)位H(i-1)；以頂點(diǎn)n+1，i為指定線段的剖分?jǐn)?shù)為H(n-i)。根據(jù)乘法原理，以0,i,n+1為一剖分三角形的剖分?jǐn)?shù)應(yīng)為：H(i-1)*H(n-i)，i=1,2,n，所得的剖分各不相同，根據(jù)加法原理則有： 這與Catalan數(shù)C(n)的表達(dá)式是一致的。故本題答案為H(n)=C(n)。niinHiHnH1)(*)1()(具體實(shí)現(xiàn)時(shí)，若直接用上述公式計(jì)算，對(duì)數(shù)字的精度要具體實(shí)現(xiàn)時(shí)，若直接用上述公式計(jì)算，對(duì)數(shù)字的精度要求較高?？蓪⑵浠癁檫f推式求較高?？蓪⑵浠癁檫f推式) 1(1) 12(*2)(nfnnnf再進(jìn)行遞推計(jì)算，并且注意類型的定義要用再進(jìn)行遞推計(jì)算，并且注

22、意類型的定義要用long long長(zhǎng)整長(zhǎng)整型。型。 Catalan數(shù)的應(yīng)用（部分和序列） 問(wèn)題：n個(gè)1和n個(gè)0組成一2n位的二進(jìn)制，要求從左到右掃描，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)，試求滿足這條件的數(shù)有多少？ 【類似1】將n個(gè)1和n個(gè)-1排成一行，要求第1個(gè)數(shù)至第k個(gè)數(shù)的累加和均非負(fù)，問(wèn)有幾種排列方法？ 【類似2】有2n個(gè)人排成一行進(jìn)入劇場(chǎng)。入場(chǎng)費(fèi)5元。其中只有n個(gè)人有一張5元鈔票，另外n人只有10元鈔票，劇院無(wú)其它鈔票，問(wèn)有多少種方法使得只要有10元的人買票，售票處就有5元的鈔票找零？Catalan數(shù)的應(yīng)用（棧 NOIp2003） 問(wèn)題：一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1,2,3,.n，有多少個(gè)不同

23、的出棧序列？ Catalan數(shù)的應(yīng)用（加括號(hào)） P=A1A2A3An，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，試問(wèn)有幾種括號(hào)化的方案？【分析分析】P(4)：即4個(gè)數(shù)相乘的情況如下：(a1a2)a3)a4);(a1(a2a3)a4);(a1a2)(a3a4);(a1(a2a3)a4);(a1(a2(a3a4)。不失一般性，可以假設(shè)最后一次乘法運(yùn)算如下：(a1ar)(ar+1an),(1=r=n)。令P(n)表示n個(gè)數(shù)乘積的n-1對(duì)括號(hào)插入的不同方案數(shù)，則： P(n)=p1pn-1+p2pn-2+.+pn-1p1,p1=p2=1 有：P(n+1)=p1pn+p2pn-1+.+pnp1

24、 (1) 令C(k)=P(k+1),k=1,2,n，代入(1)式，有： C(n)=C(0)*C(n-1)+C(1)*C(n-2)+C(n-1)*C(0) = 因此，本題的答案為C(n-1)。niinCiC1)(*)1(遞推的應(yīng)用（組合計(jì)數(shù)）錯(cuò)排問(wèn)題（經(jīng)典問(wèn)題） n個(gè)數(shù)，分別為1n，排成一個(gè)長(zhǎng)度為n的排列。若每一個(gè)數(shù)的位置都與數(shù)的本身不相等，則稱這個(gè)排列是一個(gè)錯(cuò)排。例如，n=3，則錯(cuò)排有2 3 1、3 1 2。編寫(xiě)程序，求n的錯(cuò)排個(gè)數(shù)分析 我們?cè)O(shè)k個(gè)元素的錯(cuò)位全排列的個(gè)數(shù)記做：f(k)。 四個(gè)元素的錯(cuò)位排列f(4)我們用窮舉法可以找到如下9個(gè)： (4,3,2,1);(3,4,1,2);(2,1,

25、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ī)律呢？通過(guò)反復(fù)的試驗(yàn)，我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生錯(cuò)位排列：A.將k與(1，2，k-1)的某一個(gè)數(shù)互換，其他k-2個(gè)數(shù)進(jìn)行錯(cuò)排，這樣可以得到(k-1)f(k-2)個(gè)錯(cuò)位排列。B.另一部分是將前k-1個(gè)元素的每一個(gè)錯(cuò)位排列（有f(k-1)個(gè)）中的每一個(gè)數(shù)與k互換，這樣可以得到剩下的(k-1)f(k-1) 個(gè)錯(cuò)位排列。根據(jù)加法原理，我們得到求錯(cuò)位排列的遞推公式W(k):f(k)=(k-1)*(f(k1)+f(k2)遞推的應(yīng)用（組合計(jì)數(shù)） 【例題例題】編碼問(wèn)題

26、編碼問(wèn)題 【問(wèn)題描述問(wèn)題描述】編碼工作常被運(yùn)用于密文或壓縮傳輸。這里編碼工作常被運(yùn)用于密文或壓縮傳輸。這里我們用一種最簡(jiǎn)單的編碼方式進(jìn)行編碼：把一些有規(guī)律的我們用一種最簡(jiǎn)單的編碼方式進(jìn)行編碼：把一些有規(guī)律的單詞編成數(shù)字。字母表中共有單詞編成數(shù)字。字母表中共有26個(gè)小寫(xiě)字母?jìng)€(gè)小寫(xiě)字母a,b,c.,z。這些特殊的單詞長(zhǎng)度不超過(guò)這些特殊的單詞長(zhǎng)度不超過(guò)6且字母按照升序排列。把所且字母按照升序排列。把所有這樣的單詞放在一起，按字典順序排列，一個(gè)單詞的編有這樣的單詞放在一起，按字典順序排列，一個(gè)單詞的編碼就對(duì)應(yīng)著它在字典中的位置，例如：碼就對(duì)應(yīng)著它在字典中的位置，例如：a-1;b-2;z-26;ab-2

27、7;ac-28;你的任務(wù)就是對(duì)于所給的單詞，求出它的編碼。你的任務(wù)就是對(duì)于所給的單詞，求出它的編碼。 例題：走直線棋問(wèn)題。有如下所示的一個(gè)編號(hào)為到的方格： 現(xiàn)由計(jì)算機(jī)和人進(jìn)行人機(jī)對(duì)奕，從到，每次可以走個(gè)方格，其中為集=a1,a2, a3,.am中的元素(m=4)，規(guī)定誰(shuí)最先走到第n格為勝，試設(shè)計(jì)一個(gè)人機(jī)對(duì)奕方案，摸擬整個(gè)游戲過(guò)程的情況并力求計(jì)算機(jī)盡量不敗。12345 N-1 N分析 題設(shè)條件：若誰(shuí)先走到第N格誰(shuí)將獲勝，例如，假設(shè)S=1,2，從第N格往前倒推，則走到第N-1格或第N-2格的一方必?cái)?，而走到第N-3格者必定獲勝，因此在N，S確定后，棋格中每個(gè)方格的勝、負(fù)或和態(tài)（雙方都不能到達(dá)第N格

28、）都是可以事先確定的。將目標(biāo)格置為必勝態(tài)，由后往前倒推每一格的勝負(fù)狀態(tài)，規(guī)定在自己所處的當(dāng)前格后，若對(duì)方無(wú)論走到哪兒都必定失敗，則當(dāng)前格為勝態(tài)，若走后有任一格為勝格，則當(dāng)前格為輸態(tài)，否則為和態(tài)。 設(shè)1表示必勝態(tài)，-1表示必?cái)B(tài)，0表示和態(tài)或表示無(wú)法到達(dá)的棋格。 例如，設(shè)N10，S1,2，則可確定其每個(gè)棋格的狀態(tài)如下所示： 而N10，S2,3時(shí)，其每格的狀態(tài)將會(huì)如下所示： 有了棋格的狀態(tài)圖后，程序應(yīng)能判斷讓誰(shuí)先走，計(jì)算機(jī)選擇必勝策略或雙方和（雙方均不能到達(dá)目標(biāo)格）的策略下棋，這樣就能保證計(jì)算機(jī)盡可能不敗。遞推的應(yīng)用（動(dòng)態(tài)規(guī)劃中的遞推） 例題：最小傷害例題：最小傷害 把兒站在一個(gè)N x N的方陣中

29、最左上角的格子里。他可以從一個(gè)格子走到它右邊和下邊的格子里。每一個(gè)格子都有一個(gè)傷害值。他想在受傷害最小的情況下走到方陣的最右下角。 Fij：設(shè)走到(i,j) 這格的最小傷害值,aij表示(i,j)這格的傷害值。 Fij=min(fi-1j,fij-1)+aij 邊界條件：f11=a11 fi1=fi-11+ai1(2=i=n) f1i=f1i-1+a1i(2=i=n) 在一個(gè)nm的方格中，m為奇數(shù)，放置有nm個(gè)數(shù) ，如圖,方格中間的下方有一人，此人可按照五個(gè)方向前進(jìn)但不能越出方格,見(jiàn)右下圖。 人每走過(guò)一個(gè)方格必須取此方格中的數(shù)。要求找到一條從底到頂?shù)穆窂剑蛊鋽?shù)相加之和為最大。輸出和的最大值。

30、1643126034-56700260-1-236853400-27-17407-560-1341242人 我們用坐標(biāo)我們用坐標(biāo)(x,y)唯一確定一個(gè)點(diǎn)，其中唯一確定一個(gè)點(diǎn)，其中(m,n)表示圖的右上角，表示圖的右上角，而人的出發(fā)點(diǎn)是，受人前進(jìn)方向的限制，能直接到達(dá)點(diǎn)而人的出發(fā)點(diǎn)是，受人前進(jìn)方向的限制，能直接到達(dá)點(diǎn)(x,y)的的點(diǎn)只有點(diǎn)只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到點(diǎn)。到點(diǎn)(x,y)的路徑中和最大的路徑必然要從的路徑中和最大的路徑必然要從(m/2,0)到到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y

31、-1)，(x-2,y-1)的幾條路徑中產(chǎn)生，既然要求最的幾條路徑中產(chǎn)生，既然要求最優(yōu)方案，當(dāng)然要挑一條和最大的路徑，關(guān)系式如下：優(yōu)方案，當(dāng)然要挑一條和最大的路徑，關(guān)系式如下：Fx,y= MaxFx+2,y-1 ,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1+Numx,y，其中其中Numx,y 表示表示(x,y) 點(diǎn)上的數(shù)字。點(diǎn)上的數(shù)字。邊界條件為：邊界條件為：00,2/mF)2/1 (0,mxmxFx且 上題實(shí)質(zhì)上是采用動(dòng)態(tài)規(guī)劃來(lái)求解上題實(shí)質(zhì)上是采用動(dòng)態(tài)規(guī)劃來(lái)求解,那么與遞推動(dòng)態(tài)那么與遞推動(dòng)態(tài)規(guī)劃之間到底是什么關(guān)系呢？規(guī)劃之間到底是什么關(guān)系呢？ 我們不妨畫(huà)個(gè)圖我們不妨畫(huà)個(gè)

32、圖(如下圖如下圖)。而通常人們理解的遞推關(guān)。而通常人們理解的遞推關(guān)系就是一般遞推關(guān)系，故認(rèn)為動(dòng)態(tài)規(guī)劃與遞推關(guān)系是系就是一般遞推關(guān)系，故認(rèn)為動(dòng)態(tài)規(guī)劃與遞推關(guān)系是兩個(gè)各自獨(dú)立的個(gè)體。兩個(gè)各自獨(dú)立的個(gè)體。動(dòng)態(tài)規(guī)劃一般遞推關(guān)系遞推關(guān)系 1、一般遞推邊界條件很明顯,動(dòng)態(tài)規(guī)劃邊界條件比較隱蔽,容易被忽視 2、一般遞推數(shù)學(xué)性較強(qiáng),動(dòng)態(tài)規(guī)劃數(shù)學(xué)性相對(duì)較弱 3、一般遞推一般不劃分階段,動(dòng)態(tài)規(guī)劃一般有較為明顯的階段 【例題例題1】位數(shù)問(wèn)題位數(shù)問(wèn)題 【問(wèn)題描述問(wèn)題描述】在所有的N位數(shù)中，有多少個(gè)數(shù)中有偶數(shù)個(gè)數(shù)字3？由于結(jié)果可能很大，你只需要輸出這個(gè)答案mod 12345的值?！疚募斎胛募斎搿孔x入一個(gè)數(shù)N(1=N

33、=1000)【文件輸出文件輸出】輸出有多少個(gè)數(shù)中有偶數(shù)個(gè)數(shù)字3。【樣例輸入樣例輸入】2【樣例輸出樣例輸出】73 【例題例題2】鋪磁磚問(wèn)題鋪磁磚問(wèn)題 【問(wèn)題描述問(wèn)題描述】用用1x1和和2x2的磁磚不重疊地鋪滿的磁磚不重疊地鋪滿Nx3的地板，的地板，問(wèn)共有多少種不同的方案？問(wèn)共有多少種不同的方案？【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=N=1000）。）?！疚募敵鑫募敵觥枯敵龇桨笖?shù)，由于結(jié)果可能很大，你只需要輸輸出方案數(shù)，由于結(jié)果可能很大，你只需要輸出這個(gè)答案出這個(gè)答案mod 12345的值。的值。【樣例輸入樣例輸入】2【樣例輸出樣例輸出】3 【例題例題3】路程問(wèn)題路程問(wèn)題 【問(wèn)題

34、描述問(wèn)題描述】從原點(diǎn)出發(fā)，一步只能向右走、向上走或向左從原點(diǎn)出發(fā)，一步只能向右走、向上走或向左走。恰好走走。恰好走N步且不經(jīng)過(guò)已走的點(diǎn)共有多少種走法？步且不經(jīng)過(guò)已走的點(diǎn)共有多少種走法？【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=n=1000）。）?！疚募敵鑫募敵觥枯敵鲎叻〝?shù)。由于結(jié)果可能很大，你只需要輸輸出走法數(shù)。由于結(jié)果可能很大，你只需要輸出這個(gè)答案出這個(gè)答案mod 12345的值。的值。【樣例輸入樣例輸入】2【樣例輸出樣例輸出】7 【例題例題4】圓周上的弦圓周上的弦 【問(wèn)題描述問(wèn)題描述】圓周上有圓周上有N個(gè)點(diǎn)。連接任意多條（可能是個(gè)點(diǎn)。連接任意多條（可能是0條）條）不相交的弦（

35、共用端點(diǎn)也算相交）共有多少種方案？不相交的弦（共用端點(diǎn)也算相交）共有多少種方案？【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=N=1000）。）。【文件輸出文件輸出】輸出方案數(shù)。由于結(jié)果可能很大，你只需要輸輸出方案數(shù)。由于結(jié)果可能很大，你只需要輸出這個(gè)答案出這個(gè)答案mod 12345的值。的值?！緲永斎霕永斎搿?【樣例輸出樣例輸出】9 【例題例題5】矩形中的樹(shù)矩形中的樹(shù) 【問(wèn)題描述問(wèn)題描述】在網(wǎng)格中取一個(gè)在網(wǎng)格中取一個(gè)N x 1的矩形，并把它當(dāng)作一的矩形，并把它當(dāng)作一個(gè)無(wú)向圖。這個(gè)圖有個(gè)無(wú)向圖。這個(gè)圖有2(N+1)個(gè)頂點(diǎn)，有個(gè)頂點(diǎn)，有3(N-1)+4條邊。這個(gè)條邊。這個(gè)圖有多少個(gè)生成

36、樹(shù)？圖有多少個(gè)生成樹(shù)？【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=Nc; if(c!=!)rever(); coutc; int main() rever(); return 0; 【樣例輸入樣例輸入】gnauh！ 【樣例輸出樣例輸出】 采用遞歸方法編寫(xiě)的問(wèn)題解決程序具有結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計(jì)比非遞歸算法的設(shè)計(jì)往往要容易一些，所以當(dāng)問(wèn)題本身是遞歸定義的，或者問(wèn)題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問(wèn)題的解決方法是遞歸形式的時(shí)候，往往采用遞歸算法來(lái)解決。遞歸的應(yīng)用遞歸的應(yīng)用 處理遞歸定義或解決方法為遞歸方式的問(wèn)題 解決搜索問(wèn)題 實(shí)現(xiàn)分治思想 用于輸出動(dòng)態(tài)規(guī)劃的中間過(guò)程 樹(shù)結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹(shù)有關(guān)的問(wèn)題時(shí)，常?？梢圆捎眠f歸的方法。 因?yàn)樗阉鳟a(chǎn)生的節(jié)點(diǎn)成樹(shù)狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N皇后”問(wèn)題，全排列，哈密頓回路，圖的可著色性等搜索問(wèn)題。例題：全排列例題：全排列 【問(wèn)題描述問(wèn)題描述】編程列舉出編程列舉出1、2、n的全排列，要求產(chǎn)生的全排列，要求產(chǎn)生的任一個(gè)數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字的任一個(gè)數(shù)字序列