信息學(xué)奧林匹克競賽輔導(dǎo)歸納策略

信息學(xué)奧林匹克競賽輔導(dǎo)課件歸納策略第一頁，共一百二十頁，2022年，8月28日

歸納法要比搜索的方法（例如以后將講解的枚舉法、回溯法等）更能反映問題的本質(zhì)。但是并不是所有實(shí)際問題都可以總結(jié)歸納出一般規(guī)律，即便是可以，歸納也不是一件容易的事情，尤其要?dú)w納出一個(gè)數(shù)學(xué)模型更為困難。而且歸納過程通常沒有一定的規(guī)則可供遵循。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出有用的結(jié)論或解決問題的有效途徑。第二頁，共一百二十頁，2022年，8月28日

通常，歸納的過程分四個(gè)步驟：(1)細(xì)心的觀察(2)豐富的聯(lián)想(3)繼續(xù)嘗試(4)總結(jié)歸納出結(jié)論第三頁，共一百二十頁，2022年，8月28日

歸納是一種抽象，即從特殊現(xiàn)象中找出一般關(guān)系。但在歸納過程中不可能列舉所有情況，因而最后得出的結(jié)論還只是一種猜測（即歸納假設(shè)）。通過精心觀察而提出的歸納假設(shè)得不到證實(shí)或最后證明是錯(cuò)的，也是常有的事。因此要盡可能對(duì)歸納假設(shè)加以嚴(yán)格的證明，證明的方法通常使用數(shù)學(xué)歸納法。即便找不到證明方法，也必須盡可能多地提出那些容易出錯(cuò)和疏漏的邊界情況加以驗(yàn)證，使歸納出的結(jié)論和解決問題的途徑經(jīng)得起各種測試數(shù)據(jù)的檢驗(yàn)。第四頁，共一百二十頁，2022年，8月28日問題經(jīng)過分析歸納后，一般產(chǎn)生四種結(jié)果：(1)遞推式(2)遞歸式(3)制定目標(biāo)(4)貪心方案第五頁，共一百二十頁，2022年，8月28日

當(dāng)然，經(jīng)過分析直接概括出高度抽象的數(shù)學(xué)公式亦是一種歸納過程、一種解題的途徑。但是怎樣進(jìn)行這種歸納，這個(gè)問題太寬泛，與其說它是計(jì)算機(jī)算法的策略，還不如說它是一種數(shù)學(xué)知識(shí)和數(shù)學(xué)能力，取決于解題者本身的數(shù)學(xué)功底。我們已經(jīng)在“對(duì)應(yīng)策略”一節(jié)中，對(duì)如何將試題與數(shù)學(xué)公式對(duì)應(yīng)的問題作了一些討論，這里不再贅述。第六頁，共一百二十頁，2022年，8月28日一、遞推法

瞬息變幻的世界，每一件事物都在隨時(shí)間的流逝發(fā)生著微妙的變化。而在這紛繁的變幻中，許多現(xiàn)象的變化是有規(guī)律的，這種規(guī)律往往呈現(xiàn)出前因和后果的關(guān)系。即某種現(xiàn)象的變化結(jié)果與緊靠它前面變化的一個(gè)或一些結(jié)果緊密關(guān)聯(lián)。所謂“三歲看老”，說的就是這個(gè)道理。這一道理也正體現(xiàn)了遞推的思想。遞推關(guān)系幾乎在所有的數(shù)學(xué)分支中都有重要作用，在聯(lián)賽中更因其簡捷高效而顯示出獨(dú)特的魅力。第七頁，共一百二十頁，2022年，8月28日1.遞推關(guān)系的定義和求解方法

有一類試題，每相鄰兩項(xiàng)數(shù)之間的變化有一定的規(guī)律性，我們可將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式：

fn=g(fn-1)或者fn-1=g’(fn)

這樣就在數(shù)的序列中，建立起后項(xiàng)和前項(xiàng)之間的關(guān)系。然后從初始條件(或最終結(jié)果)入手，一步步地按遞推關(guān)系式遞推，直至求出最終結(jié)果(或初始值)。很多程序就是按這樣的方法逐步求解的。如果對(duì)一個(gè)試題，我們要是能找到后一項(xiàng)數(shù)與前一項(xiàng)數(shù)的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就比較容易解決，讓計(jì)算機(jī)一步步計(jì)算就是了。讓高速的計(jì)算機(jī)從事這種重復(fù)運(yùn)算，可真正起到“物盡其用”的效果。第八頁，共一百二十頁，2022年，8月28日

順推法就是由邊界條件出發(fā)，通過遞推關(guān)系式推出后項(xiàng)值，再由后項(xiàng)值按遞推關(guān)系式推出再后項(xiàng)值，依次遞推，直到從問題初始陳述向前推進(jìn)到這個(gè)問題的解為止。

倒推法就是在不知初始值的情況下，經(jīng)推理而獲知問題的最終解或目標(biāo)，再倒過來，推知它的初始條件。因?yàn)檫@種問題的運(yùn)算過程是一一映射的，故可分析其倒推公式。然后再從最終解或目標(biāo)出發(fā)，采用倒推手段，一步步地倒推到這個(gè)問題的初始陳述。遞推分倒推法和順推法兩種形式：第九頁，共一百二十頁，2022年，8月28日一般分析思路：

if(求解初始條件f1)//倒推

{由題意(或遞推關(guān)系)確定最終結(jié)果fn;

求出倒推關(guān)系式fi-1=g’(fi);for(i=n;i>=2;i--)fi-1=g’(fi);//從最終結(jié)果fn進(jìn)行倒推推出倒推結(jié)果f1;}else//順推{由題意(或遞推關(guān)系)確定初始值f1(邊界條件);

求出順推關(guān)系式fi=g(fi-1);for(i=2;i<=n;i++)fi=g(fi-1);//從邊界條件f1出發(fā)進(jìn)行順推推出順推結(jié)果fn;}第十頁，共一百二十頁，2022年，8月28日

由此可見，遞推算法的時(shí)間復(fù)雜度一般為W(n)。我們之所以將遞推法劃入歸納策略，是因?yàn)槌跏紬l件（或最終結(jié)果）除試題己明確給定外，都是通過對(duì)問題的整理與化簡而確定的，其遞推式也是對(duì)實(shí)際問題的分析與歸納而得到的，因此遞推本質(zhì)上屬于歸納。第十一頁，共一百二十頁，2022年，8月28日2．遞推關(guān)系的建立遞推關(guān)系中存在著三大基本問題：如何建立遞推關(guān)系，已給出的遞推關(guān)系有何性質(zhì)，以及如何求解遞推關(guān)系。其中核心問題是如何建立遞推關(guān)系。第十二頁，共一百二十頁，2022年，8月28日

建立遞推關(guān)系的關(guān)鍵在于尋找第n項(xiàng)與前面（或后面）幾項(xiàng)的關(guān)系式，以及初始項(xiàng)的值（或最終結(jié)果值）。它不是一種抽象的概念，而是針對(duì)某一具體題目或一類題目而言的。下面，我們對(duì)五種典型的遞推關(guān)系的建立作比較深入具體的討論。遞推程序一般是將遞推公式“直譯”成一重循環(huán)，模式性很強(qiáng)。

