分享
 
 
 

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

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

顺推法

倒推法的逆过程就是顺推法,即由边界条件出发,通过递推关系式推出后项值,再由后项值按递推关系式推出再后项值......,依次递推,直至从问题初始陈述向前推进到这个问题的解为止。

实数数列:一个实数数列共有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 =');

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有