信息學(xué)奧林匹克競賽輔導(dǎo)課件-歸納策略培訓(xùn)資料

第三節(jié)、歸納(guīnà)策略如果說對應(yīng)策略的核心是舉一反三、觸類旁通地對已經(jīng)解決(jiějué)的類似問題和有關(guān)事實(shí)作聯(lián)想，外推出事物間聯(lián)系的話，那么歸納策略則是通過列舉試題本身的特殊情況，經(jīng)過深入分析，最后概括出事物內(nèi)在的一般規(guī)律，并得到一種高度抽象的解題模型。第一頁，共121頁。歸納法要比搜索(sōusuǒ)的方法（例如以后將講解的枚舉法、回溯法等）更能反映問題的本質(zhì)。但是并不是所有實(shí)際問題都可以總結(jié)歸納出一般規(guī)律，即便是可以，歸納也不是一件容易的事情，尤其要?dú)w納出一個數(shù)學(xué)模型更為困難。而且歸納過程通常沒有一定的規(guī)則可供遵循。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出有用的結(jié)論或解決問題的有效途徑。第二頁，共121頁。通常，歸納(guīnà)的過程分四個步驟：(1)細(xì)心的觀察(guānchá)(2)豐富的聯(lián)想(3)繼續(xù)嘗試(4)總結(jié)歸納出結(jié)論第三頁，共121頁。歸納是一種抽象，即從特殊現(xiàn)象中找出一般關(guān)系。但在歸納過程中不可能列舉(lièjǔ)所有情況，因而最后得出的結(jié)論還只是一種猜測（即歸納假設(shè)）。通過精心觀察而提出的歸納假設(shè)得不到證實(shí)或最后證明是錯的，也是常有的事。因此要盡可能對歸納假設(shè)加以嚴(yán)格的證明，證明的方法通常使用數(shù)學(xué)歸納法。即便找不到證明方法，也必須盡可能多地提出那些容易出錯和疏漏的邊界情況加以驗證，使歸納出的結(jié)論和解決問題的途徑經(jīng)得起各種測試數(shù)據(jù)的檢驗。第四頁，共121頁。問題經(jīng)過(jīngguò)分析歸納后，一般產(chǎn)生四種結(jié)果：(1)遞推式(2)遞歸式(3)制定目標(biāo)(mùbiāo)(4)貪心方案第五頁，共121頁。當(dāng)然，經(jīng)過分析直接概括出高度抽象的數(shù)學(xué)公式亦是一種歸納過程(guòchéng)、一種解題的途徑。但是怎樣進(jìn)行這種歸納，這個問題太寬泛，與其說它是計算機(jī)算法的策略，還不如說它是一種數(shù)學(xué)知識和數(shù)學(xué)能力，取決于解題者本身的數(shù)學(xué)功底。我們已經(jīng)在“對應(yīng)策略”一節(jié)中，對如何將試題與數(shù)學(xué)公式對應(yīng)的問題作了一些討論，這里不再贅述。第六頁，共121頁。一、遞推法瞬息變幻的世界，每一件事物都在隨時間(shíjiān)的流逝發(fā)生著微妙的變化。而在這紛繁的變幻中，許多現(xiàn)象的變化是有規(guī)律的，這種規(guī)律往往呈現(xiàn)出前因和后果的關(guān)系。即某種現(xiàn)象的變化結(jié)果與緊靠它前面變化的一個或一些結(jié)果緊密關(guān)聯(lián)。所謂“三歲看老”，說的就是這個道理。這一道理也正體現(xiàn)了遞推的思想。遞推關(guān)系幾乎在所有的數(shù)學(xué)分支中都有重要作用，在聯(lián)賽中更因其簡捷高效而顯示出獨(dú)特的魅力。第七頁，共121頁。1.遞推關(guān)系的定義(dìngyì)和求解方法有一類試題，每相鄰兩項數(shù)之間的變化有一定的規(guī)律性，我們可將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式：fn=g(fn-1)或者fn-1=g’(fn)這樣就在數(shù)的序列中，建立(jiànlì)起后項和前項之間的關(guān)系。然后從初始條件(或最終結(jié)果)入手，一步步地按遞推關(guān)系式遞推，直至求出最終結(jié)果(或初始值)。很多程序就是按這樣的方法逐步求解的。如果對一個試題，我們要是能找到后一項數(shù)與前一項數(shù)的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就比較容易解決，讓計算機(jī)一步步計算就是了。讓高速的計算機(jī)從事這種重復(fù)運(yùn)算，可真正起到“物盡其用”的效果。第八頁，共121頁。順推法就是由邊界條件出發(fā)，通過(tōngguò)遞推關(guān)系式推出后項值，再由后項值按遞推關(guān)系式推出再后項值，依次遞推，直到從問題初始陳述向前推進(jìn)到這個問題的解為止。倒推法就是在不知初始值的情況下，經(jīng)推理而獲知問題的最終解或目標(biāo)，再倒過來，推知它的初始條件。因為這種問題的運(yùn)算過程是一一映射的，故可分析其倒推公式。然后再從最終解或目標(biāo)出發(fā)，采用倒推手段，一步步地倒推到這個問題的初始陳述。遞推分倒推法和順(héshùn)推法兩種形式：第九頁，共121頁。一般分析(fēnxī)思路：if(求解初始條件f1)//倒推{由題意(tíyì)(或遞推關(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//順推{由題意(tíyì)(或遞推關(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;}第十頁，共121頁。由此可見，遞推算法的時間復(fù)雜度一般為W(n)。我們之所以將遞推法劃入歸納策略，是因為初始條件（或最終結(jié)果）除試題己明確給定外，都是通過對問題的整理與化簡而確定(quèdìng)的，其遞推式也是對實(shí)際問題的分析與歸納而得到的，因此遞推本質(zhì)上屬于歸納。第十一頁，共121頁。2．遞推關(guān)系(guānxì)的建立遞推關(guān)系中存在著三大基本問題：如何建立遞推關(guān)系，已給出的遞推關(guān)系有何性質(zhì)(xìngzhì)，以及如何求解遞推關(guān)系。其中核心問題是如何建立遞推關(guān)系。第十二頁，共121頁。建立遞推關(guān)系(guānxì)的關(guān)鍵在于尋找第n項與前面（或后面）幾項的關(guān)系(guānxì)式，以及初始項的值（或最終結(jié)果值）。它不是一種抽象的概念，而是針對某一具體題目或一類題目而言的。下面，我們對五種典型的遞推關(guān)系(guānxì)的建立作比較深入具體的討論。遞推程序一般是將遞推公式“直譯”成一重循環(huán)，模式性很強(qiáng)。第十三頁，共121頁。(1)Fibonacci數(shù)列(shùliè)Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”（又稱“Fibonacci問題”)：有雌雄一對兔子，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n個月后共有多少(duōshǎo)對兔子？分析：設(shè)滿X月共有兔子Fx對，其中當(dāng)月新生的兔子數(shù)目為Nx對。第x-1個月留下的兔子數(shù)設(shè)為Ox對。則：第十四頁，共121頁。Fx=Nx+Ox而Ox=Fx-1Nx=Ox-1=Fx-2(即第x-2個月的所有兔子到第x個月都有繁殖能力了)所以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)在比較簡單的組合計數(shù)問題中，例如【例9】極值問題、【例10】取石子問題、【例13】蜜蜂(mìfēng)爬行等問題都可以用這種方法來解決。第十五頁，共121頁。(2)Hanoi塔問題(wèntí)Hanoi塔由n個大小不同的圓盤和三根木柱(mùzhù)a,b,c組成。開始時，這n個圓盤由大到小依次套在a柱上，如圖所示。第十六頁，共121頁。要求(yāoqiú)把a(bǔ)柱上n個圓盤按下述規(guī)則移到c柱上：1.一次只能移一個圓盤；2.圓盤只能在三個柱上存放；3.在移動過程中，不允許大盤壓小盤。問將這n個盤子從a柱移動到c柱上，總計需要移動多少個盤次？第十七頁，共121頁。分析(fēnxī)：設(shè)hn為n個盤子從a柱移到c柱所需移動的盤次。顯然，當(dāng)n=1時，只需把a(bǔ)柱上的盤子直接移動到c柱就可以了，故h1=1。當(dāng)n=2時，先將a柱上面的小盤子移動到b柱上去；然后將大盤子從a柱移到c柱；最后，將b柱上的小盤子移到c柱上，共計3個盤次，故h2=3。第十八頁，共121頁。以此類推，當(dāng)a柱上有n(n>=2)個盤子時，總是先借助c柱把上面的n-1個盤子移動(yídòng)到b柱上，然后把a(bǔ)柱最下面的盤子移動(yídòng)到c柱上；再借助a柱把b柱上的n-1個盤子移動(yídòng)到c柱上；總共移動(yídòng)hn=2hn-1+1邊界條件：h1=1第十九頁，共121頁。(3）平面分割(fēngē)問題設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些(zhèxiē)封閉曲線把平面分割成的區(qū)域個數(shù)。分析：設(shè)an為n條封閉曲線把平面分割成的區(qū)域個數(shù)。由圖可得:a2-a1=2;a3-a2=4;a4-a3=6。第二十頁，共121頁。從這些式子中可以看出an-an-1=2(n-1)當(dāng)然，上面的式子只是我們通過觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來試著證明一下。當(dāng)平面上已有n-1條曲線將平面分割成an-1個區(qū)域后，第n條曲線每與其他曲線相交一次，就會增加(zēngjiā)一個區(qū)域，因為平面上已經(jīng)有了n-1條封閉曲線，且第n條曲線與己有的每一條閉曲線恰好相交于兩點(diǎn)，不會與任兩條曲線交于同一點(diǎn)，故平面上一共增加(zēngjiā)2(n-1)個區(qū)域，加上已有的an-1個區(qū)域，一共有an-1+2(n-1)個區(qū)域。所以本題的遞推關(guān)系是an=an-1+2(n-1)，邊界條件是a1=2。第二十一頁，共121頁。平面分割問題是競賽中經(jīng)常觸及到的一類問題，由于其靈活多變，常常(chángcháng)讓選手感到棘手，下題是另一種平面分割問題，有興趣的讀者不妨自己先試著求一下其中的遞推關(guān)系。第二十二頁，共121頁。(4)Catalan數(shù)在一個凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用hn表之，hn即為Catalan數(shù)。例如(lìrú)五邊形有如圖所示的五種拆分方案，故h5=5。求對于一個任意的凸n邊形相應(yīng)的hn。Catalan數(shù)首先是由Euler在精確計算對凸n邊形不同的對角三角形剖分的個數(shù)問題時得到的，它經(jīng)常出現(xiàn)在組合計數(shù)問題中。第二十三頁，共121頁。分析：設(shè)Cn表示(biǎoshì)凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個凸n邊形的任意一條邊都必然是一個三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在同一直線上的三點(diǎn)可以確定一個三角形”，只要在P2，P3，…，Pn-1，點(diǎn)中找一個點(diǎn)Pk(1<k<n)，與P1,Pn共同構(gòu)成一個三角形的三個頂點(diǎn)，就將n邊形分成了三個不相交的部分，我們分別稱之為區(qū)域①、區(qū)域②和區(qū)域③。第二十四頁，共121頁。其中區(qū)域③必定是一個(yīɡè)三角形，區(qū)域①是一個(yīɡè)凸k邊形，區(qū)域②是一個(yīɡè)凸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ù)為第二十五頁，共121頁。加法(jiāfǎ)原理和乘法原理(1)加法原理：做一件事，完成它可以(kěyǐ)有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共有N＝m1＋m2＋…＋mn種不同方法．

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