第十三頁，共一百二十頁，2022年，8月28日(1)Fibonacci數(shù)列

Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”（又稱“Fibonacci問題”)：有雌雄一對(duì)兔子，假定過兩個(gè)月便可繁殖雌雄各一的一對(duì)小兔子。問過n個(gè)月后共有多少對(duì)兔子？分析：設(shè)滿X月共有兔子Fx對(duì)，其中當(dāng)月新生的兔子數(shù)目為Nx對(duì)。第x-1個(gè)月留下的兔子數(shù)設(shè)為Ox對(duì)。則：第十四頁，共一百二十頁，2022年，8月28日

Fx=Nx+Ox

而Ox=Fx-1Nx=Ox-1=Fx-2(即第x-2個(gè)月的所有兔子到第x個(gè)月都有繁殖能力了)

所以Fx=Fx-1+Fx-2

邊界條件：F0=0，F(xiàn)1=1由上面的遞推關(guān)系可依次得到：

F2=F1+F0=1,F3=F2+F1=2,F4=F3+F2=3，…,Fibonacci數(shù)列常出現(xiàn)在比較簡單的組合計(jì)數(shù)問題中，例如【例9】極值問題、【例10】取石子問題、【例13】蜜蜂爬行等問題都可以用這種方法來解決。第十五頁，共一百二十頁，2022年，8月28日(2)Hanoi塔問題Hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖所示。第十六頁，共一百二十頁，2022年，8月28日要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)則移到c柱上：

1.一次只能移一個(gè)圓盤；

2.圓盤只能在三個(gè)柱上存放；

3.在移動(dòng)過程中，不允許大盤壓小盤。問將這n個(gè)盤子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤次？第十七頁，共一百二十頁，2022年，8月28日分析：設(shè)hn為n個(gè)盤子從a柱移到c柱所需移動(dòng)的盤次。顯然，當(dāng)n=1時(shí)，只需把a(bǔ)柱上的盤子直接移動(dòng)到c柱就可以了，故h1=1。當(dāng)n=2時(shí)，先將a柱上面的小盤子移動(dòng)到b柱上去；然后將大盤子從a柱移到c柱；最后，將b柱上的小盤子移到c柱上，共計(jì)3個(gè)盤次，故h2=3。第十八頁，共一百二十頁，2022年，8月28日以此類推，當(dāng)a柱上有n(n>=2)個(gè)盤子時(shí)，總是先借助c柱把上面的n-1個(gè)盤子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤子移動(dòng)到c柱上；總共移動(dòng)

hn=2hn-1+1邊界條件：h1=1第十九頁，共一百二十頁，2022年，8月28日(3）平面分割問題

設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。分析：設(shè)an為n條封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。由圖可得:a2-a1=2;a3-a2=4;a4-a3=6。第二十頁，共一百二十頁，2022年，8月28日從這些式子中可以看出

an-an-1=2(n-1)當(dāng)然，上面的式子只是我們通過觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來試著證明一下。當(dāng)平面上已有n-1條曲線將平面分割成an-1個(gè)區(qū)域后，第n條曲線每與其他曲線相交一次，就會(huì)增加一個(gè)區(qū)域，因?yàn)槠矫嫔弦呀?jīng)有了n-1條封閉曲線，且第n條曲線與己有的每一條閉曲線恰好相交于兩點(diǎn)，不會(huì)與任兩條曲線交于同一點(diǎn)，故平面上一共增加2(n-1)個(gè)區(qū)域，加上已有的an-1個(gè)區(qū)域，一共有an-1+2(n-1)個(gè)區(qū)域。所以本題的遞推關(guān)系是

an=an-1+2(n-1)，邊界條件是a1=2。第二十一頁，共一百二十頁，2022年，8月28日平面分割問題是競賽中經(jīng)常觸及到的一類問題，由于其靈活多變，常常讓選手感到棘手，下題是另一種平面分割問題，有興趣的讀者不妨自己先試著求一下其中的遞推關(guān)系。第二十二頁，共一百二十頁，2022年，8月28日(4)Catalan數(shù)在一個(gè)凸n邊形中，通過不相交于n邊形內(nèi)部的對(duì)角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用hn表之，hn即為Catalan數(shù)。例如五邊形有如圖所示的五種拆分方案，故h5=5。求對(duì)于一個(gè)任意的凸n邊形相應(yīng)的hn。Catalan數(shù)首先是由Euler在精確計(jì)算對(duì)凸n邊形不同的對(duì)角三角形剖分的個(gè)數(shù)問題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問題中。第二十三頁，共一百二十頁，2022年，8月28日分析：設(shè)Cn表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個(gè)凸n邊形的任意一條邊都必然是一個(gè)三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在同一直線上的三點(diǎn)可以確定一個(gè)三角形”，只要在P2，P3，…

，Pn-1，點(diǎn)中找一個(gè)點(diǎn)Pk(1<k<n)，與P1,Pn共同構(gòu)成一個(gè)三角形的三個(gè)頂點(diǎn)，就將n邊形分成了三個(gè)不相交的部分，我們分別稱之為區(qū)域①、區(qū)域②和區(qū)域③。

第二十四頁，共一百二十頁，2022年，8月28日

其中區(qū)域③必定是一個(gè)三角形，區(qū)域①是一個(gè)凸k邊形，區(qū)域②是一個(gè)凸n-k+1邊形，區(qū)域①的拆分方案總數(shù)是Ck，區(qū)域②的拆分方案數(shù)Cn-k+1，故包含△P1PkPn的n邊形的拆分方案數(shù)為CkCn-k+1種，而Pk可以是P2,P3，…

，Pn-1中任一點(diǎn)，根據(jù)加法原理，凸n邊形的三角拆分方案總數(shù)為第二十五頁，共一百二十頁，2022年，8月28日加法原理和乘法原理(1)加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共有N＝m1＋m2＋…＋mn種不同方法．

(2)乘法原理：做一件事，完成它需要分成n個(gè)步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事共有N＝m1×m2×…×mn種不同的方法．

要做一件事，完成它若是有n類辦法，是分類問題，第一類中的方法都是獨(dú)立的，因此用加法原理；做一件事，需要分n個(gè)步驟，步與步之間是連續(xù)的，只有將分成的若干個(gè)互相聯(lián)系的步驟，依次相繼完成，這件事才算完成，因此用乘法原理．第二十六頁，共一百二十頁，2022年，8月28日同時(shí)考慮到計(jì)算的方便，約定邊界條件C2=1.Catalan數(shù)是比較復(fù)雜的遞推關(guān)系，尤其在競賽的時(shí)候，選手很難在較短的時(shí)間里建立起正確的遞推關(guān)系。當(dāng)然，Catalan數(shù)類的問題也可以用搜索的方法來完成，但是，搜索的方法與利用遞推關(guān)系的方法比較起來，不僅效率低，編程復(fù)雜度也陡然提高。第二十七頁，共一百二十頁，2022年，8月28日(5）第二類stirling數(shù)

蘇格蘭數(shù)學(xué)家斯特林（J.Stirling,1692-1770）首次發(fā)現(xiàn)這些數(shù)并說明了它們的重要性。n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無一空盒，不同的方案數(shù)用s2(n,m)表示，稱為第二類Stirling數(shù)。分析：設(shè)有n個(gè)不同的球，分別用b1,b2，…

，bn表示。從中取出一個(gè)球bn，bn的放法有以下兩種：①bn獨(dú)自占一個(gè)盒子，那么剩下的球只能放在m-1個(gè)盒子中，方案數(shù)為S2(n-1，m-1)；②bn與別的球共占一個(gè)盒子，那么可以事先將b1,b2，…，bn-1這n-1個(gè)球放入m個(gè)盒子中，然后再將球bn可以放入其中一個(gè)盒子中，方案數(shù)為mS2(n-1,m)。第二十八頁，共一百二十頁，2022年，8月28日綜合以上兩種情況，可以得出第二類stirling數(shù)定理：S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)(n>1,m>=1)邊界條件為：S2(n,0)=0S2(n,1)=1，S2(n,n)=1S2(n,k)=0(k>n)

