算法合集之遞推關(guān)系的建立及在信息學(xué)競賽中的應(yīng)用

1、遞推關(guān)系的建立及在信息學(xué)競賽中的應(yīng)用 安徽 高寒蕊遞推關(guān)系的建立及在信息學(xué)競賽中的應(yīng)用安徽 高寒蕊(蕪湖一中，安徽，241000)【關(guān)鍵字】遞推關(guān)系 建立 應(yīng)用【摘 要】世界上的一切事物都在不經(jīng)意之中變化著，在這紛繁的變幻中，許多現(xiàn)象的變化是有規(guī)律可循的。這種規(guī)律往往呈現(xiàn)出前因和后果的關(guān)系，故我們可以運(yùn)用遞推的思想去研究這些變化。本文著重說明了遞推關(guān)系的建立，并在此基礎(chǔ)上簡略介紹求解遞推關(guān)系的方法。接著，闡明遞推關(guān)系與動(dòng)態(tài)規(guī)劃之間的關(guān)系，并比較了一般遞推關(guān)系與動(dòng)態(tài)規(guī)劃之間的異同，同時(shí)舉例說明遞推關(guān)系在競賽中的應(yīng)用。在文章的最后，總結(jié)出學(xué)好遞推關(guān)系，不僅可以提高我們的數(shù)學(xué)素質(zhì)，對(duì)信息學(xué)競賽更是大

2、有幫助目錄【正文】 第02頁 一、引論 第02頁 二、遞推關(guān)系的定義 第02頁 三、遞推關(guān)系的建立 第02頁 五種典型的遞推關(guān)系 第03頁 遞推關(guān)系的求解方法 第06頁 四、遞推關(guān)系的應(yīng)用 第06頁 五、總結(jié) 第10頁【附錄】 第10頁【參考書目】 第12頁【程序描述】 第12頁 【正 文】一、 引論瞬息變幻的世界，每一件事物都在隨時(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ù)

3、學(xué)分支中都有重要作用，在一切向“更快、更高、更強(qiáng)”看齊的當(dāng)今信息學(xué)奧林匹克競賽中更因簡潔高效而顯示出其獨(dú)具的魅力。在遞推關(guān)系發(fā)揮重要作用的今天，深入研究其性質(zhì)、特點(diǎn)便成為一件十分必要的事情。本文就將圍繞著遞推關(guān)系的三大基本問題中的如何建立遞推關(guān)系展開論述，并通過例題說明遞推關(guān)系在當(dāng)今信息學(xué)競賽中的應(yīng)用。二、 遞推關(guān)系的定義相信每個(gè)人對(duì)遞推關(guān)系都不陌生，但若要說究竟?jié)M足什么樣的條件就是遞推關(guān)系，可能每個(gè)人又會(huì)有不同的說法。為了更好地研究遞推關(guān)系，首先讓我們明確什么是遞推關(guān)系?！径x1】給定一個(gè)數(shù)的序列h0,h1,hn,若存在整數(shù)n0，使當(dāng)nn0時(shí),可以用等號(hào)(或大于號(hào)、小于號(hào))將hn與其前面的某

4、些項(xiàng)hn(0in)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。三、 遞推關(guān)系的建立遞推關(guān)系中存在著三大基本問題：如何建立遞推關(guān)系，已給的遞推關(guān)系有何性質(zhì)，以及如何求解遞推關(guān)系。如果能弄清楚這三個(gè)方面的問題，相信我們對(duì)遞推關(guān)系的認(rèn)識(shí)又會(huì)推進(jìn)一步。由于篇幅所限，本文著重論述三大基本問題之一的如何建立遞推關(guān)系。建立遞推關(guān)系的關(guān)鍵在于尋找第n項(xiàng)與前面幾項(xiàng)的關(guān)系式，以及初始項(xiàng)的值。它不是一種抽象的概念，是需要針對(duì)某一具體題目或一類題目而言的。在下文中，我們將對(duì)五種典型的遞推關(guān)系的建立作比較深入具體的討論。1五種典型的遞推關(guān)系.fibonacci數(shù)列 在所有的遞推關(guān)系中，fibonacci數(shù)列應(yīng)該是最為大家所熟悉

