NOIP基礎(chǔ)算法綜合ppt課件

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

2、=n),即狀態(tài)元素a1,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)滿足檢驗條件滿足檢驗條件)輸出問題的解輸出問題的解;.6四、枚舉法的優(yōu)缺點 枚舉法的優(yōu)點：枚舉法的優(yōu)點：由于枚舉算法一般是現(xiàn)實問題的“直譯”，且是建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)之上的，因此比較直觀，易于理解，其算法

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

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

5、for(c4=0;c4=d;c4+) /5g砝碼的個數(shù)砝碼的個數(shù) for(c5=0;c5=e;c5+) /10g砝碼的個數(shù)砝碼的個數(shù) for(c6=0;c6=f;c6+) /20g砝碼的個數(shù)砝碼的個數(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)計不同重量的個數(shù)統(tǒng)計不同重量的個數(shù)coutnum=0） 3.n(n=24)根火柴棍必須全部用上 .11例題2：火柴棒等式（火柴棒等式（NOIP2008） 【問題簡述問題簡述】給你n(n=A，滿足條件的A的最大取值為1111。所以枚舉

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

7、i個數(shù)字到第個數(shù)字到第j個數(shù)字所有數(shù)字之和。個數(shù)字所有數(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; .16【例題例題4】最大子矩陣問題最大子矩陣問題 【問題描述問題描述】給定一個二維的數(shù)組（含正數(shù)或負(fù)數(shù)），請從中找出和最大的子矩陣。例如：.17【例題例題4】最大子矩陣問題最大子矩陣問題1、“直譯直譯”枚舉過程枚舉過程for(x1=1;x1=n;x1+)/枚舉

8、矩形左上角枚舉矩形左上角(x1,y1) for(y1=1;y1=n;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)解?？疾爝^為最優(yōu)解?？疾爝^程如下：程如下：sum=0；for(x=x1;x=x2;x+)/計算當(dāng)前矩形內(nèi)元素的和計算當(dāng)前矩形內(nèi)元素的和 for(y=y1;ybest)best=sum；/調(diào)整最

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

10、sij-1-si-1j-1+mapij; 對于狀態(tài)左上角為對于狀態(tài)左上角為(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)解由于利用了計算出的結(jié)果，整個算法的時間復(fù)雜度降為由于利用了計算出的結(jié)果，整個算法的時間復(fù)雜度降為O(n4)【例題例題4】最大子矩陣問題最大子矩陣問題.193、提取恰當(dāng)?shù)男畔?、提取恰?dāng)?shù)男畔?容易觀察到，最大子矩陣問題是最大連續(xù)子序列和問題的提升，即將一條線換成一個面，將一維問題提升到二維

11、問題。所以我們計算最大子矩陣的方法就是將一行行的數(shù)進行累加以求得最大值。 但是還有一個問題，那就是應(yīng)該如何高效地存儲矩陣？ 我們可以想到：在一個一維的數(shù)列中，設(shè)數(shù)組bi表示從第1個元素到第i個元素的和，則如果想要求第i個元素到第j個元素的和，只需要計算bj-bi-1的值就行了。由此推廣到二維矩陣，設(shè)bij表示矩陣第j列前i個元素的和，aij表示元素數(shù)據(jù)，則壓縮存儲：for(i=1;i=n;i+) for(j=1;jaij;bij=bi-1j+aij; 因此，我們可以使用三重循環(huán)求出所有的矩形值，即枚舉起始行i和終止行j，壓縮子矩形成為一行，變成一維求最大字段和問題。 即tk=max(tk-1,

12、0)+bjk-bi-1k; 時間復(fù)雜度為O(n3)【例題例題4】最大子矩陣問題最大子矩陣問題.20核心代碼核心代碼 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時時,可以用等號可以用等號(或大于號、或大于號、小于號小于號)將將Hn與其前面的某些項與其前面的某些項Hi(0in)聯(lián)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。系起來，這樣的式子就叫做遞推關(guān)系。.26n 建立遞推關(guān)系

13、式建立遞推關(guān)系式n確定邊界條件確定邊界條件n遞推求解遞推求解 .27l順推法和倒推法順推法和倒推法.28l 一般遞推問題一般遞推問題l 組合計數(shù)類問題組合計數(shù)類問題l 一類博弈問題的求解一類博弈問題的求解l 動態(tài)規(guī)劃問題的遞推關(guān)系動態(tài)規(guī)劃問題的遞推關(guān)系.29例題例題1：faibonacci數(shù)列數(shù)列 【問題描述問題描述】已知faibonacci數(shù)列的前幾個數(shù)分別為0，1，1，2，3，5，編程求出此數(shù)列的第n項。（ n=60）.30【例題例題2】輸出楊輝三角的前輸出楊輝三角的前N行行 【問題描述問題描述】輸出楊輝三角的前N行(N10)?！疚募斎胛募斎搿枯斎胫挥幸恍?，包括1個整數(shù)N(N=2)個盤

14、子時，總是先借助c柱把上面的n-1個盤子移動到b柱上，然后把a柱最下面的盤子移動到c柱上；再借助a柱把b柱上的n-1個盤子移動到c柱上；總共移動hn-1+1+hn-1個盤次。hn=2hn-1+1 邊界條件：h1=1.34.35【例題例題4】數(shù)的計數(shù)數(shù)的計數(shù) 【問題描述問題描述】我們要求找出具有下列性質(zhì)數(shù)的個數(shù)我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸包含輸入的自然數(shù)入的自然數(shù)n)，先輸入一個自然數(shù)，先輸入一個自然數(shù)n(n1000)，然后對此，然后對此自然數(shù)按照如下方法進行處理：自然數(shù)按照如下方法進行處理： l.不作任何處理；不作任何處理； 2.在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過在它的左

