实用算法(基础算法-递推法-01)

有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：
    F_n=g(F_n-1)
这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件(或最终结果)入手，一步步地按递推关系递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果)，问题就好解决，让计算机一步步算就是了，让高速的计算机做这种重复运算，可真正起到“物尽其用”的效果。
递推分倒推法和顺推法两种形式。一般分析思路：
    if求解条件F1
        then begin{倒推}
由题意(或递推关系)确定最终结果Fa；
求出倒推关系式F_i-1=g'(F_i);
            i=n;{从最终结果Fn出发进行倒推}
            while 当前结果F_i非初始值F₁ do由F_i-1=g(F₁)倒推前项；
输出倒推结果F₁和倒推过程；
            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公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？
算法分析：
编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。
        No.        Distance(k.m.)        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和点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处，这就是说
    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处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即d₁₂=500/3km
        dis[2]=dis[1]+d₁₂=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公升，即d₂₃=500/5,
        dis[3]=dis[2]+d₂₃=dis[2]+500/5;

依此类推，为了在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公升，即
    d_k,k+1=500/(2k-1)
        dis[k+1]=dis[k]+d_k,k+1
                =dis[k]+500/(2k-1);

最后，i=n至始点的距离为1000-dis[n],oil[n]=500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至i=n，加上从i=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为(1000-dis[n])*(2n+1)，即始点藏油为oil[n]+(1000-dis[n])*(2n+1)。
下面为程序代码：
program oil_lib;
var
k:integer;  {贮油点位置序号}
d,            {累计终点至当前贮油点的距离}
d1:real;      {i=n至始点的距离}
oil,dis:array[1..10] of real;
i:integer;    {辅助变量}
begin
    writeln('NO.','distance(k.m)':30,'oil(1.)':80);
    k:=1;
    d:=500;    { 从i=1处开始向始点倒推}
    dis[1]:=500;
    oil[1]:=500;
    repeat
        k:=k+1;
        d:=d+500/(2*k-1);
        dis[k]:=d;
        oil[k]:=oil[k-1]+500;
    until d>=1000;

    dis[k]:=1000;        {置始点至终点的距离值}
    d1:=1000-dis[k-1];    {求i=n处至始点的距离}
    oil[k]:=d1*(2*k+1)+oil[k-1];    {求始点藏油量}
    for i:=0 to k do        {由始点开始，逐一打印始点至当前贮油点的距离和藏油量}
        writeln(i,1000-dis[k-i]:30,oil[k-i]:80);
end. {main}

转换为C语言程序如下：
#include<stdio.h>
void main()
{
    int k;            /*贮油点位置序号*/
    float d,d1;       /*d:累计终点至当前贮油点的距离,d1:i=n至始点的距离*/
    float oil[10],dis[10];
    int i;
    printf("NO. distance(k.m.)\toil(l.)\n");
    k=1;
    d=500;        /*从i=1处开始向始点倒推*/
    dis[1]=500;
    oil[1]=500;
    do{
        k=k+1;
        d=d+500/(2*k-1);
        dis[k]=d;
        oil[k]=oil[k-1]+500;
    }while(!(d>=1000));
    dis[k]=1000;        /*置始点至终点的距离值*/
    d1=1000-dis[k-1];    /*求i=n处至始点的距离*/
    oil[k]=d1*(2*k+1)+oil[k-1];    /*求始点藏油量*/
    for(i=0;i<k;i++)       /*由始点开始逐一打印始点至当前贮油点的距离和藏油量*/
        printf("%d\t%f\t%f\t\n",i,1000-dis[k-i],oil[k-i]);
}

实用算法(基础算法-递推法-02)

发表日期：2003年4月10日 出处：实用算法的分析和程序设计 作者：C语言之家整理 已经有1317位读者读过此文

顺推法
倒推法的逆过程就是顺推法，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值......，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。
实数数列：一个实数数列共有N项，已知
            ai=(a_i-1-a_i+1)/2+d,   (1<i<N)(N<60)
键盘输入N,d,a₁,a_n,m,输出a_m
输入数据均不需判错。
算法分析：
分析该题，对公式：
        A_i=(A_i-1-A_i+1)/2+d         (1<i<N)     (n<60)
作一翻推敲，探讨其数字变换规律。不然的话会无从下手。
令 X=A₂   s₂[i]=(p_i,Q_i,R_i)表示A_i=P_iX+Q_iD+R_iA₁
我们可以根据
        A_i=A_i-2-2A_i-1+2D
          =P_iX+Q_iD+R_iA₁
推出公式
        P_iX+Q_iD+R_iA₁=(P_i-2-2P_i-1)X+(Q_i-2-2Q_i-1+2)D+(R_i-2-2R_i-1)A₁
比较等号两端X,D和A1的系数项，可得
        P_i=P_i-2-2P_i-1
        Q_i=Q_i-2-2Q_i-1+2
        R_i=R_i-2-2R_i-1
加上两个边界条件
        P₁=0    Q₁=0    R₁=1    (A₁=A₁)
        P₂=1    Q₂=0    R₂=0    (A₂=A₂)