要做一件事，完成它若是有n類辦法，是分類問題，第一類中的方法都是獨(dú)立的，因此用加法原理；做一件事，需要分n個步驟，步與步之間是連續(xù)的，只有將分成的若干個互相聯(lián)系的步驟，依次相繼完成，這件事才算完成，因此用乘法原理．第二十六頁，共121頁。同時考慮到計算的方便，約定邊界條件C2=1.Catalan數(shù)是比較復(fù)雜的遞推關(guān)系，尤其在競賽的時候，選手很難在較短的時間里建立起正確的遞推關(guān)系。當(dāng)然，Catalan數(shù)類的問題也可以用搜索的方法來完成(wánchéng)，但是，搜索的方法與利用遞推關(guān)系的方法比較起來，不僅效率低，編程復(fù)雜度也陡然提高。第二十七頁，共121頁。(5）第二類stirling數(shù)蘇格蘭數(shù)學(xué)家斯特林（J.Stirling,1692-1770）首次發(fā)現(xiàn)這些數(shù)并說明了它們的重要性。n個有區(qū)別的球放到m個相同的盒子中，要求無一空盒，不同的方案數(shù)用s2(n,m)表示，稱為(chēnɡwéi)第二類Stirling數(shù)。分析：設(shè)有n個不同的球，分別用b1,b2，…，bn表示。從中取出一個球bn，bn的放法有以下兩種：①bn獨(dú)自占一個盒子，那么剩下的球只能放在m-1個盒子中，方案數(shù)為S2(n-1，m-1)；②bn與別的球共占一個盒子，那么可以事先將b1,b2，…，bn-1這n-1個球放入m個盒子中，然后再將球bn可以放入其中一個盒子中，方案數(shù)為mS2(n-1,m)。第二十八頁，共121頁。綜合(zōnghé)以上兩種情況，可以得出第二類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)