15、邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；原數(shù)的一半； 3.加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直到不能再而加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直到不能再而 自然數(shù)為止；自然數(shù)為止； .36 方法方法1：用遞推用遞推。用hn表示自然數(shù)n所能擴展的數(shù)據(jù)個數(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。時間復(fù)雜度O(n2)。 .37 方法方法2：是對方法：是對方法1的改進的改進。我們定義數(shù)組s. s(x)=h(1)+h(2)+h(x), h(x)=s(x)-s(x-1) 此算法的時間復(fù)雜度

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

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

18、】輸出包含兩行數(shù)據(jù)，第一行數(shù)據(jù)為剩下的桃子數(shù)，第二行數(shù)據(jù)為原來的桃子數(shù)。 【樣例輸入樣例輸入】3 2 【樣例輸出樣例輸出】 1 15.42【例題例題6】傳球游戲（傳球游戲（NOIP2008普及）普及）2309【問題描述問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。 游戲規(guī)則是這樣的：n（3=n=30）個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個球，當(dāng)老師吹哨子時開始傳球，每個同學(xué)可以把球傳給自己左右的兩個同學(xué)中的一個（左右任意），當(dāng)老師再吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學(xué)就是敗者，要給大家表演一個節(jié)目。 聰明的小蠻提出一個有

19、趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m（3=m2-3-1和1-3-2-1，共兩種。 .43分析 設(shè)fik表示從小蠻開始，從小蠻開始，經(jīng)過k次傳到編號為i的人手中的方案數(shù)，傳到i號同學(xué)的球只能來自于i的左邊一個同學(xué)和右邊一個同學(xué)，這兩個同學(xué)的編號分別是i-1和i+1，所以可以得到以下的遞推公式： fik=fi-1k-1+fi+1k-1 f1k=fnk-1+f2k-1, 當(dāng)i=1時 fnk=fn-1k-1+f1k-1, 當(dāng)i=n時 邊界條件：f10=1；結(jié)果在f1m中。.44參考代碼 cinnm; memset(f,0,sizeof(f); f10=1; for(k=

20、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; coutf1mendl;.45 樣例輸入 3 3 樣例輸出 2 具體過程 見右圖 數(shù)組的填充過程 按列.46 Catalan數(shù) 定義：Cn=n+2條邊的多邊形，能被分割成三角形的方案數(shù)，例如5邊型的分割方案有：.47 如圖，有一個正n+2邊形。任取一邊，從這邊的端點開始，依次給頂點編號為：0,1,2,3,.,n,n+1(所取的邊端點編號為:0,n+1)。這樣，除線段所在頂點外，還有n個頂點：1,2,3,n。我們以該線段為三角形

21、的一條邊，另一個頂點為i(1=i=n)。 .48 我們設(shè)題意要求的三角形剖分方案數(shù)為H(n)，即除線段頂點(編號0與n+1)外，還有n個頂點時的三角形剖分方案為H(n)。則以頂點0,i為指定線段(上面還有1,2,i-1，共i-1個頂點)的剖分?jǐn)?shù)位H(i-1)；以頂點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()(.49具體實現(xiàn)時，若直接用上述公式

22、計算，對數(shù)字的精度要具體實現(xiàn)時，若直接用上述公式計算，對數(shù)字的精度要求較高?？蓪⑵浠癁檫f推式求較高。可將其化為遞推式) 1(1) 12(*2)(nfnnnf再進行遞推計算，并且注意類型的定義要用再進行遞推計算，并且注意類型的定義要用long long長整長整型。型。 .50Catalan數(shù)的應(yīng)用（部分和序列） 問題：n個1和n個0組成一2n位的二進制，要求從左到右掃描，1的累計數(shù)不小于0的累計數(shù)，試求滿足這條件的數(shù)有多少？ 【類似1】將n個1和n個-1排成一行，要求第1個數(shù)至第k個數(shù)的累加和均非負(fù)，問有幾種排列方法？ 【類似2】有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔

23、票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少種方法使得只要有10元的人買票，售票處就有5元的鈔票找零？.51Catalan數(shù)的應(yīng)用（棧 NOIp2003） 問題：一個棧(無窮大)的進棧序列為1,2,3,.n，有多少個不同的出棧序列？ .52Catalan數(shù)的應(yīng)用（加括號） P=A1A2A3An，依據(jù)乘法結(jié)合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？【分析分析】P(4)：即4個數(shù)相乘的情況如下：(a1a2)a3)a4);(a1(a2a3)a4);(a1a2)(a3a4);(a1(a2a3)a4);(a1(a2(a3a4)。不失一般性，可以假設(shè)最后一次乘法運算如下：

24、(a1ar)(ar+1an),(1=r=n)。令P(n)表示n個數(shù)乘積的n-1對括號插入的不同方案數(shù)，則： P(n)=p1pn-1+p2pn-2+.+pn-1p1,p1=p2=1 有：P(n+1)=p1pn+p2pn-1+.+pnp1 (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(.53遞推的應(yīng)用（組合計數(shù)）錯排問題（經(jīng)典問題） n個數(shù)，分別為1n，排成一個長度為n的排列。若每一個數(shù)的位置都與數(shù)的本身不相等，則稱這個排列是一個

25、錯排。例如，n=3，則錯排有2 3 1、3 1 2。編寫程序，求n的錯排個數(shù).54分析 我們設(shè)k個元素的錯位全排列的個數(shù)記做：f(k)。 四個元素的錯位排列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ī)律呢？.55通過反復(fù)的試驗，我們發(fā)現(xiàn)事實上有兩種方式產(chǎn)生錯位排列：A.將k與(1，2，k-1)的某一個數(shù)互換，其他k-2個數(shù)進行錯排，這樣可以得到(k-1)f(k-2)個錯位排列。B.另一部分是將前k-1個元素的

26、每一個錯位排列（有f(k-1)個）中的每一個數(shù)與k互換，這樣可以得到剩下的(k-1)f(k-1) 個錯位排列。根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):f(k)=(k-1)*(f(k1)+f(k2).56遞推的應(yīng)用（組合計數(shù)） 【例題例題】編碼問題編碼問題 【問題描述問題描述】編碼工作常被運用于密文或壓縮傳輸。這里編碼工作常被運用于密文或壓縮傳輸。這里我們用一種最簡單的編碼方式進行編碼：把一些有規(guī)律的我們用一種最簡單的編碼方式進行編碼：把一些有規(guī)律的單詞編成數(shù)字。字母表中共有單詞編成數(shù)字。字母表中共有26個小寫字母個小寫字母a,b,c.,z。這些特殊的單詞長度不超過這些特殊的單詞長度

27、不超過6且字母按照升序排列。把所且字母按照升序排列。把所有這樣的單詞放在一起，按字典順序排列，一個單詞的編有這樣的單詞放在一起，按字典順序排列，一個單詞的編碼就對應(yīng)著它在字典中的位置，例如：碼就對應(yīng)著它在字典中的位置，例如：a-1;b-2;z-26;ab-27;ac-28;你的任務(wù)就是對于所給的單詞，求出它的編碼。你的任務(wù)就是對于所給的單詞，求出它的編碼。 .57例題：走直線棋問題。有如下所示的一個編號為到的方格： 現(xiàn)由計算機和人進行人機對奕，從到，每次可以走個方格，其中為集=a1,a2, a3,.am中的元素(m=4)，規(guī)定誰最先走到第n格為勝，試設(shè)計一個人機對奕方案，摸擬整個游戲過程的情況

28、并力求計算機盡量不敗。12345 N-1 N.58分析 題設(shè)條件：若誰先走到第N格誰將獲勝，例如，假設(shè)S=1,2，從第N格往前倒推，則走到第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)。.59 設(shè)1表示必勝態(tài)，-1表示必敗態(tài)，0表示和態(tài)或表示無法到達(dá)的棋格。 例如，設(shè)N10，S1,2，則可確定其每個棋格的狀態(tài)如下所示：

29、而N10，S2,3時，其每格的狀態(tài)將會如下所示： 有了棋格的狀態(tài)圖后，程序應(yīng)能判斷讓誰先走，計算機選擇必勝策略或雙方和（雙方均不能到達(dá)目標(biāo)格）的策略下棋，這樣就能保證計算機盡可能不敗。.60遞推的應(yīng)用（動態(tài)規(guī)劃中的遞推） 例題：最小傷害例題：最小傷害 把兒站在一個N x N的方陣中最左上角的格子里。他可以從一個格子走到它右邊和下邊的格子里。每一個格子都有一個傷害值。他想在受傷害最小的情況下走到方陣的最右下角。.61 Fij：設(shè)走到(i,j) 這格的最小傷害值,aij表示(i,j)這格的傷害值。 Fij=min(fi-1j,fij-1)+aij 邊界條件：f11=a11 fi1=fi-11+ai

30、1(2=i=n) f1i=f1i-1+a1i(2=i=n).62 在一個nm的方格中，m為奇數(shù)，放置有nm個數(shù) ，如圖,方格中間的下方有一人，此人可按照五個方向前進但不能越出方格,見右下圖。 人每走過一個方格必須取此方格中的數(shù)。要求找到一條從底到頂?shù)穆窂?，使其?shù)相加之和為最大。輸出和的最大值。1643126034-56700260-1-236853400-27-17407-560-1341242人 .63我們用坐標(biāo)我們用坐標(biāo)(x,y)唯一確定一個點，其中唯一確定一個點，其中(m,n)表示圖的右上角，表示圖的右上角，而人的出發(fā)點是，受人前進方向的限制，能直接到達(dá)點而人的出發(fā)點是，受人前進方向的限