5、的。在最基礎(chǔ)的程序設(shè)計(jì)語言logo語言中，就有很多這類的題目。而在較為復(fù)雜的basic、pascal、c語言中，fibonacci數(shù)列類的題目因?yàn)榻夥ㄏ鄬?duì)容易一些，逐漸退出了競賽的舞臺(tái)。可是這不等于說fibonacci數(shù)列沒有研究價(jià)值，恰恰相反，一些此類的題目還是能給我們一定的啟發(fā)的。fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家fibonacci于1202年提出的“兔子繁殖問題”(又稱“fibonacci問題”)。問題的提出：有雌雄一對(duì)兔子，假定過兩個(gè)月便可繁殖雌雄各一的一對(duì)小兔子。問過n個(gè)月后共有多少對(duì)兔子？解：設(shè)滿x個(gè)月共有兔子fx對(duì)，其中當(dāng)月新生的兔子數(shù)目為nx對(duì)。第x-1個(gè)月留

6、下的兔子數(shù)目設(shè)為ox對(duì)。則： fx=nx+ox而 ox=fx-1，nx=ox-1=fx-2 (即第x-2個(gè)月的所有兔子到第x個(gè)月都有繁殖能力了) fx=fx-1+fx-2 邊界條件：f0=0，f1=1由上面的遞推關(guān)系可依次得到f2=f1+f0=1，f3=f2+f1=2，f4=f3+f2=3，f5=f4+f3=5，。fabonacci數(shù)列常出現(xiàn)在比較簡單的組合計(jì)數(shù)問題中，例如以前的競賽中出現(xiàn)的“骨牌覆蓋”1問題、下文中的例題1等都可以用這種方法來解決。在優(yōu)選法2中，fibonacci數(shù)列的用處也得到了較好的體現(xiàn)。.hanoi塔問題問題的提出：hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組

