2022年算法实验报告实验-汽车加油问题 .pdf

算法实验报告算法分析与设计实验报告实验名称：汽车加油问题实验日期： 2011/03/26 学生姓名：学生学号：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 算法实验报告一、实验目的一辆汽车加满油后可行驶nkm 。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的 n 和 k 个加油站位置，计算最少加油次数。二、实验环境Windows7 + Visual Studio 2010三、实验内容1. 设计思路利用贪心算法每次使加油前行驶距离最大，一旦剩余油量不够行驶下一个加油站，就将油加满，从而最终到达目的地。2. 相关模块#include #include usingnamespacestd; 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+Algorithmsin4-9.txt; char* outFileName = H:C+Algorithmsout4-9.txt; ifstream input(inFileName,ios:in); / 从文件读取数据input distance stations; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 算法实验报告int *a = newint stations+1;/ 记录每两个站之间的距离（包括起点到第一个加油站和最后一个加油站到终点的距离）for ( int i=0; i ai; 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; idistance)/ 如果站间距离大于加满油能行驶，则无法到达目的地return -1; rest -= ai; if (restai+1)/ 如果下一个站间距离大于剩下能行驶的距离，则需要加一次油 count+; rest = 7; return count; void write(char * filename,int num) ofstream output; output.open(filename,ios:out); outputnum; output.close(); 四、实验结果分析及结论名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 算法实验报告名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -