1、NOIP基礎(chǔ)算法綜合第二部分遞推策略一、引例：Fibonacci數(shù)列 Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”(又稱“Fibonacci問題”)。問題： 一個(gè)數(shù)列的第0項(xiàng)為0，第1項(xiàng)為1，以后每一項(xiàng)都是前兩項(xiàng)的和，這個(gè)數(shù)列就是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第N項(xiàng)。 解答由問題,可寫出遞推方程算法： f0:=0; f1:=1; for i:=2 to n do fi:=fi1+fi2;0 (n=0)1 (n=1)總結(jié)從這個(gè)問題可以看出，在計(jì)算裴波那契數(shù)列的每一項(xiàng)目時(shí)，都可以由前兩項(xiàng)推出。這樣，相鄰兩項(xiàng)之間的變化有一定的規(guī)律性，

2、我們可以將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式：Fn=g(Fn-1)，這就在數(shù)的序列中，建立起后項(xiàng)和前項(xiàng)之間的關(guān)系。然后從初始條件（或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值）。很多問題就是這樣逐步求解的。對一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就可以遞推了，接下來便是讓計(jì)算機(jī)一步步了。讓高速的計(jì)算機(jī)從事這種重復(fù)運(yùn)算，真正起到“物盡其用”的效果。二、遞推概念給定一個(gè)數(shù)的序列H0,H1,Hn,若存在整數(shù)n0，使當(dāng)nn0時(shí),可以用等號(或大于號、小于號)將Hn與其前面的某些項(xiàng)Hi(0in)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。如何建立遞推

3、關(guān)系遞推關(guān)系有何性質(zhì)如何求解遞推關(guān)系 三、解決遞推問題的一般步驟 建立遞推關(guān)系式 確定邊界條件 遞推求解 四、遞推的兩種形式順推法和倒推法五、遞推的應(yīng)用分類 一般遞推問題 組合計(jì)數(shù)類問題 一類博弈問題的求解 動(dòng)態(tài)規(guī)劃問題的遞推關(guān)系例題1：faibonacci數(shù)列 【問題描述】已知faibonacci數(shù)列的前幾個(gè)數(shù)分別為0，1，1，2，3，5，編程求出此數(shù)列的第n項(xiàng)。（n=60）（一）遞推的應(yīng)用（一般遞推問題）（一）遞推的應(yīng)用（一般遞推問題） 例題2：輸出楊輝三角的前N行 【問題描述】輸出楊輝三角的前N行(N10)。【文件輸入】輸入只有一行，包括1個(gè)整數(shù)N(N2)個(gè)盤子時(shí)，我們可以利用下列步驟：