7、成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖1所示。 a b c 圖1要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)則移到c柱上：(1)一次只能移一個(gè)圓盤；(2)圓盤只能在三個(gè)柱上存放；(3)在移動(dòng)過程中，不允許大盤壓小盤。問將這n個(gè)盤子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤次？解：設(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柱上，共記3個(gè)盤次，故h2=3。以此類推，當(dāng)a柱上有n(n2)個(gè)盤子時(shí)，總是先借助c柱把上面的n-

8、1個(gè)盤子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤子移動(dòng)到c柱上；總共移動(dòng)hn-1+1+hn-1個(gè)盤次。 hn=2hn-1+1 邊界條件：hn-1=1.平面分割問題問題的提出：12132412346578圖21234567108911121314n=1n=2n=3n=4設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。解：設(shè)an為n條封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。 由圖2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。從這些式子中可以看出an-an-1=2(n-

9、1)。當(dāng)然，上面的式子只是我們通過觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來試著證明一下。當(dāng)平面上已有n-1條曲線將平面分割成an-1個(gè)區(qū)域后，第n-1條曲線每與曲線相交一次，就會(huì)增加一個(gè)區(qū)域，因?yà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=1。平面分割問題是競賽中經(jīng)常觸及到的一類問題，由于其靈活多變，常常讓選手感到棘手，下文中的例題2是另一種平面分

10、割問題，有興趣的讀者不妨自己先試著求一下其中的遞推關(guān)系。.catalan數(shù)catalan數(shù)首先是由euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問題中。問題的提出：在一個(gè)凸n邊形中，通過不相交于n邊形內(nèi)部的對(duì)角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用hn表之，hn即為catalan數(shù)。例如五邊形有如下五種拆分方案(圖6-4)，故h5=5。求對(duì)于一個(gè)任意的凸n邊形相應(yīng)的hn。圖3p1pn圖4p2p3pkpn-1解：設(shè)cn表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個(gè)凸n邊形的任意一條邊都必然是一個(gè)三角形的一條邊，邊p1 pn也不例外，再根據(jù)

11、“不在同一直線上的三點(diǎn)可以確定一個(gè)三角形”，只要在p2，p3，pn-1點(diǎn)中找一個(gè)點(diǎn)pk(1k1,m1)邊界條件可以由定義2推導(dǎo)出： s2(n,0)=0；s2(n,1)=1；s2(n,n)=1；s2(n,k)=0(kn)。 第二類stirling數(shù)在競賽中較少出現(xiàn)，但在競賽中也有一些題目與其類似，甚至更為復(fù)雜。讀者不妨自己來試著建立其中的遞推關(guān)系。小結(jié)：通過上面對(duì)五種典型的遞推關(guān)系建立過程的探討，可知對(duì)待遞推類的題目，要具體情況具體分析，通過找到某狀態(tài)與其前面狀態(tài)的聯(lián)系，建立相應(yīng)的遞推關(guān)系。 2 遞推關(guān)系的求解方法求解遞推關(guān)系最簡單易行的方法是遞推，遞推是迭代算法中一種用若干步可重復(fù)的簡單運(yùn)算來

12、描述復(fù)雜數(shù)學(xué)問題的方法，以便于計(jì)算機(jī)進(jìn)行處理。它與遞推關(guān)系的思想完全一致，由邊界條件開始往后逐個(gè)推算，在一般情況下，效率較高，編程也非常的方便。但是，我們一般只需要求遞推關(guān)系的第n項(xiàng)，而邊界條件與第n項(xiàng)前面之間的若干項(xiàng)的信息是我們不需要的，如果采用遞推的方法來求解的話，第n項(xiàng)之前的每一項(xiàng)都必須計(jì)算出來，最后才能得到所需要的第n項(xiàng)的值。這是遞推無法避免的，從而在一定程度上影響了程序的效率。當(dāng)然在大多數(shù)情況下，采用遞推的方法還是可行的，在競賽中，使用遞推的方法編程，通常會(huì)在時(shí)限內(nèi)出解。當(dāng)然，更好的求解方法還有母函數(shù)法、迭代歸納法等等，這里就不再一一展開論述了。例如同樣是對(duì)于fibonacci數(shù)列問

13、題：遞推的方法要從f1，f2開始逐個(gè)推算出f3，f4fn，而利用母函數(shù)的方法，則可以得出公式，則可直接求出所需要的任意一項(xiàng)。四、 遞推關(guān)系的應(yīng)用遞推關(guān)系的應(yīng)用十分的廣泛，其中一個(gè)非常重要的應(yīng)用就是著名的楊輝三角(又稱“pascal三角”，見圖5)。楊輝三角是根據(jù)組合公式3畫出來的。很顯然，組合公式、楊輝三角都屬于遞推關(guān)系的范圍。11111111111233464510105n=1n=2n=3n=4n=5r=0r=1r=2r=3r=4圖5在今天的信息學(xué)競賽中，遞推關(guān)系的應(yīng)用也日趨廣泛，下面就讓我們從近年來的兩道競賽題中體會(huì)遞推關(guān)系的應(yīng)用。35791113468101214圖6例1(1998蚌埠市

14、競賽復(fù)試第一題)有一只經(jīng)過訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。試求出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。解：這是一道很典型的fibonacci數(shù)列類題目，其中的遞推關(guān)系很明顯。由于“蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行”的限制，決定了蜜蜂到b點(diǎn)的路徑只能是從b-1點(diǎn)或b-2點(diǎn)到達(dá)的，故fn=fn-1+fn-2 (a+2nb)，邊界條件fa=1，fa+1=1。(附有程序pro_1.pas)例2(1998合肥市競賽復(fù)試第二題)同一平面內(nèi)的n(n500)條直線，已知有p(p2)條直線相交于同一點(diǎn)，則這n條直線最多能將平面分割成多少個(gè)不同的區(qū)域？解：這道題目與第一部分中的平面分割問題十

15、分相似，不同之處就在于線條的曲直以及是否存在共點(diǎn)線條。由于共點(diǎn)直線的特殊性，我們決定先考慮p條相交于一點(diǎn)的直線，然后再考慮剩下的n-p條直線。首先可以直接求出p條相交于一點(diǎn)的直線將平面劃分成的區(qū)域數(shù)為2p個(gè)，然后在平面上已經(jīng)有k(kp)條直線的基礎(chǔ)上，加上一條直線，最多可以與k條直線相交，而每次相交都會(huì)增加一個(gè)區(qū)域，與最后一條直線相交后，由于直線可以無限延伸，還會(huì)再增加一個(gè)區(qū)域。所以fm=fm-1+m (mp)，邊界條件在前面已經(jīng)計(jì)算過了，是fp=2p。雖然這題看上去有兩個(gè)參數(shù)，但是在實(shí)際做題中會(huì)發(fā)現(xiàn)，本題還是屬于帶一個(gè)參數(shù)的遞推關(guān)系。(附有程序pro_2.pas)上面的兩道例題之中的遞推關(guān)系

16、比較明顯，說它們屬于的遞推關(guān)系類的試題，相信沒有人會(huì)質(zhì)疑。下面再讓我們來看另一道題目。1643126034-56700260-1-236853400-27-17407-560-1341242人 圖7例3(1999江蘇省組隊(duì)選拔賽試題第二題)在一個(gè)nm的方格中，m為奇數(shù)，放置有nm個(gè)數(shù)，如圖7： 圖8方格中間的下方有一人，此人可按照五個(gè)方向前進(jìn)但不能越出方格。如圖8所示：人每走過一個(gè)方格必須取此方格中的數(shù)。要求找到一條從底到頂?shù)穆窂?，使其?shù)相加之和為最大。輸出和的最大值。解：這題在本質(zhì)上類似于第一題，都是從一個(gè)點(diǎn)可以到達(dá)的點(diǎn)計(jì)算出可以到達(dá)一個(gè)點(diǎn)的所有可能點(diǎn)，然后從中發(fā)掘它們的關(guān)系。我們用坐標(biāo)(x

17、,y)唯一確定一個(gè)點(diǎn)，其中(m,n)表示圖的右上角，而人的出發(fā)點(diǎn)是，受人前進(jìn)方向的限制，能直接到達(dá)點(diǎn)(x,y)的點(diǎn)只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到點(diǎn)(x,y)的路徑中和最大的路徑必然要從到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的幾條路徑中產(chǎ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ù)字。邊界條件為

