算法_汽车加油问题.doc

算法分析与设计

实验报告

实验名称： 汽车加油问题
实验日期：
学生姓名：
学生学号：

一、实验目的
一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
对于给定的n和k个加油站位置，计算最少加油次数。
二、实验环境
Windows7 + Visual Studio 2010
三、实验内容
1. 设计思路
利用贪心算法每次使加油前行驶距离最大，一旦剩余油量不够行驶下一个加油站，就将油加满，从而最终到达目的地。
2. 相关模块
#include <iostream>
using namespace std;

void main()
{
int n, //加满油能走的距离
k; //加油站个数
cin >> n >> k;
int *dist = new int [k+1]; //被加油站分割出的k+1段路程的长度
for (int i = 0; i <= k; ++i)
cin >> dist[i];

int petrol = n, //剩下油量
count = 0; //加油次数

//判断是否有Solution, 该步可以被合并
for (int i = 0; i <= k; ++i)
{
if (dist[i] > n)
cout << "No Solution" << endl;
}

for (int i = 1; i <= k; ++i)
{
//跑不完这段距离, 需要加油了
if (dist[i] > petrol)
{
++count;
petrol = n - dist[i];
}
//还有油能到达下一站
else
petrol -= dist[i];
}

cout << count << endl;

system("pause");
}

四、实验结果分析及结论