实用算法(基础算法递推法).doc

实用算法(基础算法递推法).doc

ID:25150402

大小:64.00 KB

页数:8页

时间:2018-11-17

实用算法(基础算法递推法).doc_第1页
实用算法(基础算法递推法).doc_第2页
实用算法(基础算法递推法).doc_第3页
实用算法(基础算法递推法).doc_第4页
实用算法(基础算法递推法).doc_第5页
资源描述:

《实用算法(基础算法递推法).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、实用算法(基础算法-递推法-01)    有一类试题,每相邻两项数之间的变化有一定的规律性,我们可将这种规律归纳成如下简捷的递推关系式:   Fn=g(Fn-1)   这就在数的序列中,建立起后项和前项之间的关系,然后从初始条件(或最终结果)入手,一步步地按递推关系递推,直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题,我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果),问题就好解决,让计算机一步步算就是了,让高速的计算机做这种重复运算,可真正起到“物尽其用”的效果。   递推分倒推法和顺推法两种形式。一般分析思路

2、:   if求解条件F1       thenbegin{倒推}           由题意(或递推关系)确定最终结果Fa;           求出倒推关系式Fi-1=g'(Fi);           i=n;{从最终结果Fn出发进行倒推}           while当前结果Fi非初始值F1do由Fi-1=g(F1)倒推前项;           输出倒推结果F1和倒推过程;           end{then}       elsebegin{顺推}           由题意(或顺推关系)确定初始值F1(边界条件);           求出顺

3、推关系式F1=g(Fi-1);           i=1;{由边界条件F1出发进行顺推}           while当前结果Fi非最终结果Fndo由Fi=g(Fi-1)顺推后项;           输出顺推结果Fn和顺推过程;       end;{else}一、倒推法   所谓倒推法,就是在不知初始值的情况下,经某种递推关系而获知问题的解或目标,再倒推过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,故可分析得其递推公式。然后再从这个解或目标出发,采用倒推手段,一步步地倒推到这个问题的初始陈述。   下面举例说明。[例1]贮油点   一辆

4、重型卡车欲穿过1000公里的沙漠,卡车耗油为1升/公里,卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,使卡车能顺利穿越沙漠,试问司机如何建立这些储油点?每一储油点应存多少油,才能使卡车以消耗最少油的代价通过沙漠?算法分析:   编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。       No.       Distance(k.m.)       oil(litre)       1               XX               XX       2          

5、     XX               XX       3               XX               XX       ...              .....             ......   设dis[i]  为第i个贮油点至终点(i=0)的距离;     oil[i]  为第i个贮油点的存贮油量;   我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及存油量。下图表示倒推时的返回点:    从贮油点i向贮油点i+1倒推的策略是,卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗

6、尽500公升汽油,而每次从i+1出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500分升汽油的要求(0<=i<=n-1)。具体地讲,第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油,这样才能保证卡车能由i=1处到达终点i=0处,这就是说   dis[1]=500       oil[1]=500;   为了在i=1处贮藏500公升汽油,卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少贮有2*500公升汽油,即oil[2]=500*2=1000。另外,再加上从i=1返回至i=2处的一趟

7、空载,合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即d12=500/3km       dis[2]=dis[1]+d12=dis[1]+500/3     为了在i=2处贮存1000公升汽油,卡车至少从i=3处开三趟满载油的车至i=2处。报以i=3处至少贮有3*500公升汽油,即oil[3]=500*3=1500。加上i=2至i=3处的二趟返程空车,合计5次。路途耗油量也应为500公升,即d23=500/5,       dis[3]=dis[2]+d23=dis[2]+500/5;     依此类推,为了在i=k处贮藏k*500公升汽油

8、,卡车至少从i=k+1处开k趟满载车至i=k处,即 

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。