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

2、的遞推關(guān)系式：Fn=g(Fn-1)，這就在數(shù)的序列中，建立起后項和前項之間的關(guān)系。然后從初始條件（或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值）。很多問題就是這樣逐步求解的。 對一個試題，我們要是能找到后一項與前一項的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就可以遞推了，接下來便是讓計算機一步步了。讓高速的計算機從事這種重復運算，真正起到“物盡其用”的效果。,遞推法,所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系，逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡后確定。 可用遞推算法求解的題目一般有以下二個特點： 1、

3、問題可以劃分成多個狀態(tài)； 2、除初始狀態(tài)外，其它各個狀態(tài)都可以用固定的遞推關(guān)系式來表示。 在我們實際解題中，題目不會直接給出遞推關(guān)系式，而是需要通過分析各種狀態(tài)，找出遞推關(guān)系式。,二、遞推概念,給定一個數(shù)的序列H0,H1,Hn,若存在整數(shù)n0，使當nn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0in)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。 如何建立遞推關(guān)系 遞推關(guān)系有何性質(zhì) 如何求解遞推關(guān)系,三、解決遞推問題的一般步驟,建立遞推關(guān)系式 確定邊界條件 遞推求解,四、遞推的兩種形式,順推法和倒推法,采用具體化、特殊化的方法尋找規(guī)律,平面上n條直線，任兩條不平行，任三條不共點，問

4、這n條直線把這平面劃分為多少個部分？,設(shè)這n條直線把這平面劃分成Fn個部分。 先用具體化特殊化的方法尋找規(guī)律，如圖所示，易知的前幾項分別為,這些數(shù)字之間的規(guī)律性不很明顯， 較難用不完全歸納法猜出Fn的一般表達式。但我們可以分析前后項之間的遞推關(guān)系，因為這些圖形中，后一個都是由前一個添加一條直線而得到的，添加一條直線便增加若干個區(qū)域。,一般地，設(shè)原來的符合題意的n-1條直線把這平面分成 個區(qū)域，再增加一條直線l，就變成n條直線，按題設(shè)條件，這l必須與原有的n-1條直線各有一個交點, 且這n-1個交點及原有的交點互不重合。這n-1個交點把l劃分成n個區(qū)間，每個區(qū)間把所在的原來區(qū)域一分為二，所以就相

5、應比原來另增了n個區(qū)域，即： 這樣，我們就找到了一個從Fn-1到Fn的的遞推式，再加上已知的初始值F1=2，就可以通過n-1步可重復的簡單運算推導出Fn的值。,var a,i,n:longint; begin read(n); a:=2; for i:=2 to n do a:=a+i; writeln(a); end.,平面上有8個圓，最多能把平面分成幾部分？,1,2,3,4,5,6,Fn=Fn-1+2 (n-1),圓周上兩個點將圓周分為兩半，在這兩點上寫上數(shù)1；然后將兩段半圓弧對分，在兩個分點上寫上相鄰兩點上的數(shù)之和；再把4段圓弧等分，在分點上寫上相鄰兩點上的數(shù)之和，如此繼續(xù)下去，問第6步

6、后，圓周上所有點上的數(shù)之和是多少？,分析:先可以采用作圖嘗試尋找規(guī)律。,第一步：圓周上有兩個點，兩個數(shù)的和是1+1=2； 第二步：圓周上有四個點，四個數(shù)的和是1+1+2+2=6；增加數(shù)之和恰好是第一步圓周上所有數(shù)之和的2倍。 第三步：圓周上有八個點，八個數(shù)的和是1+1+2+2+3+3+3+3=18，增加數(shù)之和恰好是第二步數(shù)圓周上所有數(shù)之和的2倍。 第四步：圓周上有十六個點，十六個數(shù)的和1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54， 增加數(shù)之和恰好是第三步數(shù)圓周上所有數(shù)之和的2倍。 這樣我們可以知道，圓周上所有數(shù)之和是前一步圓周上所有數(shù)之和的3倍。 設(shè)An為第n步后得出的

7、圓周上所有數(shù)之和，則An=3An1,在nn的正方形釘子板上（n是釘子板每邊上的釘子數(shù)），求連接任意兩個釘子所得到的不同長度的線段種數(shù).,Fn=Fn-1+n,某公共汽車線路上共有15個車站（包括起點站和終點站）。在每個站上車的人中，恰好在以后各站下去一個。要使行駛過程中每位乘客都有座位，車上至少要備有多少個座位？,從表中可以看出車上人數(shù)最多是56人，所以車上至少要準備56個座位。,例、有一只經(jīng)過訓練的蜜蜂只能爬向右側(cè)相鄰的 蜂房，不能反向爬行。試求出蜜蜂從蜂房a爬到蜂 房b的可能路線數(shù)。,問題分析：這是一道很典型的Fibonacci 數(shù)列類題目，其中的遞推關(guān)系很明顯。由于 “蜜蜂只能爬向右側(cè)相鄰

