算法_汽车加油问题

《算法_汽车加油问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告实验名称：汽车加油问题实验日期：学生姓名：学生学号：一、实验目的一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n和k个加油站位置，计算最少加油次数。二、实验环境Windows7+VisualStudio2010三、实验内容1.设计思路利用贪心算法每次使加油前行驶距离最大，一旦剩余油量不够行驶下一个加油站，就将油加满，从而最终到达目的地。2.相关模块#includeusingnamespacestd;voidmain(){intn,//加满

2、油能走的距离k;//加油站个数cin>>n>>k;int*dist=newint[k+1];//被加油站分割出的k+1段路程的长度for(inti=0;i<=k;++i)cin>>dist[i];intpetrol=n,//剩下油量count=0;//加油次数//判断是否有Solution,该步可以被合并for(inti=0;i<=k;++i){if(dist[i]>n)cout<<"NoSolution"<petrol){++count;petrol

3、=n-dist[i];}//还有油能到达下一站elsepetrol-=dist[i];}cout<