基础算法-递推.ppt

《基础算法-递推.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基础算法-递推递推算法递推法是一种重要的数学方法，在数学的各个领域都有广泛的应用，也是计算机用于数值计算的一个重要方法递推算法的首要问题是得到相邻数据项之间的关系，即递推关系，这样可以避开求通项公式的麻烦。递推关系式并不是一个通项公式，而是一组反映前后数据项间关系的表达式。通常可从问题的初始条件出发，先构造前若干个数据项，从中找出数据间的关系，从而确立递推关系式。递推的概念与基本思想给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0

2、的一般步骤建立递推关系式确定边界条件递推求解递推的形式顺推法和倒推法例题分析-正推例：有2*n的长方形方格，用n个1*2的骨牌铺满方格。编写一个程序，试对给出的任意一个n（n＞0），输出铺法总数。①当n=1时，只能是一种铺法，铺法总数表示为x1=1。②当n=2时，骨牌可以两个并列竖排，也可以并列横排，再无其他方法，上图所示，因此，铺法总数表示为x2=2。n=2n=3由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2时的排列方法数之和。推出一般规律：xn=xn-1+xn-2（n＞2）x1=1x2=2其中xn=xn-1+xn-2就是递推公式。如当n=4时：x3=x2

3、+x1=3x4=x3+x2=5例题分析—逆推例题：贮油点。一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：No.Distance(k.m.)Oil(litre)1××××2××××……………分析设Way[i]——第i个贮油点到终点（i=0）的距离；oil[i]—

4、—第i个贮油点的贮油量；我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。从贮油点i向贮油点i+1倒推的方法是：卡车在贮油点i和贮油点i+1间往返若干次。卡车每次返回i+1点时应该正好耗尽500公升汽油，而每次从i+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使i点贮足i*500公升汽油的要求（0≦i≦n-1）。倒推第一步第一个贮油点i=1应距终点i=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说Way[1]=500；oil[1]=500；倒推第二步为

5、了在i=1处贮藏500公升汽油，卡车至少从I=2处开两趟满载油的车至i=1处，所以i=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d1,2=500/3km，Way[2]=Way[1]+d1,2=Way[1]+500/3倒推第三步为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程空车，合计5次。路途耗

6、油亦应500公升，即d23=500/5，Way[3]=Way[2]+d2,3=Way[2]+500/5；倒推第k步……为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即oil[k+1]=(k+1)*500=oil[k]+500，加上从i=k返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1)Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；i=n的情形i=n至始点的距离为1000-Way[n],oil[n]=500*n。为了在

7、i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至I=n，加上从I=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为（1000-Way[n]）*(2n+1)，即始点藏油为oil[n]+(1000-Way[n])*(2n+1)。递推算法特点：1、一个问题的求解需要一系列的计算，在已知条件和所求问题之间总存在着某种互相联系的关系。2、在计算时，如果可以找到前后过程之间的数量关系,即递推式。3、而从已知条件推导出问题解的方法叫顺推，从问题出发逐步推到已知条件的方法叫逆推。