实用算法(基础算法-递推法).doc

: .
实用算法（基础算法-递推法-01）
有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这量按最省要求为 500 公升，即
dk,k+1=500/(2k-1)
dis[k+1]=dis[k]+d k,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()':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<>
void main()
{
int k; /* 贮油点位置序号 */
float d,d1; /*d: 累计终点至当前贮油点的距离 ,d1:i=n 至始点的距离 */
float oil[10],dis[10];
int i;
printf("NO. distance(.)\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+