算法实验报告--实验4-9汽车加油问题.doc

算法分析与设计 实验报告 实验名称： 汽车加油问题 实验日期： 2011/03/26 学生姓名： 学生学号： 一、实验目的 一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n和k个加油站位置，计算最少加油次数。 二、实验环境 Windows7 + Visual Studio 2010 三、实验内容 1. 设计思路 利用贪心算法每次使加油前行驶距离最大，一旦剩余油量不够行驶下一个加油站，就将油加满，从而最终到达目的地。 2. 相关模块 #include <iostream> #include <fstream> using namespace std; int PetrolCount(int *a, int n, int distance); void write(char* filename,int num); int main() { int distance = 0;//加满油可行驶里程 int stations = 0;//总加油站数 char* inFileName = "H:\\C++\\Algorithms\\in4-9.txt"; char* outFileName = "H:\\C++\\Algorithms\\out4-9.txt"; ifstream input(inFileName,ios::in); //从文件读取数据 input >> distance >> stations; int *a = new int[stations+1]; //记录每两个站之间的距离（包括起点到第一个加油站和最后一个加油站到终点的距离） for(int i=0; i<stations+1; ++i) input >> a[i]; input.close(); //将加油次数写入文件 write(outFileName,PetrolCount(a,stations+1,distance)); system("pause"); return 0; } //计算加油次数 int PetrolCount(int *a, int n, int distance) { int count = 0;//加油次数 int rest = 7;//剩余能行驶的距离 for(int i=0; i<n-1; ++i) { if(a[i]>distance) //如果站间距离大于加满油能行驶，则无法到达目的地 return -1; rest -= a[i]; if(rest<a[i+1]) //如果下一个站间距离大于剩下能行驶的距离，则需要加一次油 { count++; rest = 7; } } return count; } void write(char* filename,int num) { ofstream output; output.open(filename,ios::out); output << num; output.close(); } 四、实验结果分析及结论