算法设计之汽车加油问题

演示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);//输出需要加油的下标
    }
}