实用算法(基础算法-递推法).doc

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

———————————————————————————————— 作者：
———————————————————————————————— 日期：

10

个人收集整理 勿做商业用途
实用算法（基础算法-递推法-01）

    有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：
    Fn=g（Fn—1）
    这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件(或最终结果)入手，一步步地按递推关系递推，直至求出最终结果（或初始值).很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果)，问题就好解决,让计算机一步步算就是了，让高速的计算机做这种重复运算,可真正起到“物尽其用”的效果。
    递推分倒推法和顺推法两种形式。一般分析思路:
    if求解条件F1
        then begin{倒推}
            由题意（或递推关系)确定最终结果Fa；
            求出倒推关系式Fi—1=g’(Fi）；
            i=n；｛从最终结果Fn出发进行倒推｝
            while 当前结果Fi非初始值F1 do由Fi—1=g(F1)倒推前项；
            输出倒推结果F1和倒推过程;
            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公升。即d12=500/3km
        dis[2］=dis[1]+d12=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公升，即d23=500/5,
        dis［3]=dis［2]+d23=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公升，即
    dk，k+1=500/(2k—1）
        dis[k+1]=dis［k]+dk,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=（ai-1—ai+1）/2+d，   （1〈i〈N)(N<60）
    键盘输入N,d，a1，an,m，输出am
    输入数据均不需判错。
算法分析:
    分析该题，对公式：
        Ai=(Ai-1-Ai+1)/2+d         (1〈i〈N）     （n〈60)
    作一翻推敲，探讨其数字变换规律。不然的话会无从下手.
    令 X=A2   s2[i］=（pi,Qi,Ri）表示Ai=PiX+QiD+RiA1
    我们可以根据
        Ai=Ai—2-2Ai-1+2D
          =PiX+QiD+RiA1
    推出公式
        PiX+QiD+RiA1=（Pi-2—2Pi—1）X+(Qi-2-2Qi—1+2）D+(Ri-2—2Ri—1）A1
    比较等号两端X，D和A1的系数项，可得
        Pi=Pi—2—2Pi—1
        Qi=Qi—2-2Qi—1+2
        Ri=Ri-2-2Ri—1
    加上两个边界条件
        P1=0    Q1=0    R1=1    (A1=A1）
        P2=1    Q2=0    R2=0    （A2=A2)
    根据Pi、Qi、Ri的递推式，可以计算出
        S2［1]=（0,0，1);
        S2[3]=(—2，2,1)；
        S2[4］=（5，—2，-2）;
        S2[5]=（-12,8,5);
        。......。..。...。。。。.
        S2［i］=（Pi,Qi，Ri);
        。.。.。.。...。。。..。。。.
        S2[N］=(PN,QN,RN)；
    有了上述基础，AM便不难求得。有两种方法：
    1、由于AN、A1和PN、QN、RN已知,因此可以先根据公式:
        A2=AN—QND—RNA1/PN
    求出A2。然后将A2代入公式
        A3=A1-2A2+2D
    求出A3。然后将A3代入公式
        A4=A2—2A3+2D
    求出A4。然后将A4代入公式
    。....。。...。。。。.。.。。.。..。..。。
    求出Ai—1.然后将Ai—1代入公式
        Ai=Ai—2—2Ai—1+2D
    求出Ai。依此类推，直至递推至AM为止.
    上述算法的缺陷是由于A2是两数相除的结果，而除数PN递增，因此精度误差在所难免，以后的递推过程又不断地将误差扩大，以至当M超过40时，求出的AM明显徧离正确值。显然这种方法简单但不可靠。
    2、我们令A2=A2，A3=X，由S3[i]=（Pi,Qi,Ri)表示Ai=PiX+QiD+RiA2  (i〉=2） 可计算出：
        S3［2]=(0,0,1）=S2［1］;
        S3[3]=（1，0，0）=S2[2］;
        S3［4］=（-2,2,1)=S2［3］；
        S3[5］=（5,-2-2）=S2［4］;
        。。。。。.。....。。....。.。.。
        S3［i]=(。。。。.。。。。.)=S2［i—1]；
        .。。。..。。。。。..。.。.。..。
        S3［N］=(。。。..。。..。)=S2[N—1];
    再令A3=A3，A4=X,由S4[i]=(pi，Qi,Ri）表示Ai=PiX+QiD+RiA3   （i〉=3) 可计算得出：
        S4［3]=(0,0，1）=S3［2]=S2［1］；
        S4［4］=（1，0,0）=S3［3]=S2[2］;
        S4[5]=（—22，1)=S3［4］=S2［3］;
        ...。.。。.。....。.。.。。.。。...。
        S4[i］=（..。。.。.。。..）=S3[i-1]=S2［i—2］;
        .。.。。。。。.。。。.。.。..。。。。.
        S4[N]=(.。。.。.。..。.）=S3［N-1]=S2［N-2];
     依此类推，我们可以发现一个有趣的式子：
        AN=PN-i+2*Ai+QN-i+2＊D+RN-i+2＊Ai-1,  即
        Ai=(AN—QN—i+2*D-RN-i+2＊Ai-1)/PN—i+2
    我们从已知量A1和AN出发，依据上述公式顺序递推A2、A3、。。。、AM.由于PN—i+2递减,因此最后得出的AM要比第一种算法趋于精确。
程序代码如下：
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}