NOIP基礎(chǔ)算法綜合

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

2、 三、枚舉法的框架結(jié)構(gòu) 設(shè)a11為狀態(tài)元素ai的最小值；aik為狀態(tài)元素ai的最大值 (1=i=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)滿足檢驗(yàn)條件滿足檢驗(yàn)條件)輸出問(wèn)題的解輸出問(wèn)題的解; NOIP基礎(chǔ)算法綜合 四、枚舉法的優(yōu)缺點(diǎn) 枚舉法的優(yōu)點(diǎn)：枚舉法的優(yōu)點(diǎn)：由于枚舉

3、算法一般是現(xiàn)實(shí) 問(wèn)題的“直譯”，且是建立在考察大量狀 態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)之上的， 因此比較直觀，易于理解，其算法的正確 性也比較容易證明。 枚舉法的缺點(diǎn)：枚舉法的缺點(diǎn)：枚舉算法的效率取決于枚 舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)， 因此效率比較低。 NOIP基礎(chǔ)算法綜合 例題1：砝碼稱重砝碼稱重 【問(wèn)題描述問(wèn)題描述】設(shè)有1g、2g、3g、5g、10g、 20g的砝碼各若干枚（其總重=1000）， 求用這些砝碼能稱出不同的重量個(gè)數(shù)。 【文件輸入文件輸入】輸入1g、2g、3g、5g、10g、 20g的砝碼個(gè)數(shù)。 【文件輸出文件輸出】輸出能稱出不同重量的個(gè)數(shù)。 【樣例輸入樣例輸入】1 1 0

4、 0 0 0 【樣例輸出樣例輸出】3 NOIP基礎(chǔ)算法綜合 例題1：砝碼稱重砝碼稱重 【思路點(diǎn)撥思路點(diǎn)撥】根據(jù)輸入的砝碼信息，每種砝碼可 用的最大個(gè)數(shù)是確定的，而且每種砝碼的個(gè)數(shù)是 連續(xù)的，能取0到最大個(gè)數(shù)，所以符合枚舉法的兩 個(gè)條件，可以使用枚舉法。枚舉時(shí)，重量可以由 1g,2g,20g砝碼中的任何一個(gè)或者多個(gè)構(gòu)成， 枚舉對(duì)象可以確定為6種重量的砝碼，范圍為每種 砝碼的個(gè)數(shù)。判定時(shí)，只需判斷這次得到的重量 是新得到的，還是前一次已經(jīng)得到的，即判重。 由于重量=1000g，所以，可以開(kāi)一個(gè)a1001的 數(shù)組來(lái)判重 NOIP基礎(chǔ)算法綜合 例題1：砝碼稱重砝碼稱重 偽代碼如下： memset(a,

5、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+) /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ì)不同重