18、：，。(附有程序pro_3.pas)看到上面的題目，肯定有人會(huì)說，這不是遞推關(guān)系的應(yīng)用，這是動(dòng)態(tài)規(guī)劃；上面的關(guān)系式也不是遞推關(guān)系，而是動(dòng)態(tài)轉(zhuǎn)移方程。為什么呢？因?yàn)殛P(guān)系式中有取最大值運(yùn)算(max)，所以它屬于動(dòng)態(tài)規(guī)劃。是嗎？遞推關(guān)系的定義中只要求“用等號(hào)(或大于號(hào)、小于號(hào))將h(n)與其前面的某些項(xiàng)h(i)(0in)聯(lián)系起來”，聯(lián)系的含義很廣，當(dāng)然也包括用取最大(小)值運(yùn)算符聯(lián)系起來。所以我們認(rèn)為，上面的題目仍可屬于遞推關(guān)系，當(dāng)然，同時(shí)它也屬于動(dòng)態(tài)規(guī)劃。那么遞推關(guān)系動(dòng)態(tài)規(guī)劃圖9一般遞推關(guān)系遞推關(guān)系與動(dòng)態(tài)規(guī)劃之間到底是什么關(guān)系呢？我們不妨畫個(gè)venn圖(見圖9)。如果用數(shù)學(xué)式子表示，就是：a=遞推