4、第一步：先借助3柱把1柱上面的n-1個(gè)盤子移動(dòng)到2柱上，所需的 移動(dòng)次數(shù)為f(n-1)。第二步：然后再把1柱最下面的一個(gè)盤子移動(dòng)到3柱上，只需要1 次盤子。第三步：再借助1柱把2柱上的n-1個(gè)盤子移動(dòng)到3上，所需的移動(dòng) 次數(shù)為f(n-1)。由以上3步得出總共移動(dòng)盤子的次數(shù)為：f(n-1)+1+ f(n-1)。所以：f(n)=2 f(n-1)+1 hn=2hn-1+1 =2n-1 邊界條件：h1=1【擴(kuò)展1】： Hanoi雙塔問題 【問題描述】給定A,B,C三根足夠長的細(xì)柱，在A柱上放有2n個(gè)中間有空的圓盤，共有n個(gè)不同的尺寸，每個(gè)尺寸都有兩個(gè)相同的圓盤，注意這兩個(gè)圓盤是不加區(qū)分的(下圖為n=3

5、的情形）。現(xiàn)要將 這些圓盤移到C柱上，在移動(dòng)過程中可放在B柱上暫存。要求: (1)每次只能移動(dòng)一個(gè)圓盤；(2) A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序；任務(wù):設(shè)An為2n個(gè)圓盤完成上述任務(wù)所需的最少移動(dòng)次數(shù)，對于輸入的n，輸出An。 【輸入】 輸入為一個(gè)正整數(shù)n，表示在A柱上放有2n個(gè)圓盤。 【輸出】 輸出僅一行，包含一個(gè)正整數(shù)，為完成上述任務(wù)所需的最少移動(dòng)次數(shù)An。遞推方程： An=2*An-1+2【擴(kuò)展2】：四塔問題【問題分析】令fi表示四個(gè)柱子時(shí)，把i個(gè)盤子從原柱移動(dòng)到目標(biāo)柱所需的最少移動(dòng)次數(shù)。 j第一步：先把1柱上的前j個(gè)盤子移動(dòng)到另外其中一個(gè)非目標(biāo)柱（2或3柱均可，假設(shè)移到

6、2柱）上，此時(shí)3和4柱可以作為中間柱。移動(dòng)次數(shù)為：fj。第二步：再把原1柱上剩下的i-j個(gè)盤子在3根柱子（1、3、4）之間移動(dòng)，最后移動(dòng)到目標(biāo)柱4上，因?yàn)榇藭r(shí)2柱不能作為中間柱子使用，根據(jù)三柱問題可知，移動(dòng)次數(shù)為：2(i-j)-1。第三步：最后把非目標(biāo)柱2柱上的j個(gè)盤子移動(dòng)到目標(biāo)柱上，次數(shù)為：fj。 i通過以上步驟我們可以初步得出： fi = 2*fj+2(i-j)-1j可取的范圍是1=ji，所以對于不同的j，得到的fi可能是不同的，本題要求最少的移動(dòng)次數(shù)。 fi=min2*fj+2(i-j)-1，其中1=ji【擴(kuò)展3】：m塔問題【問題分析】 設(shè)F(m,n)為m根柱子,n個(gè)盤子時(shí)移動(dòng)的最少次數(shù)

7、： 1、先把1柱上的前j個(gè)盤子移動(dòng)到另外其中一個(gè)除m柱以外的非目標(biāo)柱上，移動(dòng)次數(shù)為：fm, j； 2、再把原1柱上剩下的n-j個(gè)盤子在m-1根柱子之間移動(dòng)，最后移動(dòng)到目標(biāo)柱m上，移動(dòng)次數(shù)為：fm-1, n-j； 3、最后把非目標(biāo)柱上的j個(gè)盤子移動(dòng)到目標(biāo)柱沒柱上，移動(dòng)次數(shù)為：fm, j。F(m,n)=min2*F(m,j)+F(m-1,n-j) (1=jn)j（一）遞推的應(yīng)用（一般遞推問題） 例題4:數(shù)的計(jì)數(shù) 【問題描述】我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)，先輸入一個(gè)自然數(shù)n(n1000)，然后對此自然數(shù)按照如下方法進(jìn)行處理： (1)、不作任何處理； (2)、在它的左邊加上一

8、個(gè)自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半； (3)、加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止； 【樣例輸入】6 滿足條件的數(shù)為6（此部分不必輸出） 16 26 36 126 136【樣例輸出】6 方法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)。 方法2：是對方法1的改進(jìn)。我們定義數(shù)組s。 s(x)=h(1)+h(2)+h(x) =s(x-1)+h(x) h(x)=s(x)-s(x-1) 此算法的時(shí)

9、間復(fù)雜度可降到O(n)。程序：for i:=1 to n do begin hi:=1+si div 2; s:=si-1+fi end;writeln(hn);方法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);程序：for i:=2 to n do if odd(i) then hi:=hi-1 else hi:=hi-1+hi div 2;writeln(hn);（一）遞推的應(yīng)用（一般遞推問題）例題5：猴子吃桃問題1538【問題描述】猴子摘了一堆桃，第一天吃了一半