第二十九頁，共一百二十頁，2022年，8月28日第二類stirling數(shù)在競賽中較少出現(xiàn)，但在競賽中也有一些題目與其類似，甚至更為復(fù)雜。讀者不妨自己來試著建立其中的遞推關(guān)系。通過上面對(duì)五種典型的遞推關(guān)系建立過程的探討，可知對(duì)待遞推類的題目，要具體情況具體分析，通過找到某狀態(tài)與其前面狀態(tài)的聯(lián)系，建立相應(yīng)的遞推關(guān)系。第三十頁，共一百二十頁，2022年，8月28日3．遞推關(guān)系的應(yīng)用遞推關(guān)系的應(yīng)用十分廣泛，其中一個(gè)非常重要的應(yīng)用就是著名的楊輝三角（又稱“Pascal三角”。楊輝三角是根據(jù)組合公式Cnr=Cn-1r+Cn-1r-1畫出來的。很顯然，組合公式、楊輝三角都屬于遞推關(guān)系的范圍。第三十一頁，共一百二十頁，2022年，8月28日在今天的信息學(xué)競賽中，遞推關(guān)系的應(yīng)用也日趨廣泛，下面就讓我們從近年來的兩道競賽題中體會(huì)遞推關(guān)系的應(yīng)用。第三十二頁，共一百二十頁，2022年，8月28日【例13】蜜蜂爬行有一只經(jīng)過訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行，如圖所示。試求出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)

第三十三頁，共一百二十頁，2022年，8月28日分析：這是一道很典型的Fibonacci數(shù)列類題目，其中的遞推關(guān)系很明顯。由于“蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行”的限制，決定了蜜蜂到n點(diǎn)的路徑只能是從n-1點(diǎn)或n-2點(diǎn)到達(dá)的，故:fn=fn-1+fn-2(a+2<=n<=b),

邊界條件為fa＝1，fa+1＝1.第三十四頁，共一百二十頁，2022年，8月28日【例14】分割平面同一平面內(nèi)的n(n<=500）條直線，已知有p(p>=2)條直線相交于同一點(diǎn)，則這n條直線最多能將平面分割成多少個(gè)不同的區(qū)域？分析：直線的平面分割與封閉曲線的平面分割十分相似，不同之處就在于線條的曲直以及是否存在共點(diǎn)的直線。由于共點(diǎn)直線的特殊性，我們決定先考慮p條相交于一點(diǎn)的直線，然后再考慮剩下的n-p條直線。第三十五頁，共一百二十頁，2022年，8月28日首先可以直接求出p條相交于一點(diǎn)的直線將平面劃分成的區(qū)域數(shù)為2*p個(gè)然后在平面上已經(jīng)有k(k>=p)條直線的基礎(chǔ)上，加上一條直線，最多可以與k條直線相交，而每次相交都會(huì)增加一個(gè)區(qū)域,與最后一條直線相交后，由于直線可以無限延伸，還會(huì)再增加一個(gè)區(qū)域。所以fm=fm-1+m(m>P)，邊界條件在前面己經(jīng)計(jì)算過了，是fp=2*p。雖然這題看上去有兩個(gè)參數(shù)，但是在實(shí)際做題中會(huì)發(fā)現(xiàn)，本題還是屬于帶一個(gè)參數(shù)的遞推關(guān)系。第三十六頁，共一百二十頁，2022年，8月28日【例15】平面分割空間問題一個(gè)平面把空間分成獨(dú)立的兩個(gè)部分，兩個(gè)平面把空間分成4個(gè)部分。n個(gè)平面，最多能把整個(gè)空間分割成多少個(gè)部分。分析：立體空間的情況是陌生的，但是空間和平面的關(guān)系與平面和直線的關(guān)系是相似的。平面把空間分割成兩個(gè)部分，直線也把平面分割成兩個(gè)部分。于是得到了另一個(gè)與例題相類似的問題：n條直線，最多能把整個(gè)平面分割成多少個(gè)部分，如圖所示。

第三十七頁，共一百二十頁，2022年，8月28日第三十八頁，共一百二十頁，2022年，8月28日一條直線,把平面分割為兩個(gè)部分;增加一條直線，它與第一條直線相交,被分為兩段射線，每一段射線又把所在的區(qū)域分成兩部分;因此增加了2個(gè)部分。再增加一條直線，它與前兩條直線相交，被分為三段，每一段又把所在區(qū)域分成兩部分;共增加了3個(gè)部分。由此類推，設(shè)前k-1條直線共把平面分為ak-1個(gè)部分。加入第k條直線，與前k-1條直線相交，被分為k段，每一段把所在區(qū)域分為兩部分；總共增加了k部分；總共有ak-1+k個(gè)部分。于是得到了遞推關(guān)系:第三十九頁，共一百二十頁，2022年，8月28日a1=2;ak=ak-1+k;即ak=1+k*(1+k)/2于是直線分割平面的問題就解決了。既然空間和平面，與平面和直線的關(guān)系相似，那么直接把平面換成空間，把直線換成平面，就可以直接用以上的過程來證明未知的問題了嗎？顯然是不可以的，這種僅僅根據(jù)主觀的相似性得出的機(jī)械模仿是錯(cuò)誤的。第四十頁，共一百二十頁，2022年，8月28日但是如果仔細(xì)分析一下錯(cuò)誤的原因，將會(huì)發(fā)現(xiàn)問題的關(guān)鍵:線線相交得到的是交點(diǎn),面面相交得到的是直線,k個(gè)點(diǎn)把直線分成k+1個(gè)部分,而k條直線則不是簡單的把平面分成k+1個(gè)部分。事實(shí)上,k條直線最多把平面分成ak個(gè)部分！因此兩個(gè)問題真正的相似之處在于，一個(gè)為了計(jì)算直線把平面分割成幾部分，先計(jì)算這條直線被點(diǎn)（線線交點(diǎn)）分割成幾部分，把二維的問題化為一維的問題；另一個(gè)要計(jì)算平面把空間分割成幾部分，先計(jì)算這個(gè)平面被線（面面交線）分割成幾部分，把三維的問題化為二維的問題。而二維的問題是已經(jīng)被解決了的，于是反過來，三維的問題也解決了。第四十一頁，共一百二十頁，2022年，8月28日

同樣是利用數(shù)學(xué)歸納法：一個(gè)平面把空間分割成兩部分；設(shè)前k-1個(gè)平面共把空間分割成bk-1個(gè)部分。加入第k個(gè)平面后，與前k-1個(gè)平面相交，共有k-1條交線。k-1條交線把這個(gè)平面分為幾塊呢？這買際上就是剛剛解決過的回題：k-1條直線，把平面分割成：

ak-1=1+k*(1+k)/2

分別把所在原來空間一分為二，總共增加了ak-1個(gè)部分，于是平面總共把空間分割成個(gè)部分。于是得到了遞推關(guān)系：第四十二頁，共一百二十頁，2022年，8月28日利用這一遞推關(guān)系來編寫程序，不難求出bn，而且即便對(duì)很大的n，程序的運(yùn)算速度仍然是很快的。（當(dāng)然，也可以計(jì)算出bn的通項(xiàng)公式:第四十三頁，共一百二十頁，2022年，8月28日二、遞歸法設(shè)一個(gè)未知函數(shù)f，用其自身構(gòu)成的已知函數(shù)g來定義：

f(n)=g(n,f(n-1))n>0f(0)=an=0為了定義f(n)，必須先定義f(n-1),為了定義f(n-1)，又必須先定義f(n-2)…,上述這種用自身的簡單情況來定義自己的方式稱為遞歸定義。一個(gè)遞歸定義必須是有確切含義的，也就是說，必須一步比一步簡單，最后是有終結(jié)的，決不能無限循環(huán)下去。在f(n)的定義中，當(dāng)n為0時(shí)定義一個(gè)已知數(shù)a，是最簡單的情況，稱為遞歸邊界，它本身不再使用遞歸的定義。第四十四頁，共一百二十頁，2022年，8月28日

與遞推一樣，每一個(gè)遞歸定義都有其邊界條件。但不同的是，遞推是由邊界條件出發(fā)，通過遞推公式求f(n)的值，從邊界到求解的全過程十分清楚；而遞歸則是從函數(shù)自身出發(fā)來達(dá)到邊界條件。在通往邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果保存在棧區(qū)，直至求出遞歸邊界值f(0)=a。然后返回調(diào)用函數(shù)。返回過程中，中間結(jié)果相繼出?；謴?fù)，