19、關(guān)系b=動(dòng)態(tài)規(guī)劃，ba。通常人們理解的遞推關(guān)系就是一般遞推關(guān)系，故認(rèn)為動(dòng)態(tài)規(guī)劃與遞推關(guān)系是兩個(gè)各自獨(dú)立的個(gè)體。下面讓我們通過列表來分析一般遞推關(guān)系與動(dòng)態(tài)規(guī)劃之間的異同(見表1)。一般遞推關(guān)系與動(dòng)態(tài)規(guī)劃之間的異同對(duì)照表比較項(xiàng)目一般遞推關(guān)系動(dòng)態(tài)規(guī)劃有無后效性無無邊界條件一般很明顯一般比較隱蔽，容易被忽視一般形式hn=a1hn-1+a2hn-2+ arhn-r數(shù)學(xué)性較強(qiáng)hn=max+a數(shù)學(xué)性相對(duì)較弱是否有階段一般不劃分階段一般有較明顯的階段表1盡管一般遞推關(guān)系與動(dòng)態(tài)規(guī)劃之間存在著這樣和那樣的區(qū)別，但是在實(shí)際運(yùn)用中，人們還是經(jīng)常把它們混為一談，而且總是把一般遞推關(guān)系誤認(rèn)為是動(dòng)態(tài)規(guī)劃。這是因?yàn)閺纳蟼€(gè)世紀(jì)

20、五六十年代開始被人們發(fā)現(xiàn)的動(dòng)態(tài)規(guī)劃曾在信息學(xué)競賽中掀起了一陣巨浪，直到今天，它仍是信息學(xué)競賽中的重頭戲。但是，遞推關(guān)系的歷史源遠(yuǎn)流長，雖然一般遞推關(guān)系在今天不如動(dòng)態(tài)規(guī)劃那么炙手可熱，但是它對(duì)人的影響是不可忽視的。在ioi99的選拔賽中，就出現(xiàn)過一道01統(tǒng)計(jì)4，很多人只是先利用公式求組合數(shù)，再對(duì)組合數(shù)求和，來求a類數(shù)的個(gè)數(shù)，導(dǎo)致程序效率不高，其實(shí)，這是一道非常典型的遞推關(guān)系類題目5，由于選手平時(shí)對(duì)一般遞推關(guān)系的忽視，導(dǎo)致賽場失利。還有一類博弈問題也利用了遞推關(guān)系，讓我們來看一道關(guān)于這方面的例題。例4(1995學(xué)生計(jì)算機(jī)世界)寫一個(gè)計(jì)算機(jī)程序，讓計(jì)算機(jī)和人玩紙牌游戲，爭取計(jì)算機(jī)獲勝，并顯示整個(gè)游戲

21、過程。該游戲是：兩個(gè)選手(計(jì)算機(jī)一方，人為另一方)比賽：有n張(3n10000)紙牌，兩個(gè)選手交替地拿取(計(jì)算機(jī)先拿)，誰取走最后一張即誰勝。拿取規(guī)則為：第一個(gè)選手拿走1到n-1張牌(可拿任意張，但不能拿完)；以后，每個(gè)人可取1張或1張以上，但不得取走大于對(duì)方剛?cè)?shù)目的2倍(設(shè)對(duì)方剛?cè)∽遙張，則可取1到2b張)。解：這到題目看上去是一道很明顯的動(dòng)態(tài)規(guī)劃試題，以剩余牌數(shù)劃分階段，狀態(tài)fp,k表示剩余p張牌，且第一人最多可以取k張牌的情況是必?cái)↑c(diǎn)還是必贏點(diǎn)。狀態(tài)轉(zhuǎn)移方程是：fp,k=(pk) or fp,k-1 or not fp-k,2k (1pn，1kn)然后我們可以根據(jù)求出的各個(gè)狀態(tài)的情況設(shè)

