|
实用算法 ( 基础算法 - 递推法 -01) |
|
有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式： Fn=g(Fn-1) 这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件 ( 或最终结果 ) 入手，一步步地按递推关系递推，直至求出最终结果 ( 或初始值 ) 。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件 ( 最终结果 ) ，问题就好解决，让计算机一步步算就是了，让高速的计算机做这种重复运算，可真正起到 “ 物尽其用 ” 的效果。 递推分倒推法和顺推法两种形式。一般分析思路： if 求解条件 F1 then begin{ 倒推 } 由题意 ( 或递推关系 ) 确定最终结果 Fa ； 求出倒推关系式 Fi-1=g'(Fi); i=n;{ 从最终结果 Fn 出发进行倒推 } while 当前结果 Fi 非初始值 F1 do 由 Fi-1=g(F1) 倒推前项； 输出倒推结果 F1 和倒推过程； end {then} else begin{ 顺推 } 由题意 ( 或顺推关系 ) 确定初始值 F1( 边界条件 ) ； 求出顺推关系式 F1=g(Fi-1); i=1;{ 由边界条件 F1 出发进行顺推 } while 当前结果 Fi 非最终结果 Fn do 由 Fi=g(Fi-1) 顺推后项； 输出顺推结果 Fn 和顺推过程； end; {else} 一、倒推法 所谓倒推法，就是在不知初始值的情况下，经某种递推关系而获知问题的解或目标，再倒推过来，推知它的初始条件。因为这类问题的运算过程是一一映射的，故可分析得其递推公式。然后再从这个解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。 下面举例说明。 [ 例 1] 贮油点 一辆重型卡车欲穿过 1000 公里的沙漠，卡车耗油为 1 升 / 公里，卡车总载油能力为 500 公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？ 算法分析： 编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。 No. Distance(k.m.) oil(litre) 1 X X X X 2 X X X X 3 X X X X ........ ...... 设 dis[i] 为第 i 个贮油点至终点 (i=0) 的距离； oil[i] 为第 i 个贮油点的存贮油量； 我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。 下图表示倒推时的返回点：
从贮油点 i 向贮油点 i+1 倒推的策略是，卡车在点 i 和点 i+1 间往返若干次。卡车每次返回 i+1 处时正好耗尽 500 公升汽油，而每次从 i+1 出发时又必须装足 500 公升汽油。两点之间的距离必须满足在耗油最少的条件下使 i 点贮足 i*500 分升汽油的要求 (0<=i<=n-1) 。具体地讲，第一个贮油点 i=1 应距终点 i=0 处 500km 且在该处贮藏 500 公升汽油，这样才能保证卡车能由 i=1 处到达终点 i=0 处，这就是说 dis[1]=500 oil[1]=500; 为了在 i=1 处贮藏 500 公升汽油，卡车至少从 i=2 处开两趟满载油的车至 i=1 处。所以 i=2 处至少贮有 2*500 公升汽油，即 oil[2]=500*2=1000 。另外，再加上从 i=1 返回至 i=2 处的一趟空载，合计往返 3 次。三次往返路程的耗油量按最省要求只能为 500 公升。即 d12=500/3km dis[2]=dis[1]+d12=dis[1]+500/3
为了在 i=2 处贮存 1000 公升汽油，卡车至少从 i=3 处开三趟满载油的车至 i=2 处。报以 i=3 处至少贮有 3*500 公升汽油，即 oil[3]=500*3=1500 。加上 i=2 至 i=3 处的二趟返程空车，合计 5 次。路途耗油量也应为 500 公升，即 d23=500/5, dis[3]=dis[2]+d23=dis[2]+500/5;
依此类推，为了在 i=k 处贮藏 k*500 公升汽油，卡车至少从 i=k+1 处开 k 趟满载车至 i=k 处，即 oil[k+1]=[k+1]*500=oil[k]+500 ，加上从 i=k 处返回 i=k+1 的 k-1 趟返程空间，合计 2k-1 次。这 2k-1 次总耗油量按最省要求为 500 公升，即 dk,k+1=500/(2k-1) dis[k+1]=dis[k]+dk,k+1 =dis[k]+500/(2k-1);
最后， i=n 至始点的距离为 1000-dis[n],oil[n]=500*n 。为了在 i=n 处取得 n*500 公升汽油，卡车至少从始点开 n+1 次满载车至 i=n ，加上从 i=n 返回始点的 n 趟返程空车，合计 2n+1 次， 2n+1 趟的总耗油量应正好为 (1000-dis[n])*(2n+1) ，即始点藏油为 oil[n]+(1000-dis[n])*(2n+1) 。 下面为程序代码： program oil_lib; var k:integer; { 贮油点位置序号 } d, { 累计终点至当前贮油点的距离 } d1:real;{i=n 至始点的距离 } oil,dis:array[1..10] of real; i:integer; { 辅助变量 } begin writeln('NO.','distance(k.m)':30,'oil(1.)':80); k:=1; d:=500; { 从 i=1 处开始向始点倒推 } dis[1]:=500; oil[1]:=500; repeat k:=k+1; d:=d+500/(2*k-1); dis[k]:=d; oil[k]:=oil[k-1]+500; until d>=1000;
dis[k]:=1000; { 置始点至终点的距离值 } d1:=1000-dis[k-1]; { 求 i=n 处至始点的距离 } oil[k]:=d1*(2*k+1)+oil[k-1]; { 求始点藏油量 } for i:=0 to k do { 由始点开始，逐一打印始点至当前贮油点的距离和藏油量 } writeln(i,1000-dis[k-i]:30,oil[k-i]:80); end. {main}
转换为 C 语言程序如下： #include<stdio.h> void main() { int k;/* 贮油点位置序号 */ float d,d1; /*d: 累计终点至当前贮油点的距离 ,d1:i=n 至始点的距离 */ float oil[10],dis[10]; int i; printf("NO. distance(k.m.)/toil(l.)/n"); k=1; d=500; /* 从 i=1 处开始向始点倒推 */ dis[1]=500; oil[1]=500; do{ k=k+1; d=d+500/(2*k-1); dis[k]=d; oil[k]=oil[k-1]+500; }while(!(d>=1000)); dis[k]=1000; /* 置始点至终点的距离值 */ d1=1000-dis[k-1]; /* 求 i=n 处至始点的距离 */ oil[k]=d1*(2*k+1)+oil[k-1]; /* 求始点藏油量 */ for(i=0;i<k;i++) /* 由始点开始逐一打印始点至当前贮油点的距离和藏油量 */ printf("%d/t%f/t%f/t/n",i,1000-dis[k-i],oil[k-i]); }
|
|
实用算法 ( 基础算法 - 递推法 -02) |
|
顺推法 倒推法的逆过程就是顺推法，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值 ...... ，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。 实数数列：一个实数数列共有 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
A(i-1)=( A(i-2)-A(i) )/2+d, 可以推出 A(i)=A(i-2)-2A(i-1)+2d A(i)=A(i-2)-2A(i-1)+2d=P(i)X+Q(i)d+R(i)A(1) 所以 A(i-2)=P(i-2)X+Q(i-2)d+R(i-2)A(1) A(i-1)=P(i-1)X+Q(i-1)d+R(i-1)A(1) 这样就推出 PiX+QiD+RiA1=(Pi-2-2Pi-1)X+(Qi-2-2Qi-1+2)D+(Ri-2-2Ri-1)A1
推出公式 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)} fori:=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}
|