根据Pi、Qi、Ri的递推式，可以计算出
        S₂[1]=(0,0,1);
        S₂[3]=(-2,2,1);
        S₂[4]=(5,-2,-2);
        S₂[5]=(-12,8,5);
        ...................
        S₂[i]=(P_i,Q_i,R_i);
        ...................
        S₂[N]=(P_N,Q_N,R_N);
有了上述基础，AM便不难求得。有两种方法：
    1、由于A_N、A₁和P_N、Q_N、R_N已知，因此可以先根据公式：
        A₂=A_N-Q_ND-R_NA₁/P_N
求出A₂。然后将A₂代入公式
        A₃=A₁-2A₂+2D
求出A₃。然后将A₃代入公式
        A₄=A₂-2A₃+2D
求出A₄。然后将A₄代入公式
    ............................
求出A_i-1。然后将A_i-1代入公式
        A_i=A_i-2-2A_i-1+2D
求出A_i。依此类推，直至递推至A_M为止。
上述算法的缺陷是由于A2是两数相除的结果，而除数PN递增，因此精度误差在所难免，以后的递推过程又不断地将误差扩大，以至当M超过40时，求出的AM明显徧离正确值。显然这种方法简单但不可靠。
    2、我们令A₂=A₂,A₃=X，由S₃[i]=(P_i,Q_i,R_i)表示A_i=P_iX+Q_iD+R_iA₂  (i>=2) 可计算出：
        S₃[2]=(0,0,1)=S₂[1];
        S₃[3]=(1,0,0)=S₂[2];
        S₃[4]=(-2,2,1)=S₂[3];
        S₃[5]=(5,-2-2)=S₂[4];
        ......................
        S₃[i]=(..........)=S₂[i-1];
        .....................
        S₃[N]=(..........)=S₂[N-1];
再令A₃=A₃,A₄=X,由S₄[i]=(p_i,Q_i,R_i)表示A_i=P_iX+Q_iD+R_iA₃   (i>=3) 可计算得出：
        S₄[3]=(0,0,1)=S₃[2]=S₂[1];
        S₄[4]=(1,0,0)=S₃[3]=S₂[2];
        S₄[5]=(-22,1)=S₃[4]=S₂[3];
        ..........................
        S₄[i]=(...........)=S₃[i-1]=S₂[i-2];
        .......................
        S₄[N]=(...........)=S₃[N-1]=S₂[N-2];
依此类推，我们可以发现一个有趣的式子：
        A_N=P_N-i+2*A_i+Q_N-i+2*D+R_N-i+2*A_i-1,  即
        A_i=(A_N-Q_N-i+2*D-R_N-i+2*A_i-1)/P_N-i+2
我们从已知量A₁和A_N出发，依据上述公式顺序递推A₂、A₃、...、A_M.由于P_N-i+2递减，因此最后得出的A_M要比第一种算法趋于精确。
程序代码如下：
program ND1P4;
const
    maxn    =60;
var
    n,m,i    :integer;
    d        :real;
    list     :array[1..maxn] of real;        {list[i]-------对应ai}
    s        :array[1..maxn,1..3] of real;   {s[i,1]--------对应Pi}
                                             {s[i,2]--------对应Qi}
                                             {s[i,3]--------对应Ri}
procedure init;
    begin
        write('n m d =');
        readln(n,m,d);            {输入项数，输出项序号和常数}
        write('a1 a',n,'=');
        readln(list[1],list[n]);    {输入a1和an}
    end;    {init}
procedure solve;
    begin
        s[1,1]:=0;s[1,2]:=0;s[1,3]:=1;   {求递推边界(P1,Q1,R1)和(P2,Q2,R2)}
        s[2,1]:=1;s[2,2]:=0;s[2,3]:=0;   {根据公式Pi<---Pi-2 - 2*Pi-1}
                                         {Qi<---Qi-2 - 2*Qi-1}
                                         {Ri<---Ri-2 - 2*Ri-1}
                                         {递推(P3,Q3,R3)......Pn,Qn,Rn)}
        for i:=3 to n do
            begin
                s[i,1]:=s[i-2,1]-2*s[i-1,1];
                s[i,2]:=s[i-2,2]-2*s[i-1,2]+2;
                s[i,3]:=s[i-2,3]-2*s[i-1,3];
            end; {for}
    end;{solve}
procedure main;
    begin
        solve;        {求(P1,Q1,R1)..(Pn,Qn,Rn)}
                      {根据公式Ai=(An-Qn-i+2 * d-Rn-i+2 * Ai-1)/Pn-i+2}
                      {递推A2..Am}
        for i:=2 to m do
            list[i]:=(list[n]-s[n-i+2,2]*d-s[n-i+2,3]*list[i-1])/s[n-i+2,1];
        writeln('a',m,'=',list[m]:20:10);    {输出Am}
    end;    {main}
begin
    init;        {输入数据}
    main;        {递推和输出Am}
    readln;
end.    {main}