算法分析-贪心算法解汽车加油问题-实验报告(共7页).doc

《算法分析-贪心算法解汽车加油问题-实验报告(共7页).doc》由会员分享，可在线阅读，更多相关《算法分析-贪心算法解汽车加油问题-实验报告(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上综合性、设计性实验报告姓名 唐艳 学号 4专业 计算机科学与技术 班级2009级 班实验课程名称 算法设计与分析 指导教师及职称 吕兰兰 讲师 开课学期 2011 至 2012 学年 上 学期上课时间 2011年 10 月 18 日 湖南科技学院教务处编印专心-专注-专业一、实验设计方案实验名称：贪心算法实例编程实验时间：2011-11-08 小组合作： 是 否小组成员：无1、实验目的： 1) 理解贪心算法的概念2) 掌握贪心算法的基本要素3) 掌握设计贪心算法的一般步骤4) 针对具体问题，能应用贪心算法设计有效算法5) 用C+实现算法，并且分析算法的效率2、实验设备

2、及材料：（注意：请自行填写，按实际情况写，各位同学的实验报告应有所区别）硬件设备： PC机一台机器配置：良好操作系统：windows 7开发工具：VC+6.03、实验内容： 问题描述一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并说明算法能产生一个最优解。编程任务对于给定的n和k个加油站位置，编程计算最少加油次数。样例例如，现在汽车加满油之后可跑7公里，途中共有7个加油站，各个加油站之间的距离为1公里、2公里、3公里、4公里、5公里、1公里、6公里、6公里。那么，汽车可在_第三，第四，第五，第七个加油站_（哪几个加油站）加

3、油，使沿途加油次数最少，只需加油_4_次。4、实验方法步骤及注意事项：（注意：此部分为本实验的关键部分，请自行填写，不得雷同！）实验步骤（请参考教材自行总结归纳之后再认真填写）问题分析由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的

4、求解。加油站贪心算法设计（C+）：#include#includeiostream.h#include int greed(int n,int k,int *a)int sum=0,count=0;ifstream fin;fin.open(D:input.txt);ofstream fout(D:output.txt);for(int i=1;in)count+;sum=0;i-;foutin;fink;for(i=1;iai;if(ain)printf(No Soluthion!);elsenumber=greed(n,k,a);foutn后，i的次数要减1。因为在距离大于可行驶的距离之前就应该之前的加油站加油了。（如实填写，忌文不对题）若重做本实验，为实现预期效果，仪器操作和实验步骤应如何改善：我认为此贪心算法不需要再改进，够贪心了。（如实填写，忌文不对题）3）、对实验的自我评价：对文件的输入输出的使用还没完全掌握。（注：自己的体会、感想和收获等）指导老师评语及得分：签名： 吕兰兰 2011年 11 月 15 日