《用贪心算法实现加油问题.pdf》由会员分享，可在线阅读，更多相关《用贪心算法实现加油问题.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、用贪心算法实现加油问题1/4 软件学院算法分析与设计课程实验报告2014 2015 学年 第 二 学期 2012 级软件工程专业实验四贪心算法一、实验目的1)理解贪心算法的概念2)掌握贪心算法的基本要素3)掌握设计贪心算法的一般步骤4)针对具体问题，能应用贪心算法设计有效算法二、实验环境1.PC 机一台，VC6.0 三、实验内容问题描述一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并说明算法能产生一个最优解。编程任务对于给定的n 和 k 个加油站位置，编程计算最少加油次数。样例例如，现在汽车加满油之后可跑7 公里，途中共有
2、 7 个加油站，各个加油站之间的距离为1 公里、2 公里、3 公里、4 公里、5 公里、1 公里、6 公里、6 公里。那么，汽车可在_第三，第四，第五，第七个加油站 _（哪几个加油站）加油，使沿途加油次数最少，只需加油_4_次。4问题分析 由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的方法进行下去
3、。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。5 数据输入用贪心算法实现加油问题2/4 由文件 input.txt 给出输入数据。第一行有2 个正整数 n 和 k，表示汽车加满油后可行驶n 公里，且旅途中有k 个加油站。接下来的1 行中，有 k+1 个整数，表示第k 个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。6 结果输出将编程计算出的最少加油次数以及应在哪些加油站加油输出到文件output.txt。如果无法到达目的地，则输出”No Solution”。7 测试数据四、实验过程.#include int k=0;
4、int jiayou(int a,int b,int c100,int d)int i,j=0;for(i=d;ia)序号输入文件(input.txt)输出文件(output.txt)0.7 7 1 2 3 4 5 1 6 6 4 1.3708 6 33 20 83 77 26 59 67 0 2.630 37 46 43 94 77 45 98 11 60 15 42 7 69 61 54 51 65 50 16 28 60 91 17 44 54 93 52 32 54 41 80 88 54 55 27 58 59 92 73 3 3.181 46 54 94 61 51 51 57 7
5、3 96 32 45 97 73 44 88 25 14 53 59 79 41 63 100 25 57 35 55 61 88 54 40 77 1 53 86 67 59 13 56 96 56 75 45 37 76 99 41 94 18 用贪心算法实现加油问题3/4 break;d=i;k+;if(d=b+1)return k;jiayou(a,b,c,d);int main()int a,b,int c100,int d=1,e,int i,m=0;while(scanf(%d%d,&a,&b)!=EOF&a!=0)for(i=1;i=b+1;i+)scanf(%d,&ci);for(i=1;i=b+1;i+)m=m+ci;if(m=a)printf(0n);else e=jiayou(a,b,c,d);printf(%dn,e);用贪心算法实现加油问题4/4 五、实验总结经过这次试验我更加学习到了谈心算法的应用，夜了解了用递归算法来实现贪心算法。