用贪心算法实现加油问题

《用贪心算法实现加油问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件学院算法分析与设计课程实验报告201〜20j^_学年第二学期2012级软件工程专业实验贪心算法一、实验H的1）理解贪心算法的概念2）掌握贪心算法的基木要素3）掌握设计贪心算法的一般步骤4）针对具体问题，能应用贪心算法设计有效算法二、实验环境1.PC机一台，VC6.0三、实验内容①问题描述一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并说明算法能产生一个最优解。②编程任务对于给定的n和k个加油站位置，编程计算最少加油次数。③样例例如，现在汽车加满汕之后可跑7公里，途中共有7个加汕站，各个加汕站之闹

2、的距离为1公里、2公里、3公里、4公里、5公里、1公里、6公里、6公里。那么，汽车可在_第-:，第四，第五,第七个加油站（哪几个加油站）加油，使沿途加油次数最少，只需加油4次。（4）［问题分析］由于汽车是由始向终点方向幵的，我们最人的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又叫以使我们加汕次数最少。提出问题是解决的开始.为了着手解决遇到的困难，取得最优方案。我们可以假设不到万不得己我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的方法进行下去。最终将各个阶段的最优

3、解合并为原问题的解得到我们原问题的求解。⑤数据输入由文件input.txt给山输入数据。第一行有2个正整数n和k,表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下來的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车己加满油。第k+1个加油站表示目的地。©结果输出将编程计算出的最少加油次数以及应在哪些加油站加油输出到文件output.txto如果无法到达□的地，则输出”NoSolution”。©测试数据序号输入文件(input.txt)输出文件(output.txt)0.771234516641.370863320

4、837726596702.6303746439477459811601542769615451655016286091174454935232544180885455275859927333.18146549461515157739632459773448825145359794163100255735556188544077153866759135696567545377699419418四、实验过程.#includeintk=0;intjiayou(inta,intb，intc[100]，intd){inti,j=0;for(i=d;i<=b+l;

5、i++)j+=c[il;break;d=i;k++;if(d〉=b+l)returnk;jiayou(a，b，c，d);}intmain(){inta,b，intc[100]，intd=l，e，inti，m=O;while(scanf(u%d%dH,&a,&b)!=EOF&&a!=0){for(i=l;i<=b+l;i++){scanf("%d"，&c[i]);}for(i=l;i<=b+l;i++){m=m+c[i];}if(m<=a)printf(HOn);else{e=jiayou(a，b，c，d);printfC.%dn，e);}}五、实验总结经过这次试

6、验我更加学习到了谈心算法的应用，夜了解了用递归算法来实现贪心算法。