第二十九頁，共121頁。第二類stirling數(shù)在競賽中較少出現(xiàn)，但在競賽中也有一些題目與其類似，甚至更為復(fù)雜。讀者不妨自己來試著建立其中的遞推關(guān)系。通過上面對五種典型的遞推關(guān)系建立過程的探討(tàntǎo)，可知對待遞推類的題目，要具體情況具體分析，通過找到某狀態(tài)與其前面狀態(tài)的聯(lián)系，建立相應(yīng)的遞推關(guān)系。第三十頁，共121頁。3．遞推關(guān)系(guānxì)的應(yīng)用遞推關(guān)系的應(yīng)用十分廣泛，其中一個非常重要的應(yīng)用就是著名的楊輝三角（又稱“Pascal三角”。楊輝三角是根據(jù)組合公式Cnr=Cn-1r+Cn-1r-1畫出來的。很顯然，組合公式、楊輝三角都屬于(shǔyú)遞推關(guān)系的范圍。第三十一頁，共121頁。在今天的信息學(xué)競賽中，遞推關(guān)系的應(yīng)用也日趨廣泛，下面就讓(jiùrànɡ)我們從近年來的兩道競賽題中體會遞推關(guān)系的應(yīng)用。第三十二頁，共121頁?！纠?3】蜜蜂(mìfēng)爬行有一只經(jīng)過訓(xùn)練的蜜蜂只能(zhīnénɡ)爬向右側(cè)相鄰的蜂房，不能反向爬行，如圖所示。試求出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)第三十三頁，共121頁。分析：這是一道很典型的Fibonacci數(shù)列類題目，其中的遞推關(guān)系很明顯。由于“蜜蜂只能(zhīnénɡ)爬向右側(cè)相鄰的蜂房，不能反向爬行”的限制，決定了蜜蜂到n點(diǎn)的路徑只能(zhīnénɡ)是從n-1點(diǎn)或n-2點(diǎn)到達(dá)的，故:fn=fn-1+fn-2(a+2<=n<=b),邊界條件為fa＝1，fa+1＝1.第三十四頁，共121頁?！纠?4】分割(fēngē)平面同一平面內(nèi)的n(n<=500）條直線，已知有p(p>=2)條直線相交于同一點(diǎn)(yīdiǎn)，則這n條直線最多能將平面分割成多少個不同的區(qū)域？分析：直線的平面分割與封閉曲線的平面分割十分相似，不同之處就在于線條的曲直以及是否存在共點(diǎn)的直線。由于共點(diǎn)直線的特殊性，我們決定先考慮p條相交于一點(diǎn)(yīdiǎn)的直線，然后再考慮剩下的n-p條直線。第三十五頁，共121頁。首先可以直接求出p條相交于一點(diǎn)的直線將平面劃分成的區(qū)域(qūyù)數(shù)為2*p個然后在平面上已經(jīng)有k(k>=p)條直線的基礎(chǔ)上，加上一條直線，最多可以與k條直線相交，而每次相交都會增加一個區(qū)域(qūyù),與最后一條直線相交后，由于直線可以無限延伸，還會再增加一個區(qū)域(qūyù)。所以fm=fm-1+m(m>P)，邊界條件在前面己經(jīng)計算過了，是fp=2*p。雖然這題看上去有兩個參數(shù)，但是在實(shí)際做題中會發(fā)現(xiàn)，本題還是屬于帶一個參數(shù)的遞推關(guān)系。第三十六頁，共121頁?！纠?5】平面(píngmiàn)分割空間問題一個平面把空間分成獨(dú)立的兩個部分，兩個平面把空間分成4個部分。n個平面，最多能把整個(zhěnggè)空間分割成多少個部分。分析：立體空間的情況是陌生的，但是空間和平面的關(guān)系與平面和直線的關(guān)系是相似的。平面把空間分割成兩個部分，直線也把平面分割成兩個部分。于是得到了另一個與例題相類似的問題：n條直線，最多能把整個(zhěnggè)平面分割成多少個部分，如圖所示。第三十七頁，共121頁。第三十八頁，共121頁。一條直線,把平面分割為兩個部分;增加一條直線，它與第一條直線相交,被分為兩段射線，每一段射線又把所在的區(qū)域分成兩部分;因此增加了2個部分。再增加一條直線，它與前兩條直線相交，被分為三段，每一段又把所在區(qū)域分成兩部分;共增加了3個部分。由此類推(lèituī)，設(shè)前k-1條直線共把平面分為ak-1個部分。加入第k條直線，與前k-1條直線相交，被分為k段，每一段把所在區(qū)域分為兩部分；總共增加了k部分；總共有ak-1+k個部分。于是得到了遞推關(guān)系:第三十九頁，共121頁。a1=2;ak=ak-1+k;即ak=1+k*(1+k)/2于是直線分割平面的問題就解決了。既然空間和平面，與平面和直線的關(guān)系相似，那么直接把平面換成空間，把直線換成平面，就可以直接用以上的過程來證明未知的問題了嗎？顯然是不可以的，這種僅僅根據(jù)主觀的相似性得出(déchū)的機(jī)械模仿是錯誤的。第四十頁，共121頁。但是如果仔細(xì)分析一下錯誤的原因，將會發(fā)現(xiàn)問題的關(guān)鍵:線線相交得到的是交點(diǎn),面面相交得到的是直線,k個點(diǎn)把直線分成k+1個部分,而k條直線則不是簡單的把平面(píngmiàn)分成k+1個部分。事實(shí)上,k條直線最多把平面(píngmiàn)分成ak個部分！因此兩個問題真正的相似之處在于，一個為了計算直線把平面(píngmiàn)分割成幾部分，先計算這條直線被點(diǎn)（線線交點(diǎn)）分割成幾部分，把二維的問題化為一維的問題；另一個要計算平面(píngmiàn)把空間分割成幾部分，先計算這個平面(píngmiàn)被線（面面交線）分割成幾部分，把三維的問題化為二維的問題。而二維的問題是已經(jīng)被解決了的，于是反過來，三維的問題也解決了。第四十一頁，共121頁。同樣是利用數(shù)學(xué)歸納法：一個平面把空間分割成兩部分；設(shè)前k-1個平面共把空間分割成bk-1個部分。加入第k個平面后，與前k-1個平面相交，共有k-1條交線。k-1條交線把這個平面分為幾塊呢？這買際上就是剛剛解決過的回題：k-1條直線，把平面分割成： ak-1=1+k*(1+k)/2分別把所在原來(yuánlái)空間一分為二，總共增加了ak-1個部分，于是平面總共把空間分割成個部分。于是得到了遞推關(guān)系：第四十二頁，共121頁。利用這一遞推關(guān)系來編寫程序(chéngxù)，不難求出bn，而且即便對很大的n，程序(chéngxù)的運(yùn)算速度仍然是很快的。（當(dāng)然，也可以計算出bn的通項公式:第四十三頁，共121頁。二、遞歸法設(shè)一個未知函數(shù)f，用其自身構(gòu)成的已知函數(shù)g來定義(dìngyì)：f(n)=g(n,f(n-1))n>0f(0)=an=0為了定義(dìngyì)f(n)，必須先定義(dìngyì)f(n-1),為了定義(dìngyì)f(n-1)，又必須先定義(dìngyì)f(n-2)…,上述這種用自身的簡單情況來定義(dìngyì)自己的方式稱為遞歸定義(dìngyì)。一個遞歸定義(dìngyì)必須是有確切含義的，也就是說，必須一步比一步簡單，最后是有終結(jié)的，決不能無限循環(huán)下去。在f(n)的定義(dìngyì)中，當(dāng)n為0時定義(dìngyì)一個已知數(shù)a，是最簡單的情況，稱為遞歸邊界，它本身不再使用遞歸的定義(dìngyì)。第四十四頁，共121頁。與遞推一樣，每一個遞歸定義都有其邊界條件。但不同的是，遞推是由邊界條件出發(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ù)或求解遞歸問題的過程稱為遞歸算法。一個遞歸算法，本質(zhì)(běnzhì)上是將較復(fù)雜的處理歸結(jié)為簡單處理，直到最簡單的處理。第四十五頁，共121頁。從實(shí)際問題中抽象遞歸定義和邊界條件的過程是一種歸納，通過這種歸納方式能使一個(yīɡè)蘊(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)存溢出的窘境。第四十六頁，共121頁。遞歸算法適用的一般場合為：(1)數(shù)據(jù)(shùjù)的定義形式按遞歸定義。這類遞歸問題可直接轉(zhuǎn)化為遞推算法，遞歸邊界作為遞推的邊界條件。(2)數(shù)據(jù)(shùjù)之間的關(guān)系(即數(shù)據(jù)(shùjù)結(jié)構(gòu))按遞歸定義。如樹的遍歷，圖的搜索等。(3)有些問題本身沒有明顯的遞歸結(jié)構(gòu)，但使用遞歸求解比其他方法更簡單。如遞歸的分治策略。對于(2)、(3)，可利用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法，但結(jié)構(gòu)不如遞歸算法簡單清晰，可讀性較差。第四十七頁，共121頁。編寫遞歸程序時應(yīng)注意如下幾個問題：(1)問題的遞歸定義，即如何用自身的簡單情況定義自己；(2)遞歸邊界，即遞歸至哪個邊界值后開始(kāishǐ)回溯；(3)參與遞歸運(yùn)算的變量有哪些，其中哪些作為值參，哪些作為局部變量。如果有全局變量參與遞歸運(yùn)算的話(初始值由主程序傳入，受內(nèi)存限制不便作為值參)，回溯過程中必須恢復(fù)其遞歸前狀態(tài)。第四十八頁，共121頁?！纠?6】計算(jìsuàn)交點(diǎn)數(shù)在平面上有n條直線，且無三線共點(diǎn)。問這些直線能有多少種不同的交點(diǎn)數(shù)？輸入：n輸出：以下若干行列出所有(suǒyǒu)相交方案。其中每一行為某一方案的交點(diǎn)個數(shù)。分析：我們將n條直線排成一個序列。直線2與直線1最多有一個交點(diǎn)；直線3與直線1和直線2最多有2個交點(diǎn)，…，直線n與其他n-1條直線最多有n-1個交點(diǎn)。由此得出n條直線互不平行且無三線交于一點(diǎn)的最多交點(diǎn)數(shù)中1+2+，…+(n-1)=n*(n-1)/2.第四十九頁，共121頁。設(shè)第五十頁，共121頁。我們來具體分析n=4的情況(1)四條直線全部平行，無交點(diǎn)，g[0]=1(2)其中(qízhōng)三條(n-1)直線平行，交點(diǎn)數(shù)為(n-1)x1+0=3,g[3]=1(3)其中(qízhōng)兩條(n-2)直線平行，這兩條直線與另外兩條直線之間的交點(diǎn)數(shù)為(n-2)x2=4而另外兩條直線本身既可能平行也可能相交，因此交點(diǎn)數(shù)分別為：當(dāng)平行時(n-2)x2+0=4g[4]=1當(dāng)相交時(n-2)x2+1=5g[5]=1(4)四條直線互不平行，交點(diǎn)數(shù)為：1+2+3=6g[6]=1即n=4時，有0、3、4、5、6個不同的交點(diǎn)數(shù)第五十一頁，共121頁。由此得出：m條直線的交點(diǎn)方案=r條平行線與(m-r)條直線交叉的交點(diǎn)數(shù)+(m-r)條直線本身的交點(diǎn)方案=(m-r)r+(m-r)條直線本身的交點(diǎn)數(shù)(1<=r<=m)顯然，計算不同(bùtónɡ)交點(diǎn)數(shù)的問題是遞歸的第五十二頁，共121頁?？梢悦枋龀扇缦?rúxià)遞歸算法：//m是直線(zhíxiàn)數(shù)，j是交點(diǎn)數(shù)voidcross(intm,intj){if(m>0) //若直線(zhíxiàn)存在，則遞歸計算所有的交叉情況 for(intr=m;r>=1;r--)cross(m-r,j+r*(m-r));else//否則確定m條直線(zhíxiàn)存在j個交點(diǎn) g[j]=1;}第五十三頁，共121頁。計算和輸出n條直線(zhíxià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;}}第五十四頁，共121頁。三、制定(zhìdìng)目標(biāo)有些問題看似棘手，主要是沒有找到解決問題的路子，或者說目標(biāo)不明確。一旦建立了評判好壞的標(biāo)準(zhǔn)(目標(biāo)函數(shù)或者目標(biāo)方案)，求解問題的算法也就自然而然地產(chǎn)生了。關(guān)鍵是建立標(biāo)準(zhǔn)。而這個標(biāo)準(zhǔn)是通過對實(shí)際問題的分析與歸納得到的。因此(yīncǐ)，我們將之劃入歸納的范疇。第五十五頁，共121頁?！纠?7】最優(yōu)分解(fēnjiě)方案把正整數(shù)n分解成若干個互不相等的自然數(shù)的和，且使這些(zhèxiē)自然數(shù)的乘積最大。請你編寫一個算法，由鍵盤輸入n,求滿足條件的分解方案。輸入：n(3<=n<=1000)輸出：乘積分析：如何把正整數(shù)n分解成若干互不相等的自然數(shù)的和，且使這些(zhèxiē)自然數(shù)的乘積最大呢？如果我們對這個問題不探究解析方法而去盲目搜索所有分解方案的話，則代價相當(dāng)大。但是如果我們一旦耐心地對問題認(rèn)真思考一番，是不難得出其中隱含著的數(shù)學(xué)規(guī)律的。設(shè)：第五十六頁，共121頁。由于1<=a1<a2<…<an，因此s/n>1。很明顯，要使得乘積a1×a2×…×an最大，則必須(bìxū)使得項數(shù)n最大，且相鄰兩數(shù)ai+1-ai的差最小，這就是解決問題的目標(biāo)方案。第五十七頁，共121頁。為了達(dá)到這個目標(biāo)，我們不妨設(shè)a1=2(因為a1=1時,a1在乘式中無意義(yìyì)），先求出：n=2+3+4+,…,+ak+ak+1ak>=ak+1這種分解方案的項數(shù)無疑最多。問題是要保證ak+1<=ak,ak+1要么為1,要么重復(fù)其中某一項，因此必須撤去。為了保證撤去ak+1后的各個自然數(shù)依然互不相等，其和還是等于n且乘積最大，我們將ak+1盡量平均地加在后幾項。并盡可能使得相鄰兩數(shù)的差不超過2第五十八頁，共121頁。①若ak+1=1,由于1x2x,…,xak<2x3x,…,x(ak+1)，因此ak+1=1加到ak上；②若1<ak+1<ak,我們從ak出發(fā)，依次向尾部ak+1個數(shù)加1;③若ak+1=ak,則ak加上2,其余(qíyú)k-1個數(shù)依次加1;當(dāng)然，還必須考慮一個例外情況：當(dāng)n=3或n=4時，只能分解出一個表達(dá)式：3=1+2mul=1x2=24=1+3mul=1x3=3由此可見，上述目標(biāo)方案是分解自然數(shù)的依據(jù)。第五十九頁，共121頁。有了這個目標(biāo)方案，相應(yīng)的算法也就可以(kěyǐ)設(shè)計出來了。#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時，輸出分解(fēnjiě)方案。else第六十頁，共121頁。{intk=1;a[k]=2;n=n-a[k];//從2開始分解(fēnjiě) while(n>a[k])//分解(fēnjiě)直到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;}第六十一頁，共121頁。四、貪心(tānxīn)法和前面所講的遞推法相仿，貪心法也是從問題的某一個初始解出發(fā)，向給定的目標(biāo)推進(jìn)。但不同的是，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個當(dāng)時(dàngshí)看似最佳的貪心選擇，不斷地將問題實(shí)例歸納為更小的相似的子問題，并期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個全局最優(yōu)解。對于貪心法，我們并不陌生。例如求最小生成樹、求單源最短路徑使用的算法策略實(shí)際上就是貪心法。第六十二頁，共121頁。貪心法建議通過一系列步驟來構(gòu)造問題的解，每一步對目前構(gòu)造的部分解做一個擴(kuò)展，直到獲得問題的完整解為止。這個問題的核心是，所做的每一步選擇都必須(bìxū)滿足以下條件：可行的：即它必須(bìxū)滿足問題的約束。局部最優(yōu)：它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇不可取消：即選擇一旦做出，在算法的后面步驟中就無法改變。在每一步中，它要求“貪婪”地選擇最佳操作，并希望通過一系列局部的最佳選擇，能夠產(chǎn)生一個整個問題的（全局的）最佳解。第六十三頁，共121頁。 那么如何證明按貪心選擇得出的解是最優(yōu)解呢？有兩種方法：(1)對貪心選擇進(jìn)行數(shù)學(xué)分析，從理論上證明是最優(yōu)的。(2)構(gòu)造一個最優(yōu)解，然后對該解進(jìn)行修正，使其第一步為一個貪心選擇，證明總是存在一個以貪心選擇開始的求解(qiújiě)方案，然后證明經(jīng)過若干次貪心選擇后可以得出一個最優(yōu)解。第二種證明方法相對比較容易。由于貪心選擇的設(shè)計及其產(chǎn)生最優(yōu)解的證明是對實(shí)際問題分析歸納的結(jié)果.因此,我們將貪心法列為一種歸納策略。第六十四頁，共121頁?！纠?8】活動(huódòng)選擇假設(shè)有一個需要使用某一資源的n個活動組成的集合S={1,…,n}。該資源一次只能被一個活動所占用，每一個活動有一個開始(kāishǐ)時間Si和結(jié)束時間Fi(Si<=Fi)。若Si>=Fj或者Sj>=Fi，則活動i和活動j兼容。選擇由互相兼容的活動組成的最大集合。 輸入：n S1F1 … SnFn 輸出：占用時間t 最大集合A中的活動序號第六十五頁，共121頁。分析：我們使用盡可能逼近目標(biāo)的貪心策略來選擇活動，即每一步總是(zǒnɡshì)選擇這樣一個活動來占用資源―它能夠使得余下的未調(diào)度時間最大化，使得兼容的活動盡可能多。為了達(dá)到這個目的，我們將n個待選活動按結(jié)束時間遞增的順序排列：F1<=F2<=…<=Fn遞增序列中的活動1進(jìn)入集合A。然后依次分析序列中的活動2到活動n，將那些與A中活動兼容的活動送入集合A。第六十六頁，共121頁。例如活動開始(kāishǐ)時間結(jié)束時間13521431214481250668117610857938105911213第六十七頁，共121頁。#include<iostream>usingnamespacestd;constintN=11;//活動序號intno[N]={1,2,3,4,5,6,7,8,9,10,11};//開始(kāishǐ)時間ints[N]={3,1,12,8,0,8,6,5,3,5,2};//結(jié)束時間intf[N]={5,4,14,12,6,11,10,7,8,9,13};第六十八頁，共121頁。voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}//選擇(xuǎnzé)排序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]); }}第六十九頁，共121頁。voidmain(){staticinta[N];//a是兼容集合 intt=0;//t是占用時間 sort();//按結(jié)束(jiéshù)時間遞增的順序排序 intk=0;intj=0;a[k]=no[0];//初始活動表為NO[0] for(inti=1;i<N;i++) {//若遞增序列中的活動i與A集合中的活動兼容 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]<<"";}第七十頁，共121頁。貪心(tānxīn)選擇的過程t=14a={2,8,6,3}第七十一頁，共121頁。我們使用第二種方法證明按照這個貪心選擇的解一定是最優(yōu)的：(1)構(gòu)造一個最優(yōu)解，然后對該解進(jìn)行修正，使其第一步為一個貪心選擇，證明總是存在一個以貪心選擇開始的求解方案。設(shè)最優(yōu)解為a。第一個選中的活動為k(k不等于1)。如果另一個解b開始于貪心選擇活動1(b=(a-{k})U{1})。因為f1<=fk，所以b中的活動是兼容的。又因為b與a的活動數(shù)相同(xiānɡtónɡ)，所以b也是最優(yōu)的。由此證明總存在一個以貪心選擇開始的最優(yōu)調(diào)度。第七十二頁，共121頁。(2)證明經(jīng)過若干次貪心選擇后可以得出一個最優(yōu)解當(dāng)我們作出了對活動1的貪心選擇后，原問題就變成在活動2至活動n中找與活動1兼容的那些活動的子問題。也就是說，如果問題a為原問題的一個最優(yōu)解，則a’=a-{1}就是活動選擇問題s’的一個最優(yōu)解。為什么會這樣呢？如果我們能找到s的一個含有比a’更多活動的解b’則將活動1加入了b’,就得到s的一個包含比a更多活動的解b,這就與a的最優(yōu)性相矛盾。所以在每一次貪心選擇后,留下的是一個與原問題具有相同形式(xíngshì)的最優(yōu)化問題.通過對所做選擇次數(shù)的歸納可以證明,對每一步進(jìn)行貪心選擇就可得到一個最優(yōu)解.由此得出，按照這個貪心選擇得出的解一定是最優(yōu)的。第七十三頁，共121頁。2801【例19】打包(dǎbāo)（Packaging)某個工廠生產(chǎn)出的產(chǎn)品都要被打包放入正四棱柱的盒子內(nèi)。所有盒子的高度都為h,但底面的尺寸不同(bùtónɡ)，可以為1x1,2x2,3x3,4x4,5x5,或6x6，如圖所示。第七十四頁，共121頁。這些盒子將被放入高度為h,底面尺寸為6x6的箱子里,送到消費(fèi)者手中。為了降低運(yùn)送(yùnsònɡ)成本，工廠希望盡量減少箱子的數(shù)量。如果有一個好的算法，能使箱子的數(shù)量降到最低，這將給工廠節(jié)省不少資金。請你寫一個這樣的程序。輸入：六個非負(fù)整數(shù)a1,a2,a3,a4,a5,a6。它們分別為底面尺寸為1x1,2x2,3x3,4x4,5x5,6x6的盒子的個數(shù)。輸出：一個數(shù)b，即箱子的最少個數(shù)。第七十五頁，共121頁。分析：讓我們來看看可供選擇的裝箱方法：(1)如果有6x6的盒子，則將它放入箱子，這個箱子就滿了，該過程直到6x6的盒子全部(quánbù)裝箱為止；(2)如果有5x5的盒子，則將它放入箱子，這個箱子還有空余，可以放入盡可能多的1x1的盒子，這個過程的結(jié)束條件是5x5的盒子全部(quánbù)裝箱，并且1x1的盒子全部(quánbù)裝箱或者箱子全部(quánbù)裝滿；(3)如果有4x4的盒子，箱子中的剩余空間可以放2x2的盒子，如果還有剩余，則放1x1的盒子，這個過程直到4x4的盒子全部(quánbù)裝箱，并且剩余空間被充分利用；……第七十六頁，共121頁。簡而言之就是每次找出最大的盒子放入當(dāng)前的箱子中，直到無法再放；再拿一個空箱繼續(xù)這一過程，直到所有的盒子都被裝箱。解決這一類(yīlèi)問題我們通常采用貪心算法。下面我們使用第一種方法來證明對于打包問題，貪心法可以得出最優(yōu)解。設(shè)要裝下a1個1x1的盒子,a2個2x2的盒子，……，a6個6x6的盒子需要的箱子數(shù)為f(a1,a2,a3,a4,a5,a6)個。由前面的分析可知：第七十七頁，共121頁。(1)由每一個6x6的盒子都剛好放入一個6x6的箱子可得等式(děngshì):f(a1,a2,a3,a4,a5,a6)=f(a1,a2,a3,a4,a5,0)+a6(2)己知放置每一個5x5的盒子都需要一個箱子，但每個箱子放入一個5x5的盒子后還有6x6-5x5=11個單位的空間，而這些空間只能放1x1的盒子，最多放11個,可得等式(děngshì)：f(a1,a2,a3,a4,a5,0)=f(max{0,a1-11*a5},a2,a3,a4,0,0)+a5第七十八頁，共121頁。(3)已知放置每一個4x4的盒子都需要一個箱子(xiāngzi)，之后還有6x6-4x4=20個單位的空間。這些空間恰好可以放入5個2x2的盒子，或20個1x1的盒子。根據(jù)盡可能先放大盒子的貪心策略，我們盡量先放2x2的盒子。放置a4個4x4的盒子需要a4個箱子(xiāngzi)，剩余5*a4個2x2的空間。