31、制，能直接到達(dá)點(x,y)的的點只有點只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到。到點點(x,y)的路徑中和最大的路徑必然要從的路徑中和最大的路徑必然要從(m/2,0)到到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-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，其中其

32、中Numx,y 表示表示(x,y) 點上的數(shù)字。點上的數(shù)字。邊界條件為：邊界條件為：00,2/mF)2/1 (0,mxmxFx且.64 上題實質(zhì)上是采用動態(tài)規(guī)劃來求解上題實質(zhì)上是采用動態(tài)規(guī)劃來求解,那么與遞推動態(tài)那么與遞推動態(tài)規(guī)劃之間到底是什么關(guān)系呢？規(guī)劃之間到底是什么關(guān)系呢？ 我們不妨畫個圖我們不妨畫個圖(如下圖如下圖)。而通常人們理解的遞推關(guān)。而通常人們理解的遞推關(guān)系就是一般遞推關(guān)系，故認(rèn)為動態(tài)規(guī)劃與遞推關(guān)系是系就是一般遞推關(guān)系，故認(rèn)為動態(tài)規(guī)劃與遞推關(guān)系是兩個各自獨立的個體。兩個各自獨立的個體。動態(tài)規(guī)劃一般遞推關(guān)系遞推關(guān)系.65 1、一般遞推邊界條件很明顯,動態(tài)規(guī)劃邊界條件比較隱蔽,容易被

33、忽視 2、一般遞推數(shù)學(xué)性較強,動態(tài)規(guī)劃數(shù)學(xué)性相對較弱 3、一般遞推一般不劃分階段,動態(tài)規(guī)劃一般有較為明顯的階段.66 【例題例題1】位數(shù)問題位數(shù)問題 【問題描述問題描述】在所有的N位數(shù)中，有多少個數(shù)中有偶數(shù)個數(shù)字3？由于結(jié)果可能很大，你只需要輸出這個答案mod 12345的值?！疚募斎胛募斎搿孔x入一個數(shù)N(1=N=1000)【文件輸出文件輸出】輸出有多少個數(shù)中有偶數(shù)個數(shù)字3。【樣例輸入樣例輸入】2【樣例輸出樣例輸出】73.67 【例題例題2】鋪磁磚問題鋪磁磚問題 【問題描述問題描述】用用1x1和和2x2的磁磚不重疊地鋪滿的磁磚不重疊地鋪滿Nx3的地板，的地板，問共有多少種不同的方案？問共有

34、多少種不同的方案？【文件輸入文件輸入】輸入一個整數(shù)輸入一個整數(shù)n（1=N=1000）。）?！疚募敵鑫募敵觥枯敵龇桨笖?shù)，由于結(jié)果可能很大，你只需要輸輸出方案數(shù)，由于結(jié)果可能很大，你只需要輸出這個答案出這個答案mod 12345的值。的值?！緲永斎霕永斎搿?【樣例輸出樣例輸出】3.68 【例題例題3】路程問題路程問題 【問題描述問題描述】從原點出發(fā)，一步只能向右走、向上走或向左從原點出發(fā)，一步只能向右走、向上走或向左走。恰好走走。恰好走N步且不經(jīng)過已走的點共有多少種走法？步且不經(jīng)過已走的點共有多少種走法？【文件輸入文件輸入】輸入一個整數(shù)輸入一個整數(shù)n（1=n=1000）。）?！疚募敵鑫募?/p>