10、，還嫌不過癮，又吃了一個(gè)；第二天又吃了剩下的一半零一個(gè)；以后每天如此。到第n天，猴子一看只剩下一個(gè)了。問最初有多少個(gè)桃子？ 【擴(kuò)展練習(xí)】猴子分桃 【問題描述】有一堆桃子和N只猴子，第一只猴子將桃子平均分成了M堆后，還剩了1個(gè)，它吃了剩下的一個(gè)，并拿走一堆。后面的猴子也和第1只進(jìn)行了同樣的做法，請問N只猴子進(jìn)行了同樣做法后這一堆桃子至少還剩了多少個(gè)桃子(假設(shè)剩下的每堆中至少有一個(gè)桃子)？而最初時(shí)的那堆桃子至少有多少個(gè)？ 【文件輸入】輸入包含二個(gè)數(shù)據(jù)，數(shù)據(jù)間用空格隔開。第一個(gè)數(shù)據(jù)為猴子的只數(shù)N(1N10)，第二個(gè)數(shù)據(jù)為桃子分成的堆數(shù)M(2M7)。 【文件輸出】輸出包含兩行數(shù)據(jù)，第一行數(shù)據(jù)為剩下的桃

11、子數(shù)，第二行數(shù)據(jù)為原來的桃子數(shù)。 【樣例輸入】3 2 【樣例輸出】 1 15（一）遞推的應(yīng)用（一般遞推問題）【例題6】傳球游戲（NOIP2008普及）【問題描述】上體育課的時(shí)候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。 游戲規(guī)則是這樣的：n（3=n=30）個(gè)同學(xué)站成一個(gè)圓圈，其中的一個(gè)同學(xué)手里拿著一個(gè)球，當(dāng)老師吹哨子時(shí)開始傳球，每個(gè)同學(xué)可以把球傳給自己左右的兩個(gè)同學(xué)中的一個(gè)（左右任意），當(dāng)老師再吹哨子時(shí)，傳球停止，此時(shí)，拿著球沒傳出去的那個(gè)同學(xué)就是敗者，要給大家表演一個(gè)節(jié)目。 聰明的小蠻提出一個(gè)有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了

12、m（3=m2-3-1和1-3-2-1，共兩種。 分析設(shè)fi,k表示經(jīng)過k次傳到編號為i的人手中的方案數(shù)，傳到i號同學(xué)的球只能來自于i的左邊一個(gè)同學(xué)和右邊一個(gè)同學(xué)，這兩個(gè)同學(xué)的編號分別是i-1和i+1，所以可以得到以下的遞推公式： fi,k=fi-1,k-1+fi+1,k-1 f1,k=fn,k-1+f2,k-1, 當(dāng)i=1時(shí) fn,k=fn-1,k-1+f1,k-1, 當(dāng)i=n時(shí) 邊界條件：f1,0=1； answer=f1,m參考代碼 readln(n,m); f1,0:=1; for k:=1 to m do begin f1,k:=f2,k-1+fn,k-1; for i:=2 to n

13、-1 do fi,k:=fi-1,k-1+fi+1,k-1; fn,k:=fn-1,k-1+f1,k-1; end; writeln(f1,m);（二）遞推的應(yīng)用（組合計(jì)數(shù)）Catalan數(shù)（卡塔蘭數(shù)）例題7：凸n邊形的三角形剖分在一個(gè)凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用f(n)表之，f(n)即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故f(5)=5。求對于一個(gè)任意的凸n邊形相應(yīng)的f(n)。分析:設(shè)f(n)表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個(gè)凸n邊形的任意一條邊都必然是一個(gè)三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在同

14、一直線上的三點(diǎn)可以確定一個(gè)三角形”，只要在P2，P3，Pn-1點(diǎn)中找一個(gè)點(diǎn)Pk(1kn)，與P1、Pn 共同構(gòu)成一個(gè)三角形的三個(gè)頂點(diǎn)，就將n邊形分成了三個(gè)不相交的部分(如圖)，我們分別稱之為區(qū)域、區(qū)域、區(qū)域，其中區(qū)域必定是一個(gè)三角形，區(qū)域是一個(gè)凸k邊形，區(qū)域是一個(gè)凸n-k+1邊形，區(qū)域的拆分方案總數(shù)是f(k)，區(qū)域的拆分方案數(shù)為f(n-k+1)，故包含P1PkPn的n 邊形的拆分方案數(shù)為f(k)*f(n-k+1)種，而Pk可以是P2，P3，Pn-1種任一點(diǎn)，根據(jù)加法原理，凸n邊形的三角拆分方案總數(shù)為:邊界條件：f(3)=1【擴(kuò)展1】：二叉樹數(shù)目【問題描述】：求n個(gè)結(jié)點(diǎn)能構(gòu)成不同二叉數(shù)的數(shù)目?！?/p>

