基本算法2-遞推法

基本算法二遞推策略一、引例：Fibonacci數(shù)列Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”(又稱“Fibonacci問題”)。問題：一個數(shù)列的第0項為0，第1項為1，以后每一項都是前兩項的和，這個數(shù)列就是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第N項。解答由問題,可寫出遞推方程算法：

f[0]:=1;f[1]:=2;fori:=2tondof[i]:=f[i–1]+f[i–2];總結(jié)從這個問題可以看出，在計算裴波那契數(shù)列的每一項目時，都可以由前兩項推出。這樣，相鄰兩項之間的變化有一定的規(guī)律性，我們可以將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式：Fn=g(Fn-1)，這就在數(shù)的序列中，建立起后項和前項之間的關(guān)系。然后從初始條件（或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值）。很多問題就是這樣逐步求解的。對一個試題，我們要是能找到后一項與前一項的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就可以遞推了，接下來便是讓計算機(jī)一步步了。讓高速的計算機(jī)從事這種重復(fù)運(yùn)算，真正起到“物盡其用”的效果。遞推法所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系，逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡后確定。可用遞推算法求解的題目一般有以下二個特點(diǎn)：

1、問題可以劃分成多個狀態(tài)；

2、除初始狀態(tài)外，其它各個狀態(tài)都可以用固定的遞推關(guān)系式來表示。在我們實(shí)際解題中，題目不會直接給出遞推關(guān)系式，而是需要通過分析各種狀態(tài)，找出遞推關(guān)系式。二、遞推概念給定一個數(shù)的序列H0,H1,…,Hn,…若存在整數(shù)n0，使當(dāng)n>n0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0<i<n)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。如何建立遞推關(guān)系遞推關(guān)系有何性質(zhì)如何求解遞推關(guān)系

三、解決遞推問題的一般步驟

建立遞推關(guān)系式確定邊界條件遞推求解

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

這樣，我們就找到了一個從Fn-1到Fn的的遞推式，再加上已知的初始值F1=2，就可以通過n-1步可重復(fù)的簡單運(yùn)算推導(dǎo)出Fn的值。var

a,i,n:longint;begin

read(n);

a:=2;fori:=2tondo

a:=a+i;

writeln(a);end.平面上有8個圓，最多能把平面分成幾部分？

123456Fn=Fn-1+2×

(n-1)

圓周上兩個點(diǎn)將圓周分為兩半，在這兩點(diǎn)上寫上數(shù)1；然后將兩段半圓弧對分，在兩個分點(diǎn)上寫上相鄰兩點(diǎn)上的數(shù)之和；再把4段圓弧等分，在分點(diǎn)上寫上相鄰兩點(diǎn)上的數(shù)之和，如此繼續(xù)下去，問第6步后，圓周上所有點(diǎn)上的數(shù)之和是多少？

分析:先可以采用作圖嘗試尋找規(guī)律。第一步：圓周上有兩個點(diǎn)，兩個數(shù)的和是1+1=2；第二步：圓周上有四個點(diǎn)，四個數(shù)的和是1+1+2+2=6；增加數(shù)之和恰好是第一步圓周上所有數(shù)之和的2倍。第三步：圓周上有八個點(diǎn)，八個數(shù)的和是1+1+2+2+3+3+3+3=18，增加數(shù)之和恰好是第二步數(shù)圓周上所有數(shù)之和的2倍。第四步：圓周上有十六個點(diǎn)，十六個數(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步后得出的圓周上所有數(shù)之和，則An=3×An－1在

n×n的正方形釘子板上（n是釘子板每邊上的釘子數(shù)），求連接任意兩個釘子所得到的不同長度的線段種數(shù).Fn=Fn-1+n某公共汽車線路上共有15個車站（包括起點(diǎn)站和終點(diǎn)站）。在每個站上車的人中，恰好在以后各站下去一個。要使行駛過程中每位乘客都有座位，車上至少要備有多少個座位？從表中可以看出車上人數(shù)最多是56人，所以車上至少要準(zhǔn)備56個座位。例、有一只經(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+2<=n<=b)，邊界條件fa=1，fa+1=1。例、打印楊暉三角形的前10行。楊暉三角形的前5行如左下圖所示。問題分析：我們觀察左上圖不太容易找到規(guī)律，但如果將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)楊輝三角形其實(shí)就是一個二維表（數(shù)組）的下三角部分。假設(shè)用二維數(shù)組yh存儲，每行首尾元素都為1，且其中任意一個非首尾元素yh[i,j]的值其實(shí)就是yh[i-1,j-1]與yh[i-1,j]的和，另外每一行的元素個數(shù)剛好等于行數(shù)。有了這些規(guī)律，給數(shù)組元素賦值就不難了，而要打印楊暉三角形，只需控制一下每行輸出的起始位置即可。VarYh:Array[1..10,1..10]OfInteger;