35、輸出】輸出走法數(shù)。由于結(jié)果可能很大，你只需要輸輸出走法數(shù)。由于結(jié)果可能很大，你只需要輸出這個答案出這個答案mod 12345的值。的值。【樣例輸入樣例輸入】2【樣例輸出樣例輸出】7.69 【例題例題4】圓周上的弦圓周上的弦 【問題描述問題描述】圓周上有圓周上有N個點。連接任意多條（可能是個點。連接任意多條（可能是0條）條）不相交的弦（共用端點也算相交）共有多少種方案？不相交的弦（共用端點也算相交）共有多少種方案？【文件輸入文件輸入】輸入一個整數(shù)輸入一個整數(shù)n（1=N=1000）。）?！疚募敵鑫募敵觥枯敵龇桨笖?shù)。由于結(jié)果可能很大，你只需要輸輸出方案數(shù)。由于結(jié)果可能很大，你只需要輸出這個答案出

36、這個答案mod 12345的值。的值。【樣例輸入樣例輸入】4【樣例輸出樣例輸出】9.70 【例題例題5】矩形中的樹矩形中的樹 【問題描述問題描述】在網(wǎng)格中取一個在網(wǎng)格中取一個N x 1的矩形，并把它當(dāng)作一的矩形，并把它當(dāng)作一個無向圖。這個圖有個無向圖。這個圖有2(N+1)個頂點，有個頂點，有3(N-1)+4條邊。這個條邊。這個圖有多少個生成樹？圖有多少個生成樹？【文件輸入文件輸入】輸入一個整數(shù)輸入一個整數(shù)n（1=Nc; if(c!=!)rever(); coutc; int main() rever(); return 0; 【樣例輸入樣例輸入】gnauh！ 【樣例輸出樣例輸出】 .78 采用

