C语言算法——顺推法.docVIP

顺推法 ??倒推法的逆过程就是顺推法，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值......，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。 ??实数数列：一个实数数列共有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=(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=(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=(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=(..........)=S2[i-1]; ????..................... ????S3[N]=(..........)=S2[N-1]; ??再令A3=A3,A4=X,由S4=(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=(...........)=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