22、計(jì)一種取牌方案，使計(jì)算機(jī)穩(wěn)贏，當(dāng)然，如果初始牌數(shù)是必?cái)↑c(diǎn)，那么計(jì)算機(jī)只能認(rèn)輸。在牌數(shù)不太多的情況下，這種方法效率比較高，但是一旦牌數(shù)很大(假設(shè)n達(dá)到極限)，那么需要的空間是o(105105)，必然會(huì)導(dǎo)致空間不夠的問題，這種方法就不可行。我們不妨把牌數(shù)較小的狀態(tài)畫成表來觀察(見表2)，看其中是否存在什么規(guī)律。通過表2可以很明顯的看出，如果剩余牌數(shù)為2、3、5、8張的話，無論先取牌的選手取多少張牌(假定不能夠一次取完所有的牌)，都必然會(huì)輸(除非另一個(gè)選手不想贏)；像2、3、5、8這類數(shù)字，我們稱之為“必?cái)∨茢?shù)”。在初始牌數(shù)不是必?cái)∨茢?shù)的情況下，我們要設(shè)計(jì)一種方案，使每次計(jì)算機(jī)取過x張牌后，剩余的紙

23、牌數(shù)大于2x張，且為必?cái)∨茢?shù)。那么究竟那些數(shù)字是必?cái)∨茢?shù)呢？從表中的數(shù)字2、3、5、8我們猜測(cè)fibonacci數(shù)列中從2開始的數(shù)字都是必?cái)?123456712345678注：表示true, 表示false表2kn牌數(shù)，并通過數(shù)學(xué)證明得證6。那么我們就可以根據(jù)求出的必?cái)∨茢?shù)設(shè)計(jì)方案了。如果想讓計(jì)算機(jī)在每一次取走x張牌后剩下的牌數(shù)是必?cái)∨茢?shù)，且大于2x張，看來是辦不到。例如，初始牌數(shù)20張，如果一次取走7張，使剩余13張的話，對(duì)手可以一次性將13張牌全部取走。那么我們只有再對(duì)7張牌設(shè)計(jì)一種方案，保證計(jì)算機(jī)能取到第7張牌，并且計(jì)算機(jī)最后一次取的牌數(shù)小于13/2張就可以了，而實(shí)現(xiàn)這一步這只需嵌套利用

24、次fibonacci數(shù)列就可以了(附有程序pro_4.pas)。小結(jié)：從上面的例題中可以看出，利用一般遞推關(guān)系解題有時(shí)會(huì)比動(dòng)態(tài)規(guī)劃更簡單，在動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)起來比較困難的情況下，一般遞推關(guān)系可能會(huì)產(chǎn)生重要作用，這種作用往往表現(xiàn)在直接求解或簡化動(dòng)態(tài)規(guī)劃過程兩方面。五、 總結(jié)通過上文對(duì)遞推關(guān)系的建立和在信息學(xué)競賽中的應(yīng)用的具體闡述，可知，遞推關(guān)系不是一種抽象的概念，它是具體的，是需要針對(duì)具體題目而言的，因此，我們無法找出一種方法建立出所有的遞推關(guān)系，只能根據(jù)需要解決的題目的具體條件來分析。雖然遞推關(guān)系的建立沒有一個(gè)固定的模式可循，但是從總體上來說，都要先找出題目中的重要條件，在這基礎(chǔ)上分析某一項(xiàng)與其前