I,J:Integer;BeginYh[1,1]:=1;ForI:=2To10DoBeginYh[I,1]:=1;Yh[I,I]:=1;ForJ:=2ToI-1Do

Yh[I,J]:=Yh[I-1,J-1]+Yh[I-1,J];End;

ForI:=1To10DoBeginWrite('':40-3*I);ForJ:=1ToIDoWrite(Yh[I,J]:6);

Writeln;End;End.例3、猴子第1天摘下若干個桃子,當(dāng)即吃了一半又一個。第2天又把剩下的桃吃了一半又一個,以后每天都吃前一天剩下的桃子的一半又一個,到第10天猴子想吃時,只剩下一個桃子。問猴子第1天一共摘了多少桃子?問題分析：已知條件第10天剩下1個桃子，隱含條件每一次前一天的桃子個數(shù)等于后一天桃子的個數(shù)加1的2倍。我們采取逆向思維的方法,從后往前推，可用倒推法求解。Var

S,I:LongInt;BeginS:=1;{第10天只有一個桃子}ForI:=9DownTo1DoS:=(S+1)*2;{第10天依次求前一天的桃

Writeln(S);子數(shù)}End.例題3:Hanoi塔問題

.Hanoi塔由n個大小不同的圓盤和三根木柱a,b,c組成。開始時，這n個圓盤由大到小依次套在a柱上，如圖1所示。要求把a(bǔ)柱上n個圓盤按下述規(guī)則移到c柱上：

(1)一次只能移一個圓盤；

(2)圓盤只能在三個柱上存放；

(3)在移動過程中，不允許大盤壓小盤。問將這n個盤子從a柱移動到c柱上，總計需要移動多少個盤次？abc分析ABC213當(dāng)n=1時：AC當(dāng)n=2時：AB,AC,BC當(dāng)n=3時：分析設(shè)f(n)為n個盤子從1柱移到3柱所需移動的最少盤次。當(dāng)n=1時，f(1)=1。當(dāng)n=2時，f(2)=3。以此類推，當(dāng)1柱上有n(n>2)個盤子時，我們可以利用下列步驟：第一步：先借助3柱把1柱上面的n-1個盤子移動到2柱上，所需的移動次數(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)=2f(n-1)+1

hn=2hn-1+1=2n-1

邊界條件：h1=1例5、我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n):先輸入一個自然數(shù)n(n≤1000),然后對此自然數(shù)按照如下方法進(jìn)行處理：1．不作任何處理；2．在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；3．加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止。輸入：

6

滿足條件的數(shù)為6162612636136(此部分不必輸出)輸出：

6分析:由題意可知，對于自然數(shù)N滿足條件的數(shù)應(yīng)取決于自然數(shù)1，2，…，Ndiv2滿足條件的數(shù)之和加1，顯然可用遞推解決。設(shè)A[N]表示自然數(shù)N滿足條件的數(shù)，則A[N]＝A[1]+A[2]+…+A[NDiv2]+1給A[0]賦為1,則A[N]＝A[0]+A[1]+…+A[NDiv2]VarA:Array[0..1000]OfLongInt;

N,I,J:LongInt;Begin

Read(N);A[0]:=1;ForI:=1ToNDoForJ:=0ToIDiv2DoA[I]:=A[I]+A[J];

Writeln(A[N]);End.【例題6】傳球游戲（NOIP2008普及）【問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。

游戲規(guī)則是這樣的：n（3<=n<=30）個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個球，當(dāng)老師吹哨子時開始傳球，每個同學(xué)可以把球傳給自己左右的兩個同學(xué)中的一個（左右任意），當(dāng)老師再吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學(xué)就是敗者，要給大家表演一個節(jié)目。

聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m（3<=m<=30）次后，又回到小蠻手里。兩種傳球被視作不同的方法，當(dāng)且僅當(dāng)這兩種方法中，接到球的同學(xué)按照順序組成的序列是不同的。比如3個同