基本算法2-递推法.ppt

《基本算法2-递推法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本算法二递推策略一、引例：Fibonacci数列Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。解答由问题,可写出递推方程算法：f[0]:=1;f[1]:=2;fori:=2tondof[i]:=f[i–1]+f[i–2];总结从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这

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

3、要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。可用递推算法求解的题目一般有以下二个特点：1、问题可以划分成多个状态；2、除初始状态外，其它各个状态都可以用固定的递推关系式来表示。在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。二、递推概念给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0

4、关系递推关系有何性质如何求解递推关系三、解决递推问题的一般步骤建立递推关系式确定边界条件递推求解四、递推的两种形式顺推法和倒推法采用具体化、特殊化的方法寻找规律平面上n条直线，任两条不平行，任三条不共点，问这n条直线把这平面划分为多少个部分？设这n条直线把这平面划分成Fn个部分。先用具体化特殊化的方法寻找规律，如图所示，易知的前几项分别为这些数字之间的规律性不很明显，较难用不完全归纳法猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系，因为这些图形中，后一个都是由前一个添加一条直线而得到的，添加一条直线便增

5、加若干个区域。一般地，设原来的符合题意的n-1条直线把这平面分成个区域，再增加一条直线l，就变成n条直线，按题设条件，这l必须与原有的n-1条直线各有一个交点,且这n-1个交点及原有的交点互不重合。这n-1个交点把l划分成n个区间，每个区间把所在的原来区域一分为二，所以就相应比原来另增了n个区域，即：这样，我们就找到了一个从Fn-1到Fn的的递推式，再加上已知的初始值F1=2，就可以通过n-1步可重复的简单运算推导出Fn的值。vara,i,n:longint;beginread(n);a:=2;fori:=2to

6、ndoa:=a+i;writeln(a);end.平面上有8个圆，最多能把平面分成几部分？123456Fn=Fn-1+2×(n-1)圆周上两个点将圆周分为两半，在这两点上写上数1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和，如此继续下去，问第6步后，圆周上所有点上的数之和是多少？分析:先可以采用作图尝试寻找规律。第一步：圆周上有两个点，两个数的和是1+1=2；第二步：圆周上有四个点，四个数的和是1+1+2+2=6；增加数之和恰好是第一步圆周上所有数之

7、和的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步后得出的圆周上所有数之和，则An=3×An－1在n×n的正方形钉子板上（n是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的线段种数.

8、Fn=Fn-1+n某公共汽车线路上共有15个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？从表中可以看出车上人数最多是56人，所以车上至少要准备56个座位。例、有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。问题分析：这是一道很典型的Fi