基本算法2-递推法.ppt

1、基本算法二,递推策略,一、引例：Fibonacci数列,Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。 问题： 一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。,解答,由问题,可写出递推方程,算法： f0:=1; f1:=2; for i:=2 to n do fi:=fi1+fi2;,总结,从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷

2、的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。 对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。,递推法,所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。 可用递推算法求解的题目一般有以下二个特点： 1、

3、问题可以划分成多个状态； 2、除初始状态外，其它各个状态都可以用固定的递推关系式来表示。 在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。,二、递推概念,给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。 如何建立递推关系 递推关系有何性质 如何求解递推关系,三、解决递推问题的一般步骤,建立递推关系式 确定边界条件 递推求解,四、递推的两种形式,顺推法和倒推法,采用具体化、特殊化的方法寻找规律,平面上n条直线，任两条不平行，任三条不共点，问

4、这n条直线把这平面划分为多少个部分？,设这n条直线把这平面划分成Fn个部分。 先用具体化特殊化的方法寻找规律，如图所示，易知的前几项分别为,这些数字之间的规律性不很明显， 较难用不完全归纳法猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系，因为这些图形中，后一个都是由前一个添加一条直线而得到的，添加一条直线便增加若干个区域。,一般地，设原来的符合题意的n-1条直线把这平面分成 个区域，再增加一条直线l，就变成n条直线，按题设条件，这l必须与原有的n-1条直线各有一个交点, 且这n-1个交点及原有的交点互不重合。这n-1个交点把l划分成n个区间，每个区间把所在的原来区域一分为二，所以就相

5、应比原来另增了n个区域，即： 这样，我们就找到了一个从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),圆周上两个点将圆周分为两半，在这两点上写上数1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和，如此继续下去，问第6步

6、后，圆周上所有点上的数之和是多少？,分析:先可以采用作图尝试寻找规律。,第一步：圆周上有两个点，两个数的和是1+1=2； 第二步：圆周上有四个点，四个数的和是1+1+2+2=6；增加数之和恰好是第一步圆周上所有数之和的2倍。 第三步：圆周上有八个点，八个数的和是1+1+2+2+3+3+3+3=18，增加数之和恰好是第二步数圆周上所有数之和的2倍。 第四步：圆周上有十六个点，十六个数的和1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54， 增加数之和恰好是第三步数圆周上所有数之和的2倍。 这样我们可以知道，圆周上所有数之和是前一步圆周上所有数之和的3倍。 设An为第n步后得出的

7、圆周上所有数之和，则An=3An1,在nn的正方形钉子板上（n是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的线段种数.,Fn=Fn-1+n,某公共汽车线路上共有15个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？,从表中可以看出车上人数最多是56人，所以车上至少要准备56个座位。,例、有一只经过训练的蜜蜂只能爬向右侧相邻的 蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂 房b的可能路线数。,问题分析：这是一道很典型的Fibonacci 数列类题目，其中的递推关系很明显。由于 “蜜蜂只能爬向右侧相邻

8、的蜂房，不能反向爬 行”的限制，决定了蜜蜂到b点的路径只能是 从b-1点或b-2点到达的，故fn=fn-1+fn-2 (a+2=n=b)，边界条件fa=1，fa+1=1。,例、打印杨晖三角形的前10行。杨晖三角形的前5行如左下图所示。,问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。,假设用二维数组yh存储，每行首尾元素都为1，且其 中任意一个非首尾元素yhi,j的值其实就是yhi-1,j-1 与yhi-1,j的和，另外每一行的元素个数刚好等于行 数。有了这些规律，给数组元素赋值就不难了，而要 打印杨晖三角形，只需

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 个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的个数加 1 的 2 倍。 我们采取逆向思维的方法,从后往前推，可用倒推法求解。,Var S,I:LongInt; Begin S:=1;第10天只有一个桃子 For I:=9 DownTo 1 Do S:=(S+1)*2;第10天依次求前一天的桃 Writeln(S); 子数 End.,例题3 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b

11、,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,a b c,分析,2,1,3,当n=1时：AC 当n=2时：AB,AC,BC 当n=3时：,分析,设f(n)为n 个盘子从1柱移到3柱所需移动的最少盘次。 当n=1时，f(1)=1。 当n=2时，f(2)=3。 以此类推，当1柱上有n(n2)个盘子时，我们可以利用下列步骤： 第一步：先借助3柱把1柱上面的n-1个盘子移动到2柱上，

12、所需的 移动次数为f(n-1)。 第二步：然后再把1柱最下面的一个盘子移动到3柱上，只需要1 次盘子。 第三步：再借助1柱把2柱上的n-1个盘子移动到3上，所需的移动 次数为f(n-1)。 由以上3步得出总共移动盘子的次数为：f(n-1)+1+ f(n-1)。 所以：f(n)=2 f(n-1)+1 hn=2hn-1+1 =2n-1 边界条件：h1=1,例5、我们要求找出具有下列性质数的个数(包含输入 的自然数n):先输入一个自然数n(n1000), 然后对此 自然数按照如下方法进行处理： 1不作任何处理；2在它的左边加上一个自然数，但该自然数不能超过原数的一半； 3加上数后，继续按此规则进行处

13、理，直到不能再加自然数为止。 输入： 6 满足条件的数为 6 16 26 126 36 136 (此部分不必输出) 输出： 6,分析: 由题意可知，对于自然数N满足条件的数应取 决于自然数1，2，N div 2满足条件的数 之和加1，显然可用递推解决。 设AN表示自然数N满足条件的数，则 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普及） 【问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。 游戏规则是这样的：n（32-3-1和1-3-2-1，共两种。,分析,设fi,k表示经过k次传到编号为i的人手中的方案数，传到i号同学的球只能来自于i的左边一个同学和右边一个同学，这两个同学的编号分别是i-1和i+1，所以可以得到以下的递推公式： fi,k=fi-1,k-1+fi+1,k-1 f1,k=fn,k-1+f2,k-1