文档介绍：实用算法(基础算法-递推法)
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
实用算法（基础算法-递推法-01）
 
    有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：
    Fn=g（Fn—1）
    这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件(或最终结果)入手，一步步地按递推关系递推，直至求出最终结果（或初始值).很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果)，问题就好解决,让计算机一步步算就是了，让高速的计算机做这种重复运算,可真正起到“物尽其用”的效果。
    递推分倒推法和顺推法两种形式。一般分析思路:
    if求解条件F1
        then begin{倒推}
            由题意（或递推关系)确定最终结果Fa；
            求出倒推关系式Fi—1=g’(Fi）；
            i=n；｛从最终结果Fn出发进行倒推｝
            while 当前结果Fi非初始值F1 do由Fi—1=g(F1)倒推前项；
            输出倒推结果F1和倒推过程;
            end {then}
        else begin｛顺推}
            由题意（或顺推关系）确定初始值F1（边界条件）；
            求出顺推关系式F1=g（Fi-1)；
            i=1;{由边界条件F1出发进行顺推}
            while 当前结果Fi非最终结果Fn do由Fi=g(Fi-1）顺推后项；
            输出顺推结果Fn和顺推过程;
        end; ｛else｝
一、倒推法
    所谓倒推法，就是在不知初始值的情况下,经某种递推关系而获知问题的解或目标，再倒推过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,，采用倒推手段,一步步地倒推到这个问题的初始陈述。
    下面举例说明。
［例1] 贮油点
    一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里,卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,使卡车能顺利穿越沙漠,试问司机如何建立这些储油点？每一储油点应存多少油,才能使卡车以消耗最少油的代价通过沙漠?
4
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
算法分析：
    编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。
        No。        Distance(。)        oil（litre）
        1                X X                X X
        2                X X                X X
        3                X X                X X
       ...              。。。。。              ......
    设dis[i］   为第i个贮油点至终点（i=0)的距离；
      oil［i]   为第i个贮油点的存贮油量;
    ，逐一求出每个贮油点的位置及存油量.
下图表示倒推时的返回点：
 
    从贮油点i向贮油点i+1倒推的策略是，卡车在点i