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

2019-11-17 05:32:41

字體：大中小

來源：轉載

供稿：網友

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

上一篇：實現關機時的效果的一段代碼

下一篇：上海黑暗之龍--麻將原代碼