《c语言算法——顺推法》由会员分享，可在线阅读，更多相关《c语言算法——顺推法（3页珍藏版）》请在金锄头文库上搜索。
1、顺推法 倒推法的逆过程就是顺推法，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值.，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。 实数数列：一个实数数列共有 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=(pi,Qi,Ri)表示 Ai=PiX+QiD+RiA1 我们可以根据 Ai=Ai-2
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 的递推式，可以计算出 S21=(0,0,1); S23=(-2,2,1); S24=(5,-2,-2); S25=(-12,8,5); . S2=(Pi,Q
3、i,Ri); . S2N=(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 递增，因此精度误差在所难免，以后的递推过程又不
4、断地将误差扩大，以至当 M 超过 40 时，求出的 AM 明显徧离正确值。显然这种方法简单但不可*。 2、我们令 A2=A2,A3=X，由 S3=(Pi,Qi,Ri)表示 Ai=PiX+QiD+RiA2 (i=2) 可计算出： S32=(0,0,1)=S21; S33=(1,0,0)=S22; S34=(-2,2,1)=S23; S35=(5,-2-2)=S24; . S3=(.)=S2i-1; . S3N=(.)=S2N-1; 再令 A3=A3,A4=X,由 S4=(pi,Qi,Ri)表示 Ai=PiX+QiD+RiA3 (i=3) 可计算得出： S43=(0,0,1)=S32=S21; S
5、44=(1,0,0)=S33=S22; S45=(-22,1)=S34=S23; .S4=(.)=S3i-1=S2i-2; . S4N=(.)=S3N-1=S2N-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,
6、m,i :integer; d :real; list :array1.maxn of real; list-对应 ai s :array1.maxn,1.3 of real; si,1-对应 Pi si,2-对应 Qi si,3-对应 Ri procedure init; begin write(n m d =); readln(n,m,d); 输入项数，输出项序号和常数 write(a1 a,n,=); readln(list1,listn); 输入 a1 和 an end; init procedure solve; begin s1,1:=0;s1,2:=0;s1,3:=1; 求递推边
7、界(P1,Q1,R1)和(P2,Q2,R2) s2,1:=1;s2,2:=0;s2,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 si,1:=si-2,1-2*si-1,1; si,2:=si-2,2-2*si-1,2+2; si,3:=si-2,3-2*si-1,3; end; forend;solve procedure main; begin solve; 求(P1,Q1,R1).(Pn,Qn,Rn) 根据公式 Ai=(An-Qn-i+2 * d-Rn-i+2 * Ai-1)/Pn-i