6、量的個(gè)數(shù)統(tǒng)計(jì)不同重量的個(gè)數(shù) coutnum=0） 3.n(n=24)根火柴棍必須全部用上 NOIP基礎(chǔ)算法綜合 例題2：火柴棒等式（火柴棒等式（NOIP2008） 【問(wèn)題簡(jiǎn)述問(wèn)題簡(jiǎn)述】給你n(n=A，滿足條件的A的最大 取值為1111。所以枚舉A和B的范圍是從01111。 為了加快速度，可以將0到2222的所有整數(shù)需要 的火柴棒數(shù)目提前算好保存在數(shù)組中。 NOIP基礎(chǔ)算法綜合 五、枚舉算法的優(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)的考

7、察代價(jià) 優(yōu)化過(guò)程從以下幾個(gè)方面考慮：優(yōu)化過(guò)程從以下幾個(gè)方面考慮： 枚舉對(duì)象的選取枚舉對(duì)象的選取 枚舉方法的確定枚舉方法的確定 采用局部枚舉或引進(jìn)其他算法采用局部枚舉或引進(jìn)其他算法 NOIP基礎(chǔ)算法綜合 【例題例題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ù)字所有數(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; cou

8、tsy-sx-1endl; NOIP基礎(chǔ)算法綜合 【例題例題4】最大子矩陣問(wèn)題最大子矩陣問(wèn)題 【問(wèn)題描述問(wèn)題描述】給定一個(gè)二維的數(shù)組（含正 數(shù)或負(fù)數(shù)），請(qǐng)從中找出和最大的子矩陣。 例如： NOIP基礎(chǔ)算法綜合 【例題例題4】最大子矩陣問(wèn)題最大子矩陣問(wèn)題 1、“直譯直譯”枚舉過(guò)程枚舉過(guò)程 for(x1=1;x1=n;x1+)/枚舉矩形左上角枚舉矩形左上角(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,y

9、2)內(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)粗糙，枚舉狀態(tài)的費(fèi)用為O(n6) NOIP基礎(chǔ)算法綜合 2、從減少重復(fù)計(jì)算入手、從減少重復(fù)計(jì)算入手 有剛才一維情況可以推廣到二維，在統(tǒng)計(jì)左上角為有剛才一維情況可以推廣到二維，在統(tǒng)計(jì)左上角為(x1,y1

10、)右下角為右下角為 (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)左上角為(x1,y1)右下角為右下角為(x2,y2)內(nèi)矩形的元素之和，可以改為：內(nèi)矩形的元素之和，可以改為： sum=sx2y2-sx1-1y2-sx2y1-1+sx1-

11、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)題 NOIP基礎(chǔ)算法綜合 3、提取恰當(dāng)?shù)男畔?、提取恰?dāng)?shù)男畔?容易觀察到，最大子矩陣問(wèn)題是最大連續(xù)子序列和問(wèn)題的提升，即將一條線 換成一個(gè)面，將一維問(wèn)題提升到二維問(wèn)題。所以我們計(jì)算最大子矩陣的方法就是 將一行行的數(shù)進(jìn)行累加以求得最大值。 但是還有一個(gè)問(wèn)題，那就是應(yīng)該如何高效地存儲(chǔ)矩陣？ 我們可以想到：在一個(gè)一維的數(shù)列中，設(shè)數(shù)組bi表示從第1個(gè)元素到第i個(gè)元 素的和，則如果

12、想要求第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)題最大子矩陣問(wèn)題 NOIP基礎(chǔ)算法綜合 核心代碼核心代碼 sum=-0 x7fffffff; for(i=1;i=n;i+

13、) /階段階段:起始行起始行 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)系。 NOIP基礎(chǔ)算法綜合 n 建立遞推關(guān)系式建立遞推關(guān)系式 n確定邊界條件確定邊界條件 n遞推求解遞推求解 NOIP基礎(chǔ)算法綜合 l順推法和倒推法順推法和倒推法 NOIP基礎(chǔ)算法綜合 l 一般遞推問(wèn)題

14、一般遞推問(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)系 NOIP基礎(chǔ)算法綜合 例題例題1：faibonacci數(shù)列數(shù)列 【問(wèn)題描述問(wèn)題描述】已知faibonacci數(shù)列的前幾個(gè) 數(shù)分別為0，1，1，2，3，5，編程求 出此數(shù)列的第n項(xiàng)。（ n=60） NOIP基礎(chǔ)算法綜合 【例題例題2】輸出楊輝三角的前輸出楊輝三角的前N行行 【問(wèn)題描述問(wèn)題描述】輸出楊輝三角的前N行(N10)。 【文件輸入文件輸入】輸入只有一行，包括1個(gè)整數(shù)N(N=2)個(gè)盤子時(shí)， 總是先借助c柱把上面的n-1個(gè)盤子移動(dòng)到b柱上，然后把a(bǔ)柱 最下

15、面的盤子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤子 移動(dòng)到c柱上；總共移動(dòng)hn-1+1+hn-1個(gè)盤次。 hn=2hn-1+1 邊界條件：h1=1 NOIP基礎(chǔ)算法綜合 NOIP基礎(chǔ)算法綜合 【例題例題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ù)，但該自然