15、問題分析】： 設(shè)F(n)為n個(gè)結(jié)點(diǎn)組成二叉樹的數(shù)目。 容易知道：f(1)=1;f(2)=2,f(3)=5 選定1個(gè)結(jié)點(diǎn)為根，左子樹結(jié)點(diǎn)的個(gè)數(shù)為i，二叉樹數(shù)目f(i)種；右子樹結(jié)點(diǎn)數(shù)目為n-i-1，二叉樹數(shù)目f(n-i-1)種，i的可取范圍0，n-1。所以有： 為了計(jì)算的方便：約定f(0)=1【擴(kuò)展2】：出棧序列【問題描述】：N個(gè)不同元素按一定的順序入棧，求不同的出棧序列數(shù)目。【問題分析】設(shè)f(n)為n個(gè)元素的不同出棧序列數(shù)目。 容易得出：f(1)=1；f(2)=2。 第n個(gè)元素可以第i(1=i=n)個(gè)出棧，前面已出棧有i-1個(gè)元素，出棧方法：f(i-1)；后面出棧n-i 個(gè)元素，出棧方法為：f

16、(n-i)。所以有： 初始條件： F(0)=1 （二）遞推的應(yīng)用（組合計(jì)數(shù)）例題10：錯(cuò)排問題（經(jīng)典問題）n個(gè)數(shù)，分別為1n，排成一個(gè)長度為n的排列。若每一個(gè)數(shù)的位置都與數(shù)的本身不相等，則稱這個(gè)排列是一個(gè)錯(cuò)排。例如，n=3，則錯(cuò)排有2 3 1、3 1 2。編寫程序，求n的錯(cuò)排個(gè)數(shù)分析我們設(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,4,1,3);(2,3,4,1) (4,1,2,3);(3,4,2,1);(3,1,4,2)它們有什么規(guī)律呢？通過反復(fù)的試驗(yàn)

17、，我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生錯(cuò)位排列：第一步，把第n個(gè)元素放在一個(gè)位置，比如位置k，一共有n-1種方法；第二步，放編號為k的元素，這時(shí)有兩種情況 把它放到位置n，那么，對于剩下的n-1個(gè)元素，由于第k個(gè)元素放到了位置n，剩下n-2個(gè)元素就有f(n-2）種方法； 第k個(gè)元素不把它放到位置n，這時(shí)，對于這n-1個(gè)元素，有f(n-1）種方法；f(k)=(k-1)*(f(k1)+f(k2)分析我們得到求錯(cuò)位排列的遞推公式f(k):（三）遞推的應(yīng)用（博弈問題）例題13：走直線棋問題。有如下所示的一個(gè)編號為到的方格： 現(xiàn)由計(jì)算機(jī)和人進(jìn)行人機(jī)對奕，從到，每次可以走個(gè)方格，其中為集=a1,a2, a3,.a

18、m中的元素(m=4)，規(guī)定誰最先走到第n格為勝，試設(shè)計(jì)一個(gè)人機(jī)對奕方案，摸擬整個(gè)游戲過程的情況并力求計(jì)算機(jī)盡量不敗。12345 N-1N分析題設(shè)條件：若誰先走到第N格誰將獲勝，例如，假設(shè)S=1,2，從第N格往前倒推，則走到第N-1格或第N-2格的一方必?cái)?，而走到第N-3格者必定獲勝，因此在N，S確定后，棋格中每個(gè)方格的勝、負(fù)或和態(tài)（雙方都不能到達(dá)第N格）都是可以事先確定的。將目標(biāo)格置為必勝態(tài)，由后往前倒推每一格的勝負(fù)狀態(tài)，規(guī)定在自己所處的當(dāng)前格后，若對方無論走到哪兒都必定失敗，則當(dāng)前格為勝態(tài)，若走后有任一格為勝格，則當(dāng)前格為輸態(tài)，否則為和態(tài)。分析 設(shè)1表示必勝態(tài)，-1表示必?cái)B(tài)，0表示和態(tài)或表示無法到達(dá)的棋格。 例如，設(shè)N