实用算法 基础算法-递推法

顺推法
    倒推法的逆过程就是顺推法，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值......，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。
    实数数列：一个实数数列共有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];