實用算法(基礎算法-遞推法-02)

　　
　　
　　順推法
　　    倒推法的逆過程就是順推法，即由邊界條件出發，通過遞推關系式推出後項值，再由後項值按遞推關系式推出再後項值......，依次遞推，直至從問題初始陳述向前推進到這個問題的解為止。
　　    實數數列：一個實數數列共有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 =');