算法设计与分析 · 2022年5月10日 0

算法设计之汽车加油问题

演示PPT下载

1.问题描述

已知一辆汽车加满油后可行驶n千米,而旅途中有若干个加油站。每个加油站的位置是以及知的。试问汽车一个在途中哪些加油站停靠加油,以保证顺利到达终点并且加油次数最少试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少请写出该算法。

2.算法分析

  1. 定义全局变量N(加满油最大可行驶距离)。
  2. 首先将据每一个加油站到下一个加油站的距离加入数组arr中。
  3. 创建列表list,存需加油下标。
  4. 定义一个当前油量 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);//输出需要加油的下标
    }
}