37、遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清晰，可讀性強等優(yōu)點，且遞歸算法的設(shè)計比非遞歸算法的設(shè)計往往要容易一些，所以當(dāng)問題本身是遞歸定義的，或者問題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問題的解決方法是遞歸形式的時候，往往采用遞歸算法來解決。.79遞歸的應(yīng)用遞歸的應(yīng)用 處理遞歸定義或解決方法為遞歸方式的問題 解決搜索問題 實現(xiàn)分治思想 用于輸出動態(tài)規(guī)劃的中間過程.80 樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問題時，常?？梢圆捎眠f歸的方法。.81 因為搜索產(chǎn)生的節(jié)點成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N皇后”問題，全排列，哈密頓回路，圖的可著色性等搜索問題。.82例題：全排列例

38、題：全排列 【問題描述問題描述】編程列舉出編程列舉出1、2、n的全排列，要求產(chǎn)生的全排列，要求產(chǎn)生的任一個數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字的任一個數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字【文件輸入文件輸入】輸入輸入n(1=n=9)【文件輸出文件輸出】有有1到到n組成的所有不重復(fù)數(shù)字的序列，每行組成的所有不重復(fù)數(shù)字的序列，每行一個序列一個序列.83分析 我們假設(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ù)字不能相同。 .84分析 我們畫“解答樹”時，根結(jié)點一般是一個空結(jié)點，根結(jié)點下面的第1、2、3三層分別對應(yīng)位置1、位置2、位置3，用“”標(biāo)示的分支表示該結(jié)點不滿足約束條件，不能被擴展出來：.85void f(int k) /搜索第搜索第k層結(jié)點（向第層結(jié)點（向第k