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

核心提示：顺推法 倒推法的逆过程就是顺推法，即由边界条件出发，实用算法(基础算法-递推法-02)，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值......，我们可以发现一个有趣的式子： AN=PN-i+2*Ai+QN-i+2*D+RN-i+2*Ai-1, 即 Ai=(AN-QN-i+2*D-RN-i+2*

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