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

2016-02-19 14:04 4 1 收藏

想不想get新技能酷炫一下,今天图老师小编就跟大家分享个简单的实用算法(基础算法-递推法-02)教程,一起来看看吧!超容易上手~

【 tulaoshi.com - 编程语言 】


  
  
  顺推法
      倒推法的逆过程就是顺推法,即由边界条件出发,通过递推关系式推出后项值,再由后项值按递推关系式推出再后项值......,依次递推,直至从问题初始陈述向前推进到这个问题的解为止。
      实数数列:一个实数数列共有N项,已知
              ai=(ai-1-ai+1)/2+d,   (1iN)(N60)
      键盘输入N,d,a1,an,m,输出am
      输入数据均不需判错。
  算法分析:
      分析该题,对公式:
          Ai=(Ai-1-Ai+1)/2+d         (1iN)     (n60)
      作一翻推敲,探讨其数字变换规律。不然的话会无从下手。
      令 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 =');
       
  

来源:http://www.tulaoshi.com/n/20160219/1606104.html

延伸阅读
  // 节日算法 请参见 《农历与西历对照、万年历》 unit CNYear; interface uses sysutils; type TCNDate = Cardinal; function DecodeGregToCNDate(dtGreg:TDateTime):TCNDate; function GetGregDateFromCN(cnYear,cnMonth,cnDay:word;bLeap:Boolean=False):TDateTime; function GregDate...
残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注重当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - 3 a所示)。事实上,对于任意k,恰好存在22k 种不同的残缺棋盘。 残缺棋盘的问题要求用三格板(t r i o m i n o e s)覆盖...
CRC算法与实现 作者:bhw98 提交者:eastvc 发布日期:2004-1-2 20:57:13 原文出处:http://www.csdn.net/ 摘要: 本文首先讨论了CRC的代数学算法,然后以常见的CRC-ITU为例,通过硬件电路的实现,引出了比特型算法,最后重点介绍了字节型快速查表算法,给出了相应的C语言实现。 关键词: CRC, FCS, 生成多项式, 检错重传 引言 ...
这个问题来自例1 - 2。船可以分步装载,每步装一个货箱,且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则:从剩下的货箱中,选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小,从而可以装载更多的货箱。根据这种贪婪策略,首先选择最轻的货箱,然后选次轻的货箱,如此下去直到所有货箱均装上船或船上不能再容纳其...
    首先,我们先看看这个游戏的规则,给出4个1-9之间的自然数,例如:1,5,5,5(这是很经典的一个例子哦 ^_^)。在1,5,5,5中间用+、-、*、/来运算后得到24这个数。每个数只能使用一次。如果没有计算过的基本都会被难住吧。哈哈,答案是 5*(5-1/5)。是不是很经典呢?和它类似的还有3,3,8,8。     下...

经验教程

39

收藏

21
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部