f(1)=g(1,a)f(2)=g(2,f(1))直到f(n)=g(n,f(n-1))

描述遞歸定義的函數(shù)或求解遞歸問題的過程稱為遞歸算法。一個(gè)遞歸算法，本質(zhì)上是將較復(fù)雜的處理歸結(jié)為簡單處理，直到最簡單的處理。第四十五頁，共一百二十頁，2022年，8月28日

從實(shí)際問題中抽象遞歸定義和邊界條件的過程是一種歸納，通過這種歸納方式能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡捷精煉，增加可讀性。特別是在難于找到從邊界到解的全過程的情況下，如果把問題推進(jìn)一步，其結(jié)果仍維持原問題的關(guān)系，則采用遞歸算法編程比較合適。但遞歸算法也有致命的缺點(diǎn)，其執(zhí)行的效率比較低，尤其在邊界條件設(shè)置不當(dāng)?shù)那闆r，極有可能陷入死循環(huán)或者內(nèi)存溢出的窘境。第四十六頁，共一百二十頁，2022年，8月28日遞歸算法適用的一般場合為：(1)數(shù)據(jù)的定義形式按遞歸定義。這類遞歸問題可直接轉(zhuǎn)化為遞推算法，遞歸邊界作為遞推的邊界條件。(2)數(shù)據(jù)之間的關(guān)系(即數(shù)據(jù)結(jié)構(gòu))按遞歸定義。如樹的遍歷，圖的搜索等。(3)有些問題本身沒有明顯的遞歸結(jié)構(gòu)，但使用遞歸求解比其他方法更簡單。如遞歸的分治策略。對(duì)于(2)、(3)，可利用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法，但結(jié)構(gòu)不如遞歸算法簡單清晰，可讀性較差。第四十七頁，共一百二十頁，2022年，8月28日

編寫遞歸程序時(shí)應(yīng)注意如下幾個(gè)問題：(1)問題的遞歸定義，即如何用自身的簡單情況定義自己；(2)遞歸邊界，即遞歸至哪個(gè)邊界值后開始回溯；(3)參與遞歸運(yùn)算的變量有哪些，其中哪些作為值參，哪些作為局部變量。如果有全局變量參與遞歸運(yùn)算的話(初始值由主程序傳入，受內(nèi)存限制不便作為值參)，回溯過程中必須恢復(fù)其遞歸前狀態(tài)。第四十八頁，共一百二十頁，2022年，8月28日【例16】計(jì)算交點(diǎn)數(shù)

在平面上有n條直線，且無三線共點(diǎn)。問這些直線能有多少種不同的交點(diǎn)數(shù)？輸入：n

輸出：以下若干行列出所有相交方案。其中每一行為某一方案的交點(diǎn)個(gè)數(shù)。分析：我們將n條直線排成一個(gè)序列。直線2與直線1最多有一個(gè)交點(diǎn)；直線3與直線1和直線2最多有2個(gè)交點(diǎn)，…，直線n與其他n-1條直線最多有n-1個(gè)交點(diǎn)。由此得出n條直線互不平行且無三線交于一點(diǎn)的最多交點(diǎn)數(shù)中1+2+，…+(n-1)=n*(n-1)/2.第四十九頁，共一百二十頁，2022年，8月28日設(shè)第五十頁，共一百二十頁，2022年，8月28日我們來具體分析n=4的情況(1)四條直線全部平行，無交點(diǎn)，g[0]=1(2)其中三條(n-1)直線平行，交點(diǎn)數(shù)為

(n-1)x1+0=3,g[3]=1(3)其中兩條(n-2)直線平行，這兩條直線與另外兩條直線之間的交點(diǎn)數(shù)為(n-2)x2=4而另外兩條直線本身既可能平行也可能相交，因此交點(diǎn)數(shù)分別為：當(dāng)平行時(shí)(n-2)x2+0=4g[4]=1

當(dāng)相交時(shí)(n-2)x2+1=5g[5]=1(4)四條直線互不平行，交點(diǎn)數(shù)為：

1+2+3=6g[6]=1

即n=4時(shí)，有0、3、4、5、6個(gè)不同的交點(diǎn)數(shù)

第五十一頁，共一百二十頁，2022年，8月28日由此得出：m條直線的交點(diǎn)方案=r條平行線與(m-r)條直線交叉的交點(diǎn)數(shù)+(m-r)條直線本身的交點(diǎn)方案=(m-r)r+(m-r)條直線本身的交點(diǎn)數(shù)(1<=r<=m)顯然，計(jì)算不同交點(diǎn)數(shù)的問題是遞歸的第五十二頁，共一百二十頁，2022年，8月28日可以描述成如下遞歸算法：//m是直線數(shù)，j是交點(diǎn)數(shù)voidcross(intm,intj){if(m>0) //若直線存在，則遞歸計(jì)算所有的交叉情況

