高中信息奧賽-五種典型的遞推關(guān)系

Ⅰ.Fibonacci數(shù)列在所有的遞推關(guān)系中，F(xiàn)ibonacci數(shù)列應(yīng)該是最為大家所熟悉的。在最根底的程序設(shè)計(jì)語(yǔ)言Logo語(yǔ)言中，就有很多這類的題目。而在較為復(fù)雜的Basic、Pascal、C語(yǔ)言中，F(xiàn)ibonacci數(shù)列類的題目因?yàn)榻夥ㄏ鄬?duì)容易一些，逐漸退出了競(jìng)賽的舞臺(tái)。可是這不等于說(shuō)Fibonacci數(shù)列沒有研究?jī)r(jià)值，恰恰相反，一些此類的題目還是能給我們一定的啟發(fā)的。Fibonacci數(shù)列的代表問(wèn)題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問(wèn)題”(又稱“Fibonacci問(wèn)題”)。問(wèn)題的提出：有雌雄一對(duì)兔子，假定過(guò)兩個(gè)月便可繁殖雌雄各一的一對(duì)小兔子。問(wèn)過(guò)n個(gè)月后共有多少對(duì)兔子？解：設(shè)滿x個(gè)月共有兔子Fx對(duì)，其中當(dāng)月新生的兔子數(shù)目為Nx對(duì)。第x-1個(gè)月留下的兔子數(shù)目設(shè)為Fx-1對(duì)。那么：Fx=Nx+Fx-1Nx=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，F(xiàn)3=F2+F1=2，F(xiàn)4=F3+F2=3，F(xiàn)5=F4+F3=5，……。Fabonacci數(shù)列常出現(xiàn)在比較簡(jiǎn)單的組合計(jì)數(shù)問(wèn)題中，例如以前的競(jìng)賽中出現(xiàn)的“骨牌覆蓋”問(wèn)題。在優(yōu)選法中，F(xiàn)ibonacci數(shù)列的用處也得到了較好的表達(dá)。五種典型的遞推關(guān)系Ⅱ.Hanoi塔問(wèn)題問(wèn)題的提出：Hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖3-11所示。要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)那么移到c柱上：(1)一次只能移一個(gè)圓盤；(2)圓盤只能在三個(gè)柱上存放；(3)在移動(dòng)過(guò)程中，不允許大盤壓小盤。問(wèn)將這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-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è)盤次?！鄅n=2hn-1+1邊界條件：h1=1Ⅲ.平面分割問(wèn)題問(wèn)題的提出：設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問(wèn)這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。解：設(shè)an為n條封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。由圖3-13可以看出：a2-a1=2；a3-a2=4；a4-a3=6。從這些式子中可以看出an-an-1=2(n-1)。當(dāng)然，上面的式子只是我們通過(guò)觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來(lái)試著證明一下。當(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。平面分割問(wèn)題是競(jìng)賽中經(jīng)常觸及到的一類問(wèn)題，由于其靈活多變，常常感到棘手，下面的【例7】是另一種平面分割問(wèn)題，有興趣的讀者不妨自己先試著求一下其中的遞推關(guān)系。Ⅳ.Catalan數(shù)Catalan數(shù)首先是由Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問(wèn)題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問(wèn)題中。問(wèn)題的提出：在一個(gè)凸n邊形中，通過(guò)不相交于n邊形內(nèi)部的對(duì)角線，把n邊形拆分成假設(shè)干三角形，不同的拆分?jǐn)?shù)目用hn表示，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方案(圖3-14)，故h5=5。求對(duì)于一個(gè)任意的凸n邊形相應(yīng)的hn。Catalan數(shù)是比較復(fù)雜的遞推關(guān)系，尤其在競(jìng)賽的時(shí)候，選手很難在較短的時(shí)間里建立起正確的遞推關(guān)系。當(dāng)然，Catalan數(shù)類的問(wèn)題也可以用搜索的方法來(lái)完成，但是，搜索的方法與利用遞推關(guān)系的方法比較起來(lái)，不僅效率低，編程復(fù)雜度也陡然提高。Ⅴ.第二類Stirling數(shù)在五類典型的遞推關(guān)系中，第二類Stirling是最不為大家所熟悉的。也正因?yàn)槿绱?，我們有必要先解釋一下什么是第二類Strling數(shù)。【定義2】n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無(wú)一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)。下面就讓我們根據(jù)定義來(lái)推導(dǎo)帶兩個(gè)參數(shù)的遞推關(guān)系——第二類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)。綜合以上兩種情況，可以得出第二類Stirling數(shù)定理：【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)(n>1,m1)邊界條件可以由定義2推導(dǎo)出：S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。第二類Stirling數(shù)在競(jìng)賽中較少出現(xiàn)，但在競(jìng)賽中也有一些題目與其類似，甚至更為復(fù)雜。讀者不妨自己來(lái)試著建立其中的遞推關(guān)系。小結(jié)：通過(guò)上面對(duì)五種典型的遞推關(guān)系建立過(guò)程的探討，可知對(duì)待遞推類的題目，要具體情況具體分析，通過(guò)找到某狀態(tài)與其前面狀態(tài)的聯(lián)系，建立相應(yīng)的遞推關(guān)系?！纠?】(1998合肥市競(jìng)賽復(fù)試第二題)同一平面內(nèi)的n(n500)條直線，有p(p2)條直線相交于同一點(diǎn)，那么這n條直線最多能將平面分割成多少個(gè)不同的區(qū)域？解：這道題目與第一局部中的平面分割問(wèn)題十分相似，不同之處就在于線條的曲直以及是否存在共點(diǎn)線條。由于共點(diǎn)直線的特殊性，我們決定先考慮p條相交于一點(diǎn)的直線，然后再考慮剩下的n-p條直線。首先可以直接求出p條相交于一點(diǎn)的直線將平面劃分成的區(qū)域數(shù)為2p個(gè)，然后在平面上已經(jīng)有k(kp)條直線的根底上，加上一條直線，最多可以與k條直線相交，而每次相交都會(huì)增加一個(gè)區(qū)域，與最后一條直線相交后，由于直線可以無(wú)限延伸，還會(huì)再增加一個(gè)區(qū)域。所以fm=fm-1+m(m>p)，邊界條件在前面已經(jīng)計(jì)算過(guò)了，是fp=2p。雖然這題看上去有兩個(gè)參數(shù)，但是在實(shí)際做題中會(huì)發(fā)現(xiàn)，此題還是屬于帶一個(gè)參數(shù)的遞推關(guān)系。【上機(jī)練習(xí)】1、走樓梯樓梯有N級(jí)臺(tái)階，上樓可以一步上一階，也可以一步上二階。編一遞歸程序，計(jì)算共有多少種不同走法？【輸入樣例】Stairs.in3【輸出樣例】Stairs.out32、兔子繁殖有一種兔子，出生后一個(gè)月就可以長(zhǎng)大，然后再過(guò)一個(gè)月一對(duì)長(zhǎng)大的兔子就可以生育一對(duì)小兔子且以后每個(gè)月都能生育一對(duì)。現(xiàn)在，我們有一對(duì)剛出生的這種兔子，那么，n個(gè)月過(guò)后，我們會(huì)有多少對(duì)兔子呢？假設(shè)所有的兔子都不會(huì)死亡。【輸入格式】輸入文件僅一行，包含一個(gè)自然數(shù)n?！据敵龈袷健枯敵鑫募H一行，包含一個(gè)自然數(shù)，即n個(gè)月后兔子的對(duì)數(shù)?！据斎霕永縍abbit.in5【輸出樣例】Rabbit.out53、平面分割同一平面內(nèi)有n〔n≤500〕條直線，其中p〔p≥2〕條直線相交于同一點(diǎn)，那么這n條直線最多能將平面分割成多少個(gè)不同的區(qū)域？【輸入格式】?jī)蓚€(gè)整數(shù)n〔n≤500〕和p〔2≤p≤n〕。【輸出格式】一個(gè)正整數(shù)，代表最多分割成的區(qū)域數(shù)目?！据斎霕永縎urface.in125【輸出樣例】Surface.out734、骨牌鋪法有1×n的一個(gè)長(zhǎng)方形，用一個(gè)1×1、1×2和1×3的骨牌鋪滿方格。例如當(dāng)n=3時(shí)為1×3的方格。此時(shí)用1×1、1×2和1×3的骨牌鋪滿方格，共有四種鋪法。如以下圖：【輸入樣例】Domino.in3【輸出樣例】Domino.out45、蜜蜂路線【問(wèn)題描述】一只蜜蜂在以下圖所示的數(shù)字蜂房上爬動(dòng),它只能從標(biāo)號(hào)小的蜂房爬到標(biāo)號(hào)大的相鄰蜂房,現(xiàn)在問(wèn)你：蜜蜂從蜂房M開始爬到蜂房N，M<N，有多少種爬行路線？【輸入格式】