第七十九頁，共121頁。若a2>=5*a4,則這些空間(kōngjiān)全部用掉，否則剩下的空間(kōngjiān)還可以“見縫插針”地放入1x1的盒子。由此可得等式：第八十頁，共121頁。(4)已知每個箱子可以放4個3x3的盒子。這樣4個4個放完后，可能還剩余(shèngyú)0,1,2,3個3x3的盒子。與放置4x4的盒子時同樣的原理，還是先放2x2的盒子,再放1x1的盒子。第八十一頁，共121頁。在這4種情況(qíngkuàng)下分別還能放0,1,3,5個2x2的盒子。剩余的空間再放入1x1的盒子。第八十二頁，共121頁。(5)一個箱子可放9個2x2的盒子，放完2x2的盒子后，多余的空間放1x1的盒子。等式(děngshì)如下：第八十三頁，共121頁。(6)放置1x1的盒子(hézi)時有關(guān)系式(圖j)：這六個等式的順序即為貪心策略。由此證明貪心法可以求得最優(yōu)解第八十四頁，共121頁。intpack(inta1,inta2,inta3,inta4,inta5,inta6){intc=a6;c=c+a5;//加上放入6x6,5X5的盒子(hézi)數(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;}第八十五頁，共121頁。 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第八十六頁，共121頁。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;}第八十七頁，共121頁。#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);}第八十八頁，共121頁。#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)品(chǎnpǐn)時剩余放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;}第八十九頁，共121頁。貪心(tānxīn)算法的基本要素可以用貪心算法求解的問題一般具有兩個重要的性質(zhì)：貪心選擇(xuǎnzé)性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)1.貪心選擇(xuǎnzé)性質(zhì)：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇(xuǎnzé)，即貪心選擇(xuǎnzé)來達(dá)到。貪心算法所做的貪心選擇(xuǎnzé)可以依賴于以往所做過的選擇(xuǎnzé)，但決不依賴于將來所做的選擇(xuǎnzé)，也不依賴于子問題的解。第九十頁，共121頁。貪心算法通常以自頂向下的方式進(jìn)行，以迭代(diédài)的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2.最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。第九十一頁，共121頁。本節(jié)作業(yè)(zuòyè)一、簡要回答如下問題：簡述歸納過程步驟(bùzhòu)？遞推方法一般分析思路是什么？遞歸算法適用的一般場合是什么？簡述貪心算法的基本要素第九十二頁，共121頁。二、根據(jù)題意，建立如下問題的遞推公式或遞歸公式？(1)Fibonacci數(shù)列(2)Hanoi塔問題(3)封閉(fēngbì)曲線分割平面問題(4)Catalan數(shù)(5)第二類stirling數(shù)【例13】蜜蜂爬行【例14】直線分割平面【例15】平面分割空間問題第九十三頁，共121頁。第四節(jié)、模擬(mónǐ)策略在自然界和日常生活中，許多現(xiàn)象具有不確定的性質(zhì)，有些問題甚至很難建立數(shù)學(xué)模型，或者很難用計算機(jī)建立遞推、遞歸、枚舉、回溯等算法。在這種情況下，一般采用模擬策略。所謂模擬策略就是模擬某個過程，通過改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察(guānchá)變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計。第九十四頁，共121頁。模擬題沒有固定的模式，一般形式有兩種：(1)隨機(jī)模擬：題目給定或者隱含某一概率。設(shè)計者利用隨機(jī)函數(shù)和取整函數(shù)設(shè)定某一范圍的隨機(jī)值，將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬的數(shù)學(xué)模型展開算法設(shè)計。由于解題過程(guòchéng)借助了計算機(jī)的偽隨機(jī)數(shù)發(fā)生器，其隨機(jī)的意義要比實(shí)際問題中真實(shí)的隨機(jī)變量稍差一些，因此模擬效果有不確定的因素。第九十五頁，共121頁。(2)過程模擬：題目不給出概率，要求編程者按照題意設(shè)計數(shù)學(xué)模型的各種參數(shù)，觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計。模擬效果完全取決于過程模擬的真實(shí)性和算法的正確性，不含任何不確定因素。 由于過程模擬的結(jié)果無二義性，因此競賽大都(dàdōu)采用過程模擬。第九十六頁，共121頁。模擬的解題方法一般有三種類型：(1)直敘式模擬(2)篩選(shāixuǎn)法模擬(3)構(gòu)造法模擬第九十七頁，共121頁。一、直敘式模擬(mónǐ)直敘式模擬，即按照試題(shìtí)要求展開模擬過程。編程者要忠實(shí)于原題，認(rèn)真審題，千萬不要疏漏任何條件，精心設(shè)計方便模擬的數(shù)據(jù)結(jié)構(gòu)。直敘式模擬的難度取決于模擬對象所包含的動態(tài)變化的屬性個數(shù)，動態(tài)屬性愈多，則難度愈大。第九十八頁，共121頁?！纠?9】約瑟夫問題(wèntí)有n只猴子，按順時針方向圍成一圈選大王（編號從1到n），從第1號開始報數(shù)，一直數(shù)到m，數(shù)到m的猴子退出圈外，剩下的猴子再接著(jiēzhe)從1開始報數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時，這個猴子就是猴王，編程求輸入n，m后，輸出最后猴王的編號。Input:每行是用空格分開的兩個整數(shù)，第一個是n,第二個是m(0<m,n<=300)。最后一行是：00Output:對于每行輸入數(shù)據(jù)（最后一行除外)，輸出數(shù)據(jù)也是一行，即最后猴王的編號第九十九頁，共121頁。SampleInput621248300SampleOutput517第一百頁，共121頁。解題思路1：用數(shù)組loop來存放n個數(shù)，相當(dāng)于n個數(shù)排成的圈，用整型變量nPtr指向當(dāng)前(dāngqián)數(shù)到的數(shù)組元素，相當(dāng)于人的手指，劃掉一個數(shù)就將該數(shù)置0，在數(shù)數(shù)時，要跳過為0的元素。當(dāng)nPtr指向最后一個元素時再數(shù)下一個時則指向數(shù)組的頭一個元素。第一百零一頁，共121頁。#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;}}}第一百零二頁，共121頁。采用(cǎiyòng)循環(huán)鏈表實(shí)現(xiàn)如下#include<iostream.h>采用(cǎiyòng)循環(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;

第一百零三頁，共121頁。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;}第一百零四頁，共121頁?！纠?0】DAM語言(yǔyán)有個機(jī)器執(zhí)行一種(yīzhǒnɡ)DAM語言。該機(jī)器有一個棧，初始時棧里只有一個元素x，隨著DAM語言程序的執(zhí)行，棧里的元素會發(fā)生變化。DAM語言有三種指令：D指令：把棧頂元素復(fù)制一次加到棧頂。A指令：把棧頂元素取出，加到新的棧頂元素中。M指令：把棧頂元素取出，乘到新的棧頂元素中。第一百零五頁，共121頁。如果執(zhí)行A或M指令的時候棧內(nèi)只有一個元素，則機(jī)器會發(fā)出錯誤信息。如果程序無誤，那么執(zhí)行完畢以后，棧頂元素應(yīng)該是X的多項式，例如，程序DADDMA的執(zhí)行情況(qíngkuàng)為（棧內(nèi)元素按照從底到頂?shù)捻樞驈淖笾劣遗帕?，用逗號隔開）：第一百零六頁，共121頁。給出一段DAM程序，求出執(zhí)行完畢后棧頂元素。輸入：輸入僅一行，包含一個不空的字符串s，長度不超過12，代表一段DAM程序。輸入程序保證合法且不會導(dǎo)致錯誤。輸出：僅輸出一行，即棧頂多項式。須按照習(xí)慣寫法降冪輸出，即等于1的系數(shù)不要打印，系數(shù)為0的項不打印，第一項不打印正號。一次方不打印“^1”。分析(fēnxī)：本題是一道“直敘式模擬”題，即按照DAM指令的順序模擬執(zhí)行過程。在模擬的時候有些問題是需要注意的：第一百零七頁，共121頁。(1)多項式的表示方式。有的選手或許會覺得本題沒有說明次數(shù)的上限，因此最好用鏈表做。其實(shí)完全沒有必要。由于指令不超過12條，而D指令和A、M指令總數(shù)應(yīng)該相等，因此最多有6條M指令，因此次數(shù)上限為26=64。我們可以用數(shù)組來表示多項式，既方便又不會導(dǎo)致時間和空間上的問題。(2)本題也沒有說明系數(shù)的最大值。稍微細(xì)心的選手會發(fā)現(xiàn)：它最大可能為232,未超過長整數(shù)(zhěngshù)的范圍，不存在非得用高精度的必要。第一百零八頁，共121頁。#include<iostream.h>#include<string.h>voidmain(){staticintdegree[13];//存儲系數(shù)個數(shù)的棧 staticlongco[13][65];//存儲多項式的棧 longtmp[65];//系數(shù)序列 chars[13];//DAM程序(chéngxù)inti,j; inttop=1;//棧頂指針 degree[1]=1; co[1][1]=1;

cin>>s;第一百零九頁，共121頁。 for(i=0;i<strlen(s);i++) {switch(s[i]) {case'D': top++; deg