for(intr=m;r>=1;r--)cross(m-r,j+r*(m-r));else//否則確定m條直線存在j個(gè)交點(diǎn)

g[j]=1;}第五十三頁，共一百二十頁，2022年，8月28日計(jì)算和輸出n條直線的交點(diǎn)方案如下：#include<iostream>usingnamespacestd;constintMAX=10000;staticintg[MAX];voidmain(){ intn,k,total=0; cin>>n; k=n*(n-1)/2; cross(n,0); for(inti=0;i<=k;i++) if(g[i]==1){total++;cout<<i<<endl;}}第五十四頁，共一百二十頁，2022年，8月28日三、制定目標(biāo)

有些問題看似棘手，主要是沒有找到解決問題的路子，或者說目標(biāo)不明確。一旦建立了評(píng)判好壞的標(biāo)準(zhǔn)(目標(biāo)函數(shù)或者目標(biāo)方案)，求解問題的算法也就自然而然地產(chǎn)生了。關(guān)鍵是建立標(biāo)準(zhǔn)。而這個(gè)標(biāo)準(zhǔn)是通過對(duì)實(shí)際問題的分析與歸納得到的。因此，我們將之劃入歸納的范疇。第五十五頁，共一百二十頁，2022年，8月28日【例17】最優(yōu)分解方案

把正整數(shù)n分解成若干個(gè)互不相等的自然數(shù)的和，且使這些自然數(shù)的乘積最大。請(qǐng)你編寫一個(gè)算法，由鍵盤輸入n,求滿足條件的分解方案。輸入：n(3<=n<=1000)輸出：乘積分析：如何把正整數(shù)n分解成若干互不相等的自然數(shù)的和，且使這些自然數(shù)的乘積最大呢？如果我們對(duì)這個(gè)問題不探究解析方法而去盲目搜索所有分解方案的話，則代價(jià)相當(dāng)大。但是如果我們一旦耐心地對(duì)問題認(rèn)真思考一番，是不難得出其中隱含著的數(shù)學(xué)規(guī)律的。設(shè)：第五十六頁，共一百二十頁，2022年，8月28日由于1<=a1<a2<…<an，因此s/n>1。很明顯，要使得乘積a1×a2×

…×an最大，則必須使得項(xiàng)數(shù)n最大，且相鄰兩數(shù)ai+1-ai的差最小，這就是解決問題的目標(biāo)方案。第五十七頁，共一百二十頁，2022年，8月28日為了達(dá)到這個(gè)目標(biāo)，我們不妨設(shè)a1=2(因?yàn)閍1=1時(shí),a1在乘式中無意義），先求出：

n=2+3+4+,…,+ak+ak+1ak>=ak+1這種分解方案的項(xiàng)數(shù)無疑最多。問題是要保證ak+1<=ak,ak+1要么為1,要么重復(fù)其中某一項(xiàng)，因此必須撤去。為了保證撤去ak+1后的各個(gè)自然數(shù)依然互不相等，其和還是等于n且乘積最大，我們將ak+1盡量平均地加在后幾項(xiàng)。并盡可能使得相鄰兩數(shù)的差不超過2第五十八頁，共一百二十頁，2022年，8月28日①若ak+1=1,由于1x2x,…,xak<2x3x,…,x(ak+1)，因此ak+1=1加到ak上；②若1<ak+1<ak,我們從ak出發(fā)，依次向尾部ak+1個(gè)數(shù)加1;③若ak+1=ak,則ak加上2,其余k-1個(gè)數(shù)依次加1;當(dāng)然，還必須考慮一個(gè)例外情況：當(dāng)n=3或n=4時(shí)，只能分解出一個(gè)表達(dá)式：

3=1+2mul=1x2=24=1+3mul=1x3=3由此可見，上述目標(biāo)方案是分解自然數(shù)的依據(jù)。第五十九頁，共一百二十頁，2022年，8月28日有了這個(gè)目標(biāo)方案，相應(yīng)的算法也就可以設(shè)計(jì)出來了。#include<iostream>usingnamespacestd;constintMAX=1000;staticinta[MAX];voidmain(){intn,mul=1;cin>>n;if((n==3)||(n==4))mul=1*(n-1);

//當(dāng)n=3或4時(shí)，輸出分解方案。

else第六十頁，共一百二十頁，2022年，8月28日{(diào)intk=1;a[k]=2;n=n-a[k];//從2開始分解

while(n>a[k])//分解直到a[k+1]<=a[k] {k++;a[k]=a[k-1]+1;n=n-a[k];} if(n==1){a[k]++;n--;//a[k+1]=1} else {if(n==a[k])//a[k+1]=a[k] {a[k]++; n--;}

//1<a[k+1]<a[k] for(inti=0;i<=n-1;i++)a[k-i]++;} for(inti=1;i<=k;i++)mul=mul*a[i]; }cout<<mul;}第六十一頁，共一百二十頁，2022年，8月28日四、貪心法

和前面所講的遞推法相仿，貪心法也是從問題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)推進(jìn)。但不同的是，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪心選擇，不斷地將問題實(shí)例歸納為更小的相似的子問題，并期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個(gè)全局最優(yōu)解。對(duì)于貪心法，我們并不陌生。例如求最小生成樹、求單源最短路徑使用的算法策略實(shí)際上就是貪心法。

第六十二頁，共一百二十頁，2022年，8月28日

貪心法建議通過一系列步驟來構(gòu)造問題的解，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問題的完整解為止。這個(gè)問題的核心是，所做的每一步選擇都必須滿足以下條件：可行的：即它必須滿足問題的約束。局部最優(yōu)：它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇不可取消：即選擇一旦做出，在算法的后面步驟中就無法改變。在每一步中，它要求“貪婪”地選擇最佳操作，并希望通過一系列局部的最佳選擇，能夠產(chǎn)生一個(gè)整個(gè)問題的（全局的）最佳解。第六十三頁，共一百二十頁，2022年，8月28日

那么如何證明按貪心選擇得出的解是最優(yōu)解呢？有兩種方法：(1)對(duì)貪心選擇進(jìn)行數(shù)學(xué)分析，從理論上證明是最優(yōu)的。(2)構(gòu)造一個(gè)最優(yōu)解，然后對(duì)該解進(jìn)行修正，使其第一步為一個(gè)貪心選擇，證明總是存在一個(gè)以貪心選擇開始的求解方案，然后證明經(jīng)過若干次貪心選擇后可以得出一個(gè)最優(yōu)解。第二種證明方法相對(duì)比較容易。由于貪心選擇的設(shè)計(jì)及其產(chǎn)生最優(yōu)解的證明是對(duì)實(shí)際問題分析歸納的結(jié)果.因此,我們將貪心法列為一種歸納策略。第六十四頁，共一百二十頁，2022年，8月28日【例18】活動(dòng)選擇

假設(shè)有一個(gè)需要使用某一資源的n個(gè)活動(dòng)組成的集合S={1,…,n}。該資源一次只能被一個(gè)活動(dòng)所占用，每一個(gè)活動(dòng)有一個(gè)開始時(shí)間Si和結(jié)束時(shí)間Fi(Si<=Fi)。若Si>=Fj或者Sj>=Fi，則活動(dòng)i和活動(dòng)j兼容。選擇由互相兼容的活動(dòng)組成的最大集合。 輸入：n S1F1