25、面的若干項(xiàng)的關(guān)系，然后找出邊界條件。遞推關(guān)系在競賽中的應(yīng)用相當(dāng)?shù)膹V泛，它包含了幾乎每賽必考的動(dòng)態(tài)規(guī)劃，所以學(xué)好遞推關(guān)系的建立，無論是對(duì)提高我們的數(shù)學(xué)素質(zhì)，還是今后的競賽，都大有裨益。因?yàn)閯?dòng)態(tài)規(guī)劃更為大家所熟悉，所以本文著重說明了遞推關(guān)系中的一般遞推關(guān)系，希望能給選手一定的啟發(fā)。【附 錄】 3、6的證明是作者自己證明的，若有錯(cuò)誤之處，請(qǐng)指正。1 骨牌覆蓋：2n的棋盤用12的骨牌作完全覆蓋，求不同的覆蓋方式數(shù)cn2 優(yōu)選法：設(shè)函數(shù)y=fx在區(qū)間(a,b)上有一單峰極值點(diǎn)，假定為極大點(diǎn)。所謂單峰極值，即只有一個(gè)極點(diǎn)，而且當(dāng)x與偏離越大，偏差|f(x)-f()|也越大。要求用若干次試驗(yàn)找到點(diǎn)準(zhǔn)確到一定

26、的程度。較優(yōu)的是實(shí)驗(yàn)方法有0.618優(yōu)選法和fibonacci優(yōu)選法。3 組合公式的證明： 證畢。4 01序列：近來ioi的專家們?cè)谶M(jìn)行一項(xiàng)有關(guān)二進(jìn)制數(shù)的研究，研究設(shè)計(jì)的一個(gè)統(tǒng)計(jì)問題令他們大傷腦筋。問題是這樣的：對(duì)于一個(gè)自然數(shù)n，可以把他轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)，其中：n=ak2k+ak-12k-1+a121+a0；而且ai=0或1(0ik)，ak=1。如：10=1010；5=101。我們統(tǒng)計(jì)一下a0ak，這k+1個(gè)數(shù)中0的個(gè)數(shù)和1的個(gè)數(shù)。如果在這k+1個(gè)數(shù)中，0的個(gè)數(shù)比1的個(gè)數(shù)多，就稱為a類數(shù)。現(xiàn)在的任務(wù)是，對(duì)于一個(gè)給定的m，求1m中a類數(shù)的個(gè)數(shù)。5 有關(guān)于01統(tǒng)計(jì)的解法可參見徐靜同學(xué)的解題報(bào)告