16、數(shù)不能超過(guò) 原數(shù)的一半；原數(shù)的一半； 3.加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再而加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再而 自然數(shù)為止；自然數(shù)為止； NOIP基礎(chǔ)算法綜合 方法方法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)。 NOIP基礎(chǔ)算法綜合 方法方法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) 此算

17、法的時(shí)間復(fù)雜度可降到O(n)。 NOIP基礎(chǔ)算法綜合 方法方法3：還是用遞推：還是用遞推。 只要做仔細(xì)分析，其實(shí)我們還可以得到以 下的遞推公式： (1)當(dāng)i為奇數(shù)時(shí),h(i)=h(i-1); (2) 當(dāng)i為偶數(shù)時(shí),h(i)=h(i-1)+h(i/2); NOIP基礎(chǔ)算法綜合 【思考思考】1.若若n=10000怎么計(jì)算；怎么計(jì)算； 2.若若n=3000000怎么計(jì)算；怎么計(jì)算； NOIP基礎(chǔ)算法綜合 例題例題5：猴子吃桃問(wèn)題：猴子吃桃問(wèn)題1538 猴子吃桃問(wèn)題。猴子摘了一堆桃，第一天吃了一猴子吃桃問(wèn)題。猴子摘了一堆桃，第一天吃了一 半，還嫌不過(guò)癮，又吃了一個(gè)；第二天又吃了剩半，還嫌不過(guò)癮，又吃了

18、一個(gè)；第二天又吃了剩 下的一半零一個(gè)；以后每天如此。到第下的一半零一個(gè)；以后每天如此。到第n天，猴天，猴 子一看只剩下一個(gè)了。問(wèn)最初有多少個(gè)桃子？子一看只剩下一個(gè)了。問(wèn)最初有多少個(gè)桃子？ NOIP基礎(chǔ)算法綜合 【擴(kuò)展練習(xí)擴(kuò)展練習(xí)】猴子分桃猴子分桃 【問(wèn)題描述問(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)。第一

19、個(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 NOIP基礎(chǔ)算法綜合 【例題例題6】傳球游戲（傳球游戲（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è)（

20、左右任意），當(dāng)老師再吹哨子 時(shí)，傳球停止，此時(shí)，拿著球沒(méi)傳出去的那個(gè)同學(xué)就是敗者，要給大家 表演一個(gè)節(jié)目。 聰明的小蠻提出一個(gè)有趣的問(wèn)題：有多少種不同的傳球方法可以使 得從小蠻手里開(kāi)始傳的球，傳了m（3=m2-3-1和1-3-2- 1，共兩種。 NOIP基礎(chǔ)算法綜合 分析 設(shè)fik表示經(jīng)過(guò)k次傳到編號(hào)為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=1時(shí) 邊界條件

21、：f10=1；結(jié)果在f1m中。 NOIP基礎(chǔ)算法綜合 參考代碼 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; coutf1mendl; NOIP基礎(chǔ)算法綜合 Catalan數(shù) 定義：Cn=n+2條邊的多邊形，能被分割成 三角形的方案數(shù)，例如5邊型的分割方案有： NOIP基礎(chǔ)算法綜合 如圖，有一個(gè)正n+2邊形。任取一邊，從這邊的端點(diǎn)開(kāi)始， 依次給頂點(diǎn)編號(hào)為：0,1,2,3,.,n,n+1(所取

22、的邊端點(diǎn)編號(hào) 為:0,n+1)。這樣，除線段所在頂點(diǎn)外，還有n個(gè)頂點(diǎn)： 1,2,3,n。我們以該線段為三角形的一條邊，另一個(gè)頂 點(diǎn)為i(1=i=n)。 NOIP基礎(chǔ)算法綜合 我們?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,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ù)加法原理則有： 這與Cat

