算法分析_贪心算法解汽车加油问题_实验报告

综合性、性实验报告 姓名    唐艳      学号 200908001124 专业 计算机科学与技术 班级2009级  班 实验课程名称      算法设计与分析    指导教师及职称    吕兰兰 讲师      开课学期 2011 至 2012  学年  上  学期 上课时间    2011年 10 月 18 日    湖南科技学院教务处编印 一、实验设计 实验名称：贪心算法实例编程 实验时间：2011-11-08 小组合作： 是○ 否● 小组成员：无 1、实验目的： 1) 理解贪心算法的概念 2) 掌握贪心算法的基本要素 3) 掌握设计贪心算法的一般步骤 4) 针对具体问题，能应用贪心算法设计有效算法 5) 用C++实现算法，并且分析算法的效率 2、实验设备及材料：（注意：请自行填写，按实际情况写，各位同学的实验报告应有所区别） 硬件设备： PC机一台 机器配置：良好 操作系统：windows 7 开发工具：VC++6.0 3、实验内容： ①问题描述 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。并说明算法能产生一个最优解。 ②编程任务 对于给定的n和k个加油站位置，编程计算最少加油次数。 ③样例 例如，现在汽车加满油之后可跑7公里，途中共有7个加油站，各个加油站之间的距离为1公里、2公里、3公里、4公里、5公里、1公里、6公里、6公里。 那么，汽车可在____第三，第四，第五，第七个加油站______（哪几个加油站）加油，使沿途加油次数最少，只需加油___4_____次。       4、实验方法步骤及注意事项：（注意：此部分为本实验的关键部分，请自行填写，不得雷同！） ①实验步骤（请参考教材自行归纳之后再认真填写） [问题分析] 由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。 提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。 加油站贪心算法设计（C++）： #include #include"iostream.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;i<=k+1;i++) { sum+=a[i]; if(sum>n) {count++;sum=0;i--; fout<>n; fin>>k; for(i=1;i<=k+1;i++) fin>>a[i]; if(a[i]>n) printf("No Soluthion!"); else { number=greed(n,k,a); fout<n后，i的次数要减1。因为在距离大于可行驶的距离之前就应该之前的加油站加油了。 （如实填写，忌文不对题） 若重做本实验，为实现预期效果，仪器操作和实验步骤应如何改善： 我认为此贪心算法不需要再改进，够贪心了。 （如实填写，忌文不对题） 3）、对实验的自我评价： 对文件的输入输出的使用还没完全掌握。 （注：自己的体会、感想和收获等） 指导老师评语及得分： 签名： 吕兰兰 2011年 11 月 15 日