文档介绍：精品文档，供参考！
页脚下载后可删除，如有侵权请告知删除！
精品文档，供参考！
#include<>
int  add_station(int n,int k,int a[],int A[]) //到达目的站时所需的最少加油站次数
{
 int i,s = 0;
 
 for(i=0;i<=k;i++)
 {   if(a[i+1]>n) {cout<<"No Solution"<<endl;return 0;break;}
 
     else
     {
     
        s+=a[i];
        if(s+a[i+1] < n)  A[i] = 0;
        else {A[i] = 1;s =0;}
     }
 
 }
 
 return 1;
}
int main()
{
 int i,k,n,t,s=0;
 cout<<"请输入汽车一次加油可行驶的最大距离:";cin>>n;
 cout<<"请输入旅途中的加油站数目:";cin>>k;
 int *a = new int [k+1+1];
 int *A = new int [k+1+1];
 a[0] = 0;
 cout<<"请输入各个站点的距离(以空格分隔)共"<<k+1<<"段:/n";
 for (i=1;i<=k+1;i++)
     cin>>a[i];
 
 for(i=0;i<k+1;i++)
     A[i] = 0;
 cout<<"输出最少的加油次数:/n";
 t = add_station( n, k, a, A);
if(t ==0) return 0;
else{
 
for(i=0;i<k+1;i++)
    s+= A[i] ;
cout<<s<<endl;
精品文档，供参考！
页脚下载后可删除，如有侵权请告知删除！
精品文档，供参考！
}
}
 
 
一、实验名称：
用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。
二、实验目的：
课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的：
（1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法；
（2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法；
（3）使学生提高对实际问题的分析、设计和实现能力；
（4）为学生后续课程的学习及课程设计打下坚实的实践基础。
三、使用的策略：
贪心算法、回溯算法等。
四、实验内容：
（一）问题描述
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。
给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。
（二）问题分析（前提行驶前车里加满油）
对于这个问题我们有以下几种情况：设加油次数为k，