23、alan數(shù)C(n)的表達(dá)式是一致的。故本題答 案為H(n)=C(n)。 n i inHiHnH 1 )(*)1()( NOIP基礎(chǔ)算法綜合 具體實(shí)現(xiàn)時(shí)，若直接用上述公式計(jì)算，對(duì)數(shù)字的精度要具體實(shí)現(xiàn)時(shí)，若直接用上述公式計(jì)算，對(duì)數(shù)字的精度要 求較高?？蓪⑵浠癁檫f推式求較高?？蓪⑵浠癁檫f推式 ) 1( 1 ) 12(*2 )( nf n n nf 再進(jìn)行遞推計(jì)算，并且注意類型的定義要用再進(jìn)行遞推計(jì)算，并且注意類型的定義要用long long長(zhǎng)整長(zhǎng)整 型。型。 NOIP基礎(chǔ)算法綜合 Catalan數(shù)的應(yīng)用（部分和序列） 問(wèn)題：n個(gè)1和n個(gè)0組成一2n位的二進(jìn)制，要求從左到右掃描， 1的累計(jì)數(shù)不小于0的

24、累計(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元的鈔票找零？ NOIP基礎(chǔ)算法綜合 Catalan數(shù)的應(yīng)用（棧 NOIp2003） 問(wèn)題：一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1,2,3,.n，有 多少個(gè)不同的出棧序列？ NOIP基礎(chǔ)算法綜合 Catalan數(shù)的應(yīng)用（加括號(hào)） P=A1A2A3An，依據(jù)乘法結(jié)合律，不改變其 順序，只用括號(hào)表示

25、成對(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 (1) 令C(k)=P(k+1),k=1,2,n，代入(1)式，有： C(n)=C(0)*C(n-1

26、)+C(1)*C(n-2)+C(n-1)*C(0) = 因此，本題的答案為C(n-1)。 n i inCiC 1 )(*)1( NOIP基礎(chǔ)算法綜合 遞推的應(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。編寫程序，求n的錯(cuò) 排個(gè)數(shù) NOIP基礎(chǔ)算法綜合 分析 我們?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,4,3) (4,3,1,2);(2,

27、4,1,3);(2,3,4,1) (4,1,2,3);(3,4,2,1);(3,1,4,2) 它們有什么規(guī)律呢？ NOIP基礎(chǔ)算法綜合 通過(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) NOIP基礎(chǔ)算法綜合 遞推的應(yīng)用（組合計(jì)

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

29、：a-1;b-2;z-26;ab- 27;ac-28;你的任務(wù)就是對(duì)于所給的單詞，求出它的編碼。你的任務(wù)就是對(duì)于所給的單詞，求出它的編碼。 NOIP基礎(chǔ)算法綜合 例題：走直線棋問(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 NOIP基礎(chǔ)算法綜合 分析 題設(shè)條件：若誰(shuí)先走到第N格誰(shuí)將獲勝，例如，假設(shè) S=1,2，從第N格往前倒推，則走到第N-1格或第N-2格 的一方必?cái)?/p>

30、，而走到第N-3格者必定獲勝，因此在N，S 確定后，棋格中每個(gè)方格的勝、負(fù)或和態(tài)（雙方都不能 到達(dá)第N格）都是可以事先確定的。將目標(biāo)格置為必勝 態(tài)，由后往前倒推每一格的勝負(fù)狀態(tài)，規(guī)定在自己所處 的當(dāng)前格后，若對(duì)方無(wú)論走到哪兒都必定失敗，則當(dāng)前 格為勝態(tài)，若走后有任一格為勝格，則當(dāng)前格為輸態(tài)， 否則為和態(tài)。 NOIP基礎(chǔ)算法綜合 設(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á)目

31、標(biāo)格）的策略下棋， 這樣就能保證計(jì)算機(jī)盡可能不敗。 NOIP基礎(chǔ)算法綜合 遞推的應(yīng)用（動(dòng)態(tài)規(guī)劃中的遞推） 例題：最小傷害例題：最小傷害 把兒站在一個(gè)N x N的方陣中最左上角的格子里。他可以 從一個(gè)格子走到它右邊和下邊的格子里。每一個(gè)格子都有 一個(gè)傷害值。他想在受傷害最小的情況下走到方陣的最右 下角。 NOIP基礎(chǔ)算法綜合 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) NOIP基礎(chǔ)算法綜合 在一個(gè)nm

32、的方格中，m 為奇數(shù)，放置有nm個(gè) 數(shù) ，如圖,方格中間的下 方有一人，此人可按照五 個(gè)方向前進(jìn)但不能越出方 格,見(jiàn)右下圖。 人每走過(guò)一個(gè)方格必須取 此方格中的數(shù)。要求找到 一條從底到頂?shù)穆窂?，?其數(shù)相加之和為最大。輸 出和的最大值。 164312603 4-567002 60-1-2368 53400-27 -17407-56 0-1341242 人 NOIP基礎(chǔ)算法綜合 我們用坐標(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)

33、的的 點(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-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

34、 表示表示(x,y) 點(diǎn)上的數(shù)字。點(diǎn)上的數(shù)字。 邊界條件為：邊界條件為： 0 0,2/ m F ) 2/1 ( 0, mxmxFx且 NOIP基礎(chǔ)算法綜合 上題實(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)系呢？ 我們不妨畫個(gè)圖我們不妨畫個(gè)圖(如下圖如下圖)。而通常人們理解的遞推關(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)系 NOIP基礎(chǔ)算法綜合 1、一般

35、遞推邊界條件很明顯,動(dòng)態(tài)規(guī)劃邊界條件 比較隱蔽,容易被忽視 2、一般遞推數(shù)學(xué)性較強(qiáng),動(dòng)態(tài)規(guī)劃數(shù)學(xué)性相對(duì)較 弱 3、一般遞推一般不劃分階段,動(dòng)態(tài)規(guī)劃一般有較 為明顯的階段 NOIP基礎(chǔ)算法綜合 【例題例題1】位數(shù)問(wèn)題位數(shù)問(wèn)題 【問(wèn)題描述問(wèn)題描述】在所有的N位數(shù)中，有多少個(gè)數(shù)中有偶數(shù)個(gè)數(shù) 字3？由于結(jié)果可能很大，你只需要輸出這個(gè)答案mod 12345的值。 【文件輸入文件輸入】讀入一個(gè)數(shù)N(1=N=1000) 【文件輸出文件輸出】輸出有多少個(gè)數(shù)中有偶數(shù)個(gè)數(shù)字3。 【樣例輸入樣例輸入】2 【樣例輸出樣例輸出】73 NOIP基礎(chǔ)算法綜合 【例題例題2】鋪磁磚問(wèn)題鋪磁磚問(wèn)題 【問(wèn)題描述問(wèn)題描述】用用1x

36、1和和2x2的磁磚不重疊地鋪滿的磁磚不重疊地鋪滿Nx3的地板，的地板， 問(wèn)共有多少種不同的方案？問(wèn)共有多少種不同的方案？ 【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=N=1000）。）。 【文件輸出文件輸出】輸出方案數(shù)，由于結(jié)果可能很大，你只需要輸輸出方案數(shù)，由于結(jié)果可能很大，你只需要輸 出這個(gè)答案出這個(gè)答案mod 12345的值。的值。 【樣例輸入樣例輸入】2 【樣例輸出樣例輸出】3 NOIP基礎(chǔ)算法綜合 【例題例題3】路程問(wèn)題路程問(wèn)題 【問(wèn)題描述問(wèn)題描述】從原點(diǎn)出發(fā)，一步只能向右走、向上走或向左從原點(diǎn)出發(fā)，一步只能向右走、向上走或向左 走。恰好走走。恰好走N步且不經(jīng)過(guò)已走的點(diǎn)共有多

37、少種走法？步且不經(jīng)過(guò)已走的點(diǎn)共有多少種走法？ 【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=n=1000）。）。 【文件輸出文件輸出】輸出走法數(shù)。由于結(jié)果可能很大，你只需要輸輸出走法數(shù)。由于結(jié)果可能很大，你只需要輸 出這個(gè)答案出這個(gè)答案mod 12345的值。的值。 【樣例輸入樣例輸入】2 【樣例輸出樣例輸出】7 NOIP基礎(chǔ)算法綜合 【例題例題4】圓周上的弦圓周上的弦 【問(wèn)題描述問(wèn)題描述】圓周上有圓周上有N個(gè)點(diǎn)。連接任意多條（可能是個(gè)點(diǎn)。連接任意多條（可能是0條）條） 不相交的弦（共用端點(diǎn)也算相交）共有多少種方案？不相交的弦（共用端點(diǎn)也算相交）共有多少種方案？ 【文件輸入文件輸入】輸入

38、一個(gè)整數(shù)輸入一個(gè)整數(shù)n（1=N=1000）。）。 【文件輸出文件輸出】輸出方案數(shù)。由于結(jié)果可能很大，你只需要輸輸出方案數(shù)。由于結(jié)果可能很大，你只需要輸 出這個(gè)答案出這個(gè)答案mod 12345的值。的值。 【樣例輸入樣例輸入】4 【樣例輸出樣例輸出】9 NOIP基礎(chǔ)算法綜合 【例題例題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è)生成樹(shù)？圖有多少個(gè)生成樹(shù)？ 【文件輸入文件輸入】輸入一個(gè)整數(shù)輸入一個(gè)整數(shù)n

39、（1=Nc; if(c!=!)rever(); coutc; int main() rever(); return 0; 【樣例輸入樣例輸入】gnauh！ 【樣例輸出樣例輸出】 NOIP基礎(chǔ)算法綜合 采用遞歸方法編寫的問(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)解決。 NOIP基礎(chǔ)算法綜合 遞歸的應(yīng)用遞歸的應(yīng)用 處理遞歸定義或解決方法為遞歸方式的問(wèn)題 解決搜索問(wèn)題 實(shí)現(xiàn)分治思想 用于輸出動(dòng)態(tài)規(guī)劃的中間過(guò)程 NOIP

40、基礎(chǔ)算法綜合 樹(shù)結(jié)構(gòu)是由遞歸定義的。因此，在解決與 樹(shù)有關(guān)的問(wèn)題時(shí)，常?？梢圆捎眠f歸的方 法。 NOIP基礎(chǔ)算法綜合 因?yàn)樗阉鳟a(chǎn)生的節(jié)點(diǎn)成樹(shù)狀結(jié)構(gòu)，所以可以用遞 歸方法解決。這類例子很多，如“N皇后”問(wèn)題， 全排列，哈密頓回路，圖的可著色性等搜索問(wèn)題。 NOIP基礎(chǔ)算法綜合 例題：全排列例題：全排列 【問(wèn)題描述問(wèn)題描述】編程列舉出編程列舉出1、2、n的全排列，要求產(chǎn)生的全排列，要求產(chǎn)生 的任一個(gè)數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字的任一個(gè)數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字 【文件輸入文件輸入】輸入輸入n(1=n=9) 【文件輸出文件輸出】有有1到到n組成的所有不重復(fù)數(shù)字的序列，每行組成的所有不重復(fù)數(shù)字的序列，每行 一個(gè)序列一個(gè)序列 NOIP基礎(chǔ)算法綜合 分析 我們假設(shè)n=3時(shí)，如下圖：位置1可以放置數(shù)字1、2、3；位 置2可以放置數(shù)字1、2、3；位置3可以放置數(shù)字1、2、3， 但是當(dāng)位置1放了數(shù)字1后位置2和位置3都不能在放1，因此 畫樹(shù)的約束條件是：各位置的數(shù)字不能相同。 NOIP基礎(chǔ)算法綜合 分析 我們畫