用贪心算法实现加油问题.doc

软件学院 算法分析与设计 课程实验报告2014 2015学年 第 二 学期 2012 级 软件工程 专业实验四 贪心算法一、实验目的1)理解贪心算法的概念2)掌握贪心算法的基本要素3)掌握设计贪心算法的一般步骤4)针对具体问题，能应用贪心算法设计有效算法二、实验环境1. PC机一台，VC6.0三、实验内容问题描述一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并说明算法能产生一个最优解。编程任务对于给定的n和k个加油站位置，编程计算最少加油次数。样例例如，现在汽车加满油之后可跑7公里，途中共有7个加油站，各个加油站之间的距离为1公里、2公里、3公里、4公里、5公里、1公里、6公里、6公里。那么，汽车可在_第三，第四，第五，第七个加油站_（哪几个加油站）加油，使沿途加油次数最少，只需加油_4_次。 问题分析由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。数据输入由文件input.txt给出输入数据。第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。结果输出将编程计算出的最少加油次数以及应在哪些加油站加油输出到文件output.txt。如果无法到达目的地，则输出”No Solution”。测试数据序号输入文件(input.txt)输出文件(output.txt)0.7 71 2 3 4 5 1 6 641.3708 633 20 83 77 26 59 6702.630 3746 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 7333.181 4654 94 61 51 51 57 73 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 9418四、实验过程.#includeint k=0;int jiayou(int a,int b,int c100,int d)int i,j=0;for(i=d;ia)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);elsee