论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

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

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:45:40




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

       

视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058