8、的蜂房，不能反向爬 行”的限制，決定了蜜蜂到b點的路徑只能是 從b-1點或b-2點到達的，故fn=fn-1+fn-2 (a+2=n=b)，邊界條件fa=1，fa+1=1。,例、打印楊暉三角形的前10行。楊暉三角形的前5行如左下圖所示。,問題分析：我們觀察左上圖不太容易找到規(guī)律，但如果將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)楊輝三角形其實就是一個二維表（數(shù)組）的下三角部分。,假設(shè)用二維數(shù)組yh存儲，每行首尾元素都為1，且其 中任意一個非首尾元素yhi,j的值其實就是yhi-1,j-1 與yhi-1,j的和，另外每一行的元素個數(shù)剛好等于行 數(shù)。有了這些規(guī)律，給數(shù)組元素賦值就不難了，而要 打印楊暉三角形，只需

9、控制一下每行輸出的起始位置 即可。,Var Yh:Array1.10,1.10 Of Integer; I,J:Integer; Begin Yh1,1:=1; For I:=2 To 10 Do Begin YhI,1:=1;YhI,I:=1; For J:=2 To I-1 Do YhI,J:=YhI-1,J-1+YhI-1,J; End; For I:=1 To 10 Do Begin Write( :40-3*I); For J:=1 To I Do Write(YhI,J:6); Writeln; End; End.,例3、猴子第1天摘下若干個桃子,當即吃了一半又一個。第2天又把剩下

10、的桃吃了一半又一個,以后每天都吃前一天剩下的桃子的一半又一個,到第10天猴子想吃時,只剩下一個桃子。 問猴子第1天一共摘了多少桃子?,問題分析： 已知條件第 10 天剩下 1 個桃子，隱含條件每一次前一天的桃子個數(shù)等于后一天桃子的個數(shù)加 1 的 2 倍。 我們采取逆向思維的方法,從后往前推，可用倒推法求解。,Var S,I:LongInt; Begin S:=1;第10天只有一個桃子 For I:=9 DownTo 1 Do S:=(S+1)*2;第10天依次求前一天的桃 Writeln(S); 子數(shù) End.,例題3 : Hanoi塔問題 . Hanoi塔由n個大小不同的圓盤和三根木柱a,b

11、,c組成。開始時，這n個圓盤由大到小依次套在a柱上，如圖1所示。要求把a柱上n個圓盤按下述規(guī)則移到c柱上： (1)一次只能移一個圓盤； (2)圓盤只能在三個柱上存放； (3)在移動過程中，不允許大盤壓小盤。 問將這n個盤子從a柱移動到c柱上，總計需要移動多少個盤次？,a b c,分析,2,1,3,當n=1時：AC 當n=2時：AB,AC,BC 當n=3時：,分析,設(shè)f(n)為n 個盤子從1柱移到3柱所需移動的最少盤次。 當n=1時，f(1)=1。 當n=2時，f(2)=3。 以此類推，當1柱上有n(n2)個盤子時，我們可以利用下列步驟： 第一步：先借助3柱把1柱上面的n-1個盤子移動到2柱上，

12、所需的 移動次數(shù)為f(n-1)。 第二步：然后再把1柱最下面的一個盤子移動到3柱上，只需要1 次盤子。 第三步：再借助1柱把2柱上的n-1個盤子移動到3上，所需的移動 次數(shù)為f(n-1)。 由以上3步得出總共移動盤子的次數(shù)為：f(n-1)+1+ f(n-1)。 所以：f(n)=2 f(n-1)+1 hn=2hn-1+1 =2n-1 邊界條件：h1=1,例5、我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入 的自然數(shù)n):先輸入一個自然數(shù)n(n1000), 然后對此 自然數(shù)按照如下方法進行處理： 1不作任何處理；2在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半； 3加上數(shù)后，繼續(xù)按此規(guī)則進行處

13、理，直到不能再加自然數(shù)為止。 輸入： 6 滿足條件的數(shù)為 6 16 26 126 36 136 (此部分不必輸出) 輸出： 6,分析: 由題意可知，對于自然數(shù)N滿足條件的數(shù)應取 決于自然數(shù)1，2，N div 2滿足條件的數(shù) 之和加1，顯然可用遞推解決。 設(shè)AN表示自然數(shù)N滿足條件的數(shù)，則 ANA1+A2+AN Div 2+1 給A0賦為1, 則ANA0+A1+AN Div 2,Var A:Array0.1000 Of LongInt; N,I,J:LongInt; Begin Read(N); A0:=1; For I:=1 To N Do For J:=0 To I Div 2 Do AI:=AI+AJ; Writeln(AN); End.,【例題6】傳球游戲（NOIP2008普及） 【問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。 游戲規(guī)則是這樣的：n（32-3-1和1-3-2-1，共兩種。,分析,設(shè)fi,k表示經(jīng)過k次傳到編號為i的人手中的方案數(shù)，傳到i號同學的球只能來自于i的左邊一個同學和右邊一個同學，這兩個同學的編號分別是i-1和i+1，所以可以得到以下的遞推公式： fi,k=fi-1,k-1+fi+1,k-1 f1,k=fn,k-1+f2,k-1