“请你编程”95001讲评

广州 陆文杰
1995-03-31

        汽车穿越沙漠的整个过程是怎样的呢?广西覃东晟同学画出了下面的示意图：
        这个图说明：不管加油站定在何处，均可如图对它们编号，而且1、2站之间的路程必定经过了三次(因为经过次数愈多耗油也越多)，2、3号站之间必定经过了五次。归纳之，i号加油站和i+1号加油站之间必定经过了2i+1次。
        由于要求汽车所走的路程最短，那么各站之间的距离应尽量远。由题意，1号加油站应设在距终点500公里处。假设第2号加油站应在距第1号x公里处，这时必有3x+500≤2*500,也即x≤500/3(其中3x是2号到1号之间的耗油量)。因各站之间距离应尽量远，故取x=500/3，类似的分析可得第3号加油站应设在距离第2号500/5公里处。运用归纳法，第i+1号加油站应设在离i号500/(2i+1)公里处。
        有了上面的分析，编程求最小耗油是不难的。湖北吴云洋用C语言编程如下：
        #include <stdio.h>#define M 1000#define N 500Void main(){float s=N;/*S：这个加油站离终点的距离*/float p=M;/*P：终点或中途加油站离始点的距离*/
        int i=1;/*倒数第i个加油站*/
        do printf("倒数第%d个加油站在离起点%.3f公里处。\n",\i,p-=(float)N/(2*i-1);
        while((s+=(float)N/(++i*2-1))<M);s-=(float)N/(i--*2-1);printf("\nTotal=%.3f",i*N+(float)(M-s)*(2*i+1));}
        这个程序求出的最小耗油量是3836.497升，倒数第7个加油站是最后一个站，距起点22.433公里。计算表明，从起点到倒数第七站运油时必有一次不是满载。
        请注意上面程序中的强制类型转换“(float)”，很多读者忽略了这一点，所以求出的最小耗油量偏大。
        同样的思路，四川曹林用QBasic编出如下程序：
        P=500 'P：相邻两站的用油量
        X=0 'X：行使的路程
        Y=1 'Y：从一站到下一站用油是单程的几倍
        Z=500 'Z：各加油站拥有油量
        PRINT "距终点";500;"公里,";"拥有油量";ZWHILE X<500Y=Y+2IF X+P/Y>500 THEN P=(500-X)*YX=X+P/YZ=Z+PPRINT "距终点"；500-X；"公里，"；"拥有油量"；ZWENDEND
        湖南李南松避开了耗时较大的浮点运算，他的程序执行速度极快：
        #define MaxLoad 50000000L#define MaxLen 100000000Lint main(){long len,total=0;je=0;/*total:累计用油，je：累计距离*/long count;/*各站间路段最少驾车次数*/int k=0;/*路段计数*/while(1){if((total-1)%(MaxLoad-2)==0)count=(total-1)/(MaxLoad-2);else count=(total-1)/(MaxLoad-2)+1;len=(MaxLoad*conut-total)/(2*count-1);if(je+=len)≥MaxLen)}len=MaxLen=je+len;printf("k=%d len=%f oil=%f\n",k,(float)len/1.0E5,(float)total/1.0E5);total+=len*(2*count-1);break;}printf("k=%d len=%f oil=%f\n",k,(float)len/1.0E5,(float)total/1.0E5);total+=len*(2*count-1);k++;}printf("Total=%f\n",total/1.0E5);}
        上面程序是基于这样一个事实，即500*count-(2*count-1)*len(>=+total也即count>=(total-len)/(500-2*len)，要count的最小值，必有len=1,故count为不小于(total)/(500-2)的最小整数。
        也有少数读者采用直接搜索法，这样的解法似乎更令人信服。如广西陆秀忠的程序也相当漂亮，但限下篇幅，这次的讲评就到此为止了。
        最后我们采用电脑抽奖法确定了10名作为这次“请你编程”的幸运者，他们是：
        广西 陆秀忠
        四川 曹林
        浙江 李南松
        湖北 吴云洋
        浙江 胡茂华
        安徽 刘险峰
        四川 花仕良
        安徽 丁美怀
        上海 林孙义
        广州 陆文杰
        ［本期题目］95003
        请编一个电脑抽奖程序，在输入候奖人数、人名及获奖人数后，电脑按照机会均等原则确定出获奖者名单。要求：程序简洁，结构清晰、操作方便、算法合情合理。
 
 