基础算法-递推法

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

1、基础算法-递推法.txt只要你要，只要我有，你还外边转什么阿老实在我身边待着就行了。听我的就是，问那么多干嘛，我在你身边,你还走错路!跟着我!不能给你幸福是我的错，但谁让你不幸福，我TMD去砍了他实用算法（基础算法-递推法-01）有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：Fn=g（Fn~l）这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件（或最终结果）入手,—•步步地按递推关系递推，直至求出最终结果（或初始值）。很多程序就是按这样的方法逐步求解的

2、。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（最终结果），问题就好解决，让计算机一步步算就是了，让高速的计算机做这种重复运算，可真正起到“物尽其用”的效果。递推分倒推法和顺推法两种形式。一般分析思路：if求解条件F1thenbegin｛倒推｝rh题意（或递推关系）确定坟终结果Fa；求出倒推关系式Ei-l=g，（Ei）;i二n;｛从最终结果Fn出发进行倒推｝wh订e当前结果Fi非初始值Fldo由Fi-l=g（F1）倒推前项；输岀倒推结果F1和倒推过程；end｛then｝elsebegin

3、｛顺推｝山题意（或顺推关系）确定初始值Fl（边界条件）；求出顺推关系式F1二g（Fi-l）;i二1；｛由边界条件F1出发进行顺推｝while当前结果Fi非最终结果Fndo由Fi=g（Fi-l）顺推后项；输出顺推结果Fn和顺推过程；end;｛else｝一、倒推法所谓倒推法，就是在不知初始值的情况下，经某种递推关系而获知问题的解或目标，再倒推过来，推知它的初始条件。因为这类问题的运算过程是一一映射的，故可分析得其递推公式。然后再从这个解或目标出发，采川倒推手段，一步步地倒推到这个问题的初始陈述。下曲举例说明。［例

4、1］贮油点-辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立儿个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？算法分析：编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。No.Distanee(k.m.)oi1(litre)1XXXX2XXXX3XXXX设dis[i]为笫i个贮油点至终点(i二0)的距离；oil[i]为第i个贮

5、油点的存贮油量;我们可以用倒推法來解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。下图表示倒推时的返冋点：从贮油点i向贮油点i+1倒推的策略是，卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油，而每次从i+1出发时又必须装足500公升汽油。两点之间的距离必须满足在耗汕最少的条件下使i点贮足i*500分升汽汕的要求(0<=i<=n-l)o具体地讲，第一个贮汕点i=l应距终点i=0处500km且在该处贮藏500公升汽汕，这样才能保证卡千能市1=1处到达终点i二0处，

6、这就是说dis[l>500oil[l]=500;为了在i=l处贮藏500公升汽油，卡车至少从i=2处开两趟满载油的车至i二1处。所以i=2处至少贮有2*500公升汽油，即o订[2]=500*2=1000o另外，再加上从i=l返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即dl2=500/3kmdis[2]=dis[l]+dl2=dis[l]+500/3为了在i=2处贮存1000公升汽汕，卡车至少从i=3处开三趟满载汕的车至i=2处。扌馭i二3处至少贮有3*500公升汽

7、油，即oil[3]二500*3二1500。加ki二2至1=3处的二趟返程空车,合计5次。路途耗油量也应为500公升,即d23=500/5,dis⑶二dis[2]+d23二dis[21+500/5;依此类推，为了在i=k处贮藏k*500公升汽油，卡车至少从i二k+1处开k趟满载车至i二k处，即oil[k+1]二[k+l]*500二oil[k]+500,加上从i=k处返冋i二k+1的k-1趟返程空间,合计2k-l次。这2k-1次总耗汕量按最省要求为500公升,即dk,k+l=500/(2k-l)dis[k+1]=

8、dis[k]+dk,k+1二dis[k]+500/(2k-l);最后，i=n至始点的距离为1000-dis[n],oil[n]二500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至i=n,加上从i=n返回始点的n趟返程空车，合计2n+l次,2n+l趟的总耗油量应正好为(1000-dis[n])*(2n+l),即始点藏油为oi1[n]+(1000-dis[n])*(2n+