汽车加油问题(贪心算法)

完成时间：大二上

问题描述

汽车加油问题：一辆汽车加满油后可以行驶n千米。旅途中有k个加油站。若要使沿途的加油次数最少，设计一个有效的算法，采用贪心算法，编程计算并输出最少加油次数，以及指出应在那些加油站停靠加油。
数据输入：由文件input.txt 给出输入数据。第一行有2个正整数n和k，表示汽车加满油后可行驶n km，且旅途中有k个加油站。接下来1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。
结果输出： 将编程计算出的最少加油次数，以及哪些加油站，输出到文件ouput.txt。如果无法到达目的地，则输出“No Solution”。

源码

for i in range(len(l)):
        if n < l[i]:
            refueling(L2[0],L3,x,pos)
            with open("output.txt","w") as f:
                f.write("No Solution")
            return
    while temp - l[x] > 0:
        temp -= l[x]
        x += 1
        if x == len(l):
            # print("汽车已经到达")
            break
        if (temp - l[x]) <= 0:
            pos += 1
            L_res.append(x)
            L_pos.append(pos)
            refueling(n,l,x,pos)

其中，传入for循环的列表L，存储各站点之间的距离信息，如果n小于其中任意站点间距之一，则汽车无法到达目的地，输出No Solution，反之，则对n进行减运算，n依次减去站点间距，直到小于0，此时pos加1（pos表示需要加油的次数），并将此时的x记录（x表示需要在此加油），记录此时的x的值，并进行递归，直到遍历完成，即 x 等于 列表L的长度，此时停止。

说明

本实验完成于大二上学期（2021下半年），所使用语言为Python