… SnFn

輸出：占用時(shí)間t

最大集合A中的活動(dòng)序號(hào)第六十五頁，共一百二十頁，2022年，8月28日分析：我們使用盡可能逼近目標(biāo)的貪心策略來選擇活動(dòng)，即每一步總是選擇這樣一個(gè)活動(dòng)來占用資源―它能夠使得余下的未調(diào)度時(shí)間最大化，使得兼容的活動(dòng)盡可能多。為了達(dá)到這個(gè)目的，我們將n個(gè)待選活動(dòng)按結(jié)束時(shí)間遞增的順序排列：

F1<=F2<=…<=Fn

遞增序列中的活動(dòng)1進(jìn)入集合A。然后依次分析序列中的活動(dòng)2到活動(dòng)n，將那些與A中活動(dòng)兼容的活動(dòng)送入集合A。第六十六頁，共一百二十頁，2022年，8月28日例如活動(dòng)開始時(shí)間結(jié)束時(shí)間

13521431214481250668117610857938105911213第六十七頁，共一百二十頁，2022年，8月28日#include<iostream>usingnamespacestd;constintN=11;//活動(dòng)序號(hào)intno[N]={1,2,3,4,5,6,7,8,9,10,11};//開始時(shí)間ints[N]={3,1,12,8,0,8,6,5,3,5,2};//結(jié)束時(shí)間intf[N]={5,4,14,12,6,11,10,7,8,9,13};第六十八頁，共一百二十頁，2022年，8月28日voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}//選擇排序voidsort(){for(inti=0;i<N-1;i++) {intmin=i; for(intj=i+1;j<N;j++) if(f[min]>f[j])min=j; swap(f[min],f[i]); swap(no[min],no[i]); swap(s[min],s[i]); }}第六十九頁，共一百二十頁，2022年，8月28日voidmain(){staticinta[N];//a是兼容集合

intt=0;//t是占用時(shí)間

sort();//按結(jié)束時(shí)間遞增的順序排序

intk=0;intj=0;a[k]=no[0];//初始活動(dòng)表為NO[0] for(inti=1;i<N;i++) {//若遞增序列中的活動(dòng)i與A集合中的活動(dòng)兼容

if(s[i]>=f[j]){k++;a[k]=no[i];t=f[i];j=i;} }cout<<t<<endl;for(i=0;i<=k;i++)cout<<a[i]<<"";}第七十頁，共一百二十頁，2022年，8月28日

貪心選擇的過程t=14a={2,8,6,3}第七十一頁，共一百二十頁，2022年，8月28日我們使用第二種方法證明按照這個(gè)貪心選擇的解一定是最優(yōu)的：(1)構(gòu)造一個(gè)最優(yōu)解，然后對(duì)該解進(jìn)行修正，使其第一步為一個(gè)貪心選擇，證明總是存在一個(gè)以貪心選擇開始的求解方案。設(shè)最優(yōu)解為a。第一個(gè)選中的活動(dòng)為k(k不等于1)。如果另一個(gè)解b開始于貪心選擇活動(dòng)1(b=(a-{k})U{1})。因?yàn)閒1<=fk，所以b中的活動(dòng)是兼容的。又因?yàn)閎與a的活動(dòng)數(shù)相同，所以b也是最優(yōu)的。由此證明總存在一個(gè)以貪心選擇開始的最優(yōu)調(diào)度。第七十二頁，共一百二十頁，2022年，8月28日(2)證明經(jīng)過若干次貪心選擇后可以得出一個(gè)最優(yōu)解當(dāng)我們作出了對(duì)活動(dòng)1的貪心選擇后，原問題就變成在活動(dòng)2至活動(dòng)n中找與活動(dòng)1兼容的那些活動(dòng)的子問題。也就是說，如果問題a為原問題的一個(gè)最優(yōu)解，則a’=a-{1}就是活動(dòng)選擇問題s’的一個(gè)最優(yōu)解。為什么會(huì)這樣呢？如果我們能找到s的一個(gè)含有比a’更多活動(dòng)的解b’則將活動(dòng)1加入了b’,就得到s的一個(gè)包含比a更多活動(dòng)的解b,這就與a的最優(yōu)性相矛盾。所以在每一次貪心選擇后,留下的是一個(gè)與原問題具有相同形式的最優(yōu)化問題.通過對(duì)所做選擇次數(shù)的歸納可以證明,對(duì)每一步進(jìn)行貪心選擇就可得到一個(gè)最優(yōu)解.由此得出，按照這個(gè)貪心選擇得出的解一定是最優(yōu)的。第七十三頁，共一百二十頁，2022年，8月28日2801【例19】打包（Packaging)某個(gè)工廠生產(chǎn)出的產(chǎn)品都要被打包放入正四棱柱的盒子內(nèi)。所有盒子的高度都為h,但底面的尺寸不同，可以為1x1,2x2,3x3,4x4,5x5,或6x6，如圖所示。第七十四頁，共一百二十頁，2022年，8月28日這些盒子將被放入高度為h,底面尺寸為6x6的箱子里,送到消費(fèi)者手中。為了降低運(yùn)送成本，工廠希望盡量減少箱子的數(shù)量。如果有一個(gè)好的算法，能使箱子的數(shù)量降到最低，這將給工廠節(jié)省不少資金。請(qǐng)你寫一個(gè)這樣的程序。輸入：六個(gè)非負(fù)整數(shù)a1,a2,a3,a4,a5,a6。它們分別為底面尺寸為1x1,2x2,3x3,4x4,5x5,6x6的盒子的個(gè)數(shù)。輸出：一個(gè)數(shù)b，即箱子的最少個(gè)數(shù)。第七十五頁，共一百二十頁，2022年，8月28日分析：讓我們來看看可供選擇的裝箱方法：(1)如果有6x6的盒子，則將它放入箱子，這個(gè)箱子就滿了，該過程直到6x6的盒子全部裝箱為止；(2)如果有5x5的盒子，則將它放入箱子，這個(gè)箱子還有空余，可以放入盡可能多的1x1的盒子，這個(gè)過程的結(jié)束條件是5x5的盒子全部裝箱，并且1x1的盒子全部裝箱或者箱子全部裝滿；(3)如果有4x4的盒子，箱子中的剩余空間可以放2x2的盒子，如果還有剩余，則放1x1的盒子，這個(gè)過程直到4x4的盒子全部裝箱，并且剩余空間被充分利用；

……第七十六頁，共一百二十頁，2022年，8月28日簡而言之就是每次找出最大的盒子放入當(dāng)前的箱子中，直到無法再放；再拿一個(gè)空箱繼續(xù)這一過程，直到所有的盒子都被裝箱。解決這一類問題我們通常采用貪心算法。下面我們使用第一種方法來證明對(duì)于打包問題，貪心法可以得出最優(yōu)解。設(shè)要裝下a1個(gè)1x1的盒子,a2個(gè)2x2的盒子，…

…