27、。6 證明：用數(shù)學(xué)歸納法證明：1. 由表2 可以得知：fibonacci數(shù)2、3、5、是必?cái)∨茢?shù)，且在(1,5)之間的其他牌數(shù)都是必贏牌數(shù)2. 假設(shè)fibonacci數(shù)列f1,f2fi,fi+1滿足在(f1,fi+1區(qū)間，只有fibonacci數(shù)才是必?cái)∨茢?shù)，且其他牌數(shù)都是必贏牌數(shù)。則我們可證明在(f1,fi+2區(qū)間的牌數(shù)也滿足上面的性質(zhì)。證明如下： 設(shè)剩下fi+2張牌，設(shè)這一次，計(jì)算機(jī)取了x張牌，則剩下牌數(shù)為p=fi+2-x張(1) 若xfi，則pfi+1， fi=fi+fi-1且fi-1fi fi+12fi p2x 人可以一次將剩下的p張牌全部取完 計(jì)算機(jī)一定會(huì)輸(2) 若1xfi+1，

28、fi+2-fi=fi+1且fi+1是fibonacci數(shù) 計(jì)算機(jī)無法通過一種取牌方案，使計(jì)算機(jī)在某一次取過少于fi+1/2張牌后，剩下fi+1張牌 當(dāng)剩下fi+1張牌的時(shí)候，必然輪到計(jì)算機(jī)取，且計(jì)算機(jī)這時(shí)不能一次將所有牌取完 fi+1是fibonacci數(shù) 計(jì)算機(jī)一定會(huì)輸 又p(fi+1,fi+2),即剩下p張牌輪到人取的時(shí)候，人一定獲勝， p是必贏牌數(shù)3. 由1、2可得結(jié)論成立。 證畢?！緟⒖紩俊?楊振生 編著 王樹禾 審 組合數(shù)學(xué)及其算法 中國科技大學(xué)出版社 19972孫淑玲 許胤龍 組合數(shù)學(xué)引論 中國科技大學(xué)出版社出版 19993盧開澄 組合數(shù)學(xué) 清華大學(xué)出版社 19914吳文虎 王建

29、德 青少年國際和全國信息學(xué)(計(jì)算機(jī))奧林匹克競賽指導(dǎo)組合數(shù)學(xué)的算法與程序設(shè)計(jì) 清華大學(xué)出版社 19975吳文虎 主編 信息學(xué)(計(jì)算機(jī))奧林匹克高級(jí)本 北京大學(xué)出版社 19926吳文虎 主編 信息學(xué)(計(jì)算機(jī))奧林匹克中級(jí)本 北京大學(xué)出版社 1992【程序描述】pro_1.pasprogram pro_1;蜂巢問題，最大范圍：目標(biāo)點(diǎn)與出發(fā)點(diǎn)之差不超過40000 type tarr=array1.10000 of byte; tnum=array1.4 of tarr; tlen=array1.4 of word; varstart,finish:longint;出發(fā)點(diǎn)和目標(biāo)點(diǎn)num:tnum;nu

30、m1num3分別保存到達(dá)相鄰三個(gè)蜂巢的路徑數(shù)；num4是用于交換的臨時(shí)變量len:tlen;leni表示numi的長度 procedure datainit;數(shù)據(jù)初始化 var i:integer; begin for i:=1 to 3 do begin new(numi); fillchar(numi,sizeof(numi),0); numi1:=1; leni:=1; end; end; procedure add;高精度加法運(yùn)算：num3=num1+num2 var i,carry:word;carry是進(jìn)位數(shù)字 begin carry:=0; for i:=1 to len2 do

31、 begin carry:=carry+num2i+num1i; num3i:=carry mod 10; carry:=carry div 10; end; len3:=i; if carry0 then begin inc(len3); num3i+1:=carry; end; end; procedure work;求從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路徑總數(shù) var i:longint; begin num11:=1; num21:=1; for i:=start+2 to finish do begin add;高精度加法運(yùn)算：num3=num1+num2 num4:=num1; num1:=num

32、2; num2:=num3; num3:=num4; len4:=len1; move(len2,len1,6); end; end; procedure out;輸出結(jié)果 var i:integer; begin for i:=len2 downto 1 do write(num2i); writeln; end; begin datainit; 數(shù)據(jù)初始化 write(input: ); readln(start,finish); work; 求從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路徑總數(shù) out; 輸出結(jié)果 end.pro_2.pasprogram pro_2;第二種平面分割問題 var n,p,tota

33、l,i:longint;total是區(qū)域總數(shù) begin write(n=); readln(n); write(p=); readln(p); total:=p*2; for i:=p+1 to n do inc(total,i); 也可用total:=(p+n+1*(n-p) div 2 writeln(total area:,total); end.pro_3.pasprogram pro_3;取數(shù) const infns=pro_3.in; sign=-10000000;不可到達(dá)的點(diǎn)的標(biāo)志 type tarr=array0.100,1.101 of longint; var num:t

34、arr;保存每個(gè)點(diǎn)上的數(shù)字 sum:tarr; 保存到每個(gè)點(diǎn)的和最大是多少n, 方格的高度m:integer; 方格的寬度 procedure readin;讀入數(shù)據(jù)并初始化 var ni,mi:integer; begin assign(input,infns); reset(input); readln(n,m); new(num); for ni:=n downto 1 do for mi:=1 to m do begin read(numni,mi); end; for mi:=1 to m do sum0,mi:=sign; 置不可到達(dá)的點(diǎn)的標(biāo)志 sum0,m div 2+1:=0;人的出發(fā)點(diǎn) close(input); end;