輸入M，N的值?！据敵龈袷健?/p>

爬行有多少種路線?！据斎霕永縝ee.in114【輸出樣例】bee.out3776、數(shù)塔問(wèn)題【問(wèn)題描述】設(shè)有一個(gè)三角形的數(shù)塔，頂點(diǎn)為根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一個(gè)整數(shù)值。從頂點(diǎn)出發(fā)，可以向左走或向右走，如下圖：假設(shè)要求從根結(jié)點(diǎn)開始，請(qǐng)找出一條路徑，使路徑之和最大，只要輸出路徑的和?！据斎敫袷健康谝恍袨閚(n<10)，表示數(shù)塔的層數(shù)從第2行至n+1行，每行有假設(shè)干個(gè)數(shù)據(jù)，表示數(shù)塔中的數(shù)值?！据敵龈袷健枯敵雎窂胶妥畲蟮穆窂街??！据斎霕永縯ower.in51311812726614158127132411【輸出樣例】tower.out867、過(guò)河卒〔NOIP2002〕【問(wèn)題描述】棋盤上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)那么：可以向下、或者向右。同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬〔如C點(diǎn)〕，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)〔如圖中的C點(diǎn)和P1，P2，……，P8〕。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n,m)(n,m為不超過(guò)20的整數(shù)),同樣馬的位置坐標(biāo)是需要給出的，C≠A且C≠B。現(xiàn)在輸入B點(diǎn)坐標(biāo)和C點(diǎn)的坐標(biāo)，要你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。【輸入樣例】knight.in4824【輸出樣例】knight.out0