，a6個(gè)6x6的盒子需要的箱子數(shù)為f(a1,a2,a3,a4,a5,a6)個(gè)。由前面的分析可知：第七十七頁，共一百二十頁，2022年，8月28日(1)由每一個(gè)6x6的盒子都剛好放入一個(gè)6x6的箱子可得等式:f(a1,a2,a3,a4,a5,a6)=f(a1,a2,a3,a4,a5,0)+a6(2)己知放置每一個(gè)5x5的盒子都需要一個(gè)箱子，但每個(gè)箱子放入一個(gè)5x5的盒子后還有6x6-5x5=11個(gè)單位的空間，而這些空間只能放1x1的盒子，最多放11個(gè),可得等式：f(a1,a2,a3,a4,a5,0)=f(max{0,a1-11*a5},a2,a3,a4,0,0)+a5第七十八頁，共一百二十頁，2022年，8月28日(3)已知放置每一個(gè)4x4的盒子都需要一個(gè)箱子，之后還有6x6-4x4=20個(gè)單位的空間。這些空間恰好可以放入5個(gè)2x2的盒子，或20個(gè)1x1的盒子。根據(jù)盡可能先放大盒子的貪心策略，我們盡量先放2x2的盒子。放置a4個(gè)4x4的盒子需要a4個(gè)箱子，剩余5*a4個(gè)2x2的空間。

第七十九頁，共一百二十頁，2022年，8月28日若a2>=5*a4,則這些空間全部用掉，否則剩下的空間還可以“見縫插針”地放入1x1的盒子。由此可得等式：第八十頁，共一百二十頁，2022年，8月28日(4)已知每個(gè)箱子可以放4個(gè)3x3的盒子。這樣4個(gè)4個(gè)放完后，可能還剩余0,1,2,3個(gè)3x3的盒子。與放置4x4的盒子時(shí)同樣的原理，還是先放2x2的盒子,再放1x1的盒子。第八十一頁，共一百二十頁，2022年，8月28日在這4種情況下分別還能放0,1,3,5個(gè)2x2的盒子。剩余的空間再放入1x1的盒子。第八十二頁，共一百二十頁，2022年，8月28日(5)一個(gè)箱子可放9個(gè)2x2的盒子，放完2x2的盒子后，多余的空間放1x1的盒子。等式如下：第八十三頁，共一百二十頁，2022年，8月28日(6)放置1x1的盒子時(shí)有關(guān)系式(圖j)：這六個(gè)等式的順序即為貪心策略。由此證明貪心法可以求得最優(yōu)解第八十四頁，共一百二十頁，2022年，8月28日intpack(inta1,inta2,inta3,inta4,inta5,inta6){intc=a6;c=c+a5;//加上放入6x6,5X5的盒子數(shù)

a1=max(0,a1-11*a5);c=c+a4; if(a2>=5*a4)a2=a2-5*a4;else{a1=max(0,a1-(20*a4-4*a2));a2=0;}第八十五頁，共一百二十頁，2022年，8月28日 if(a3%4==0)c=c+a3/4;elsec=c+a3/4+1; if(a3%4==3){a1=max(0,a1-(9-4*min(1,a2)));a2=max(0,a2-1);}elseif(a3%4==2){a1=max(0,a1-(18-4*min(3,a2)));a2=max(0,a2-3);}else{a1=max(0,a1-(27-4*min(5,a2)));a2=max(0,a2-5);}//a3%4==1第八十六頁，共一百二十頁，2022年，8月28日if(a2%9==0)c=c+a2/9;elsec=c+a2/9+1;if(a2%9!=0)a1=max(0,a1-(36-4*(a2%9)));

if(a1%36==0)c=c+a1/36;elsec=c+a1/36+1;returnc;}第八十七頁，共一百二十頁，2022年，8月28日#include<iostream>usingnamespacestd;inlineintmax(inta,intb){returna>b?a:b;}inlineintmin(inta,intb){returna<b?a:b;}voidmain(){ inta1,a2,a3,a4,a5,a6; cin>>a1>>a2>>a3>>a4>>a5>>a6; cout<<pack(a1,a2,a3,a4,a5,a6);}第八十八頁，共一百二十頁，2022年，8月28日#include<iostream>//優(yōu)化#include<cmath>usingnamespacestd;intmain(){ intc,a1,a2,a3,a4,a5,a6,x,y; intu[4]={0,5,3,1};//當(dāng)放3*3產(chǎn)品時(shí)剩余放2*2數(shù) while(cin>>a1>>a2>>a3>>a4>>a5>>a6) {if((a1==0)&&(a2==0)&&(a3==0)&&(a4==0)&&(a5==0)&&(a6==0))break; c=a6+a5+a4+ceil(a3/4.0);y=5*a4+u[a3%4]; if(a2>y)c+=ceil((a2-y)/9.0); x=36*c-36*a6-25*a5-16*a4-9*a3-4*a2; if(a1>x)c+=ceil((a1-x)/36.0); cout<<c<<endl; }return0;}第八十九頁，共一百二十頁，2022年，8月28日貪心算法的基本要素可以用貪心算法求解的問題一般具有兩個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)1.貪心選擇性質(zhì)：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。貪心算法所做的貪心選擇可以依賴于以往所做過的選擇，但決不依賴于將來所做的選擇，也不依賴于子問題的解。第九十頁，共一百二十頁，2022年，8月28日

貪心算法通常以自頂向下的方式進(jìn)行，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2.最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。第九十一頁，共一百二十頁，2022年，8月28日本節(jié)作業(yè)一、簡要回答如下問題：簡述歸納過程步驟？遞推方法一般分析思路是什么？遞歸算法適用的一般場合是什么？簡述貪心算法的基本要素第九十二頁，共一百二十頁，2022年，8月28日二、根據(jù)題意，建立如下問題的遞推公式或遞歸公式？(1)Fibonacci數(shù)列(2)Hanoi塔問題(3)封閉曲線分割平面問題(4)Catalan數(shù)(5)第二類stirling數(shù)【例13】蜜蜂爬行【例14】直線分割平面【例15】平面分割空間問題第九十三頁，共一百二十頁，2022年，8月28日第四節(jié)、模擬策略

在自然界和日常生活中，許多現(xiàn)象具有不確定的性質(zhì)，有些問題甚至很難建立數(shù)學(xué)模型，或者很難用計(jì)算機(jī)建立遞推、遞歸、枚舉、回溯等算法。在這種情況下，一般采用模擬策略。所謂模擬策略就是模擬某個(gè)過程，通過改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計(jì)。第九十四頁，共一百二十頁，2022年，8月28日模擬題沒有固定的模式，一般形式有兩種：(1)隨機(jī)模擬：題目給定或者隱含某一概率。設(shè)計(jì)者利用隨機(jī)函數(shù)和取整函數(shù)設(shè)定某一范圍的隨機(jī)值，將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬的數(shù)學(xué)模型展開算法設(shè)計(jì)。由于解題過程借助了計(jì)算機(jī)的偽隨機(jī)數(shù)發(fā)生器，其隨機(jī)的意義要比實(shí)際問題中真實(shí)的隨機(jī)變量稍差一些，因此模擬效果有不確定的因素。第九十五頁，共一百二十頁，2022年，8月28日(2)過程模擬：題目不給出概率，要求編程者按照題意設(shè)計(jì)數(shù)學(xué)模型的各種參數(shù)，觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計(jì)。模擬效果完全取決于過程模擬的真實(shí)性和算法的正確性，不含任何不確定因素。 由于過程模擬的結(jié)果無二義性，因此競賽大都采用過程模擬。第九十六頁，共一百二十頁，2022年，8月28日模擬的解題方法一般有三種類型：(1)直敘式模擬(2)篩選法模擬(3)構(gòu)造法模擬第九十七頁，共一百二十頁，2022年，8月28日一、直敘式模擬

