1.问题描述
已知一辆汽车加满油后可行驶n千米,而旅途中有若干个加油站。每个加油站的位置是以及知的。试问汽车一个在途中哪些加油站停靠加油,以保证顺利到达终点并且加油次数最少试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少请写出该算法。
2.算法分析
- 定义全局变量N(加满油最大可行驶距离)。
- 首先将据每一个加油站到下一个加油站的距离加入数组arr中。
- 创建列表list,存需加油下标。
- 定义一个当前油量 sy ,初值为N;
遍历每一个arr中元素, 判断是否大于N;大于则加满油也无法到达下一站;输出无法到达,结束该程序。 当前拥有油量(sy)是否可以到达下一站。 如果不能:则加满油(sy=N),list中添加当前下标。 前往下一个加油站(sy减去当前距离)
3.Java代码展示
public class car {
static int N = 100;//加满油可以行驶距离
public static void main(String[] args) {
int[] arr = {41,67,34,10,69,24,8,58,62,64};//距离下一个加油站的距离
int sy = 100;//剩下油可以走的距离,
List<Integer> list = new ArrayList<>();//存放需要加油的下标
for (int i = 0; i < arr.length; i++) {//从第一个开始遍历每一个加油站
if (arr[i]>N) {
//前往下一给加油站的距离大于满油可以行驶的距离,所以不能到达
System.out.println("不能到达!");
return;
}
if (sy<arr[i]){//当前油量不足以到达下一个加油站,
list.add(i);//添加加油下标
sy=100;//加满油
}
sy-=arr[i];//走过这一段
}
System.out.println("需要加油的下标为"+list);//输出需要加油的下标
}
}