直敘式模擬，即按照試題要求展開模擬過程。編程者要忠實(shí)于原題，認(rèn)真審題，千萬不要疏漏任何條件，精心設(shè)計(jì)方便模擬的數(shù)據(jù)結(jié)構(gòu)。直敘式模擬的難度取決于模擬對(duì)象所包含的動(dòng)態(tài)變化的屬性個(gè)數(shù)，動(dòng)態(tài)屬性愈多，則難度愈大。第九十八頁，共一百二十頁，2022年，8月28日【例19】約瑟夫問題

有n只猴子，按順時(shí)針方向圍成一圈選大王（編號(hào)從1到n），從第1號(hào)開始報(bào)數(shù)，一直數(shù)到m，數(shù)到m的猴子退出圈外，剩下的猴子再接著從1開始報(bào)數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時(shí)，這個(gè)猴子就是猴王，編程求輸入n，m后，輸出最后猴王的編號(hào)。Input:每行是用空格分開的兩個(gè)整數(shù)，第一個(gè)是n,第二個(gè)是m(0<m,n<=300)。最后一行是：00Output:對(duì)于每行輸入數(shù)據(jù)（最后一行除外)，輸出數(shù)據(jù)也是一行，即最后猴王的編號(hào)

第九十九頁，共一百二十頁，2022年，8月28日SampleInput621248300SampleOutput517第一百頁，共一百二十頁，2022年，8月28日解題思路1：用數(shù)組loop來存放n個(gè)數(shù)，相當(dāng)于n個(gè)數(shù)排成的圈，用整型變量nPtr指向當(dāng)前數(shù)到的數(shù)組元素，相當(dāng)于人的手指，劃掉一個(gè)數(shù)就將該數(shù)置0，在數(shù)數(shù)時(shí)，要跳過為0的元素。當(dāng)nPtr指向最后一個(gè)元素時(shí)再數(shù)下一個(gè)時(shí)則指向數(shù)組的頭一個(gè)元素。第一百零一頁，共一百二十頁，2022年，8月28日#include<iostream.h>constintMAX=300;intloop[MAX];voidmain(){intn,m,i;while(1){cin>>n>>m; if(n==0)break; for(i=0;i<n;i++)loop[i]=i+1; intnPtr=0;for(i=0;i<n;i++){intnCount=0;while(nCount<m){ while(loop[nPtr]==0)nPtr=(nPtr+1)%n; nCount++;nPtr=(nPtr+1)%n;}nPtr--;if(nPtr<0)nPtr=n-1;if(i==n-1)cout<<loop[nPtr];loop[nPtr]=0;}}}第一百零二頁，共一百二十頁，2022年，8月28日采用循環(huán)鏈表實(shí)現(xiàn)如下#include<iostream.h>采用循環(huán)鏈表實(shí)現(xiàn)structMonkey{ intID;Monkey*next;};intmain(){ Monkey*link,*monkey,*lastMonkey; intn,m,count; cin>>n>>m;link=NULL; for(inti=0;i<n;i++) {monkey=newMonkey; monkey->ID=i+1; if(link==NULL)link=lastMonkey=monkey; else{lastMonkey->next=monkey; lastMonkey=monkey;} } lastMonkey->next=link;

第一百零三頁，共一百二十頁，2022年，8月28日count=1;while(link!=NULL){if(link->next==link){cout<<link->ID; deletelink;break;} if(count==m-1) {monkey=link->next; link->next=monkey->next; deletemonkey; count=0; } link=link->next; count++;}return0;}第一百零四頁，共一百二十頁，2022年，8月28日【例20】DAM語言

有個(gè)機(jī)器執(zhí)行一種DAM語言。該機(jī)器有一個(gè)棧，初始時(shí)棧里只有一個(gè)元素x，隨著DAM語言程序的執(zhí)行，棧里的元素會(huì)發(fā)生變化。DAM語言有三種指令：D指令：把棧頂元素復(fù)制一次加到棧頂。A指令：把棧頂元素取出，加到新的棧頂元素中。M指令：把棧頂元素取出，乘到新的棧頂元素中。第一百零五頁，共一百二十頁，2022年，8月28日

如果執(zhí)行A或M指令的時(shí)候棧內(nèi)只有一個(gè)元素，則機(jī)器會(huì)發(fā)出錯(cuò)誤信息。如果程序無誤，那么執(zhí)行完畢以后，棧頂元素應(yīng)該是X的多項(xiàng)式，例如，程序DADDMA的執(zhí)行情況為（棧內(nèi)元素按照從底到頂?shù)捻樞驈淖笾劣遗帕?，用逗?hào)隔開）：第一百零六頁，共一百二十頁，2022年，8月28日給出一段DAM程序，求出執(zhí)行完畢后棧頂元素。輸入：輸入僅一行，包含一個(gè)不空的字符串s，長度不超過12，代表一段DAM程序。輸入程序保證合法且不會(huì)導(dǎo)致錯(cuò)誤。輸出：僅輸出一行，即棧頂多項(xiàng)式。須按照習(xí)慣寫法降冪輸出，即等于1的系數(shù)不要打印，系數(shù)為0的項(xiàng)不打印，第一項(xiàng)不打印正號(hào)。一次方不打印“^1”。分析：本題是一道“直敘式模擬”題，即按照DAM指令的順序模擬執(zhí)行過程。在模擬的時(shí)候有些問題是需要注意的：第一百零七頁，共一百二十頁，2022年，8月28日(1)多項(xiàng)式的表示方式。有的選手或許會(huì)覺得本題沒有說明次數(shù)的上限，因此最好用鏈表做。其實(shí)完全沒有必要。由于指令不超過12條，而D指令和A、M指令總數(shù)應(yīng)該相等，因此最多有6條M指令，因此次數(shù)上限為26=64。我們可以用數(shù)組來表示多項(xiàng)式，既方便又不會(huì)導(dǎo)致時(shí)間和空間上的問題。(2)本題也沒有說明系數(shù)的最大值。稍微細(xì)心的選手會(huì)發(fā)現(xiàn)：它最大可能為232,未超過長整數(shù)的范圍，不存在非得用高精度的必要。第一百零八頁，共一百二十頁，2022年，8月28日#include<iostream.h>#include<string.h>voidmain(){staticintdegree[13];//存儲(chǔ)系數(shù)個(gè)數(shù)的棧

staticlongco[13][65];//存儲(chǔ)多項(xiàng)式的棧

longtmp[65];//系數(shù)序列

chars[13];//DAM程序

inti,j; inttop=1;//棧頂指針

degree