SCL编程实例100例-123-贪心算法解决汽车加油问题

- 1 - 问题描述

一辆汽车加满油后可以行驶 n 千米，旅途中有若干 (k) 个加油站，设计一个算法并用西门子 TIA Portal SCL 编程语言编写程序求解最少加油次数。

- 2 - 算法分析

假设汽车的续航里程为 7，沿途加油站数量为 7，相邻两个加油站之间的距离分别为 1、2、3、4、5、1、6、6，得到如下示意图。



根据以上示意图，采用贪心算法解题，根据贪心算法的贪心选择性质，每当到达一个加油站的时候，都要进行一次判断，计算剩余的油量能否维持到下一个加油站。也就是说如果剩余的油量能够到达下一站的话，就不需要在本站停车加油，继续前进；如果不能到达下一站，则需要在本站停车加油，待加满油后继续前进。

- 3 - 硬件选择

PLC：CPU 1214C DC/DC/DC。



- 4 - 程序设计

1.添加功能块FB，命名为：CarRefuel。定义接口变量。



定义输入变量 range，数据类型为整型，即汽车续航里程；定义输入变量 gasNum，数据类型为整型，即路途中加油站数量；定义输入变量 distances，数据类型为整型数组，即路途中每两个相邻加油站之间的距离；定义输出变量 countQ，数据类型为整型，即最少加油次数，作为计算结果的输出；定义静态变量 statSum，数据类型为整型，即加满油后到达下下个加油站的目标行驶路程；定义临时变量 tempI，数据类型为整型，即循环变量；定义局部常量 MAX_N，数据类型为整型，即数组的最大长度。

2.编写算法代码。



参数错误时，函数直接返回。任意两个加油站之间的距离超过续航里程时，输出 0，表示不能到达终点。加满油后，循环累加到达下下个加油站的目标里程，计算是否会超过续航里程，如果超过续航里程则加油 1 次，否则继续累加目标里程。

3.创建一个全局数据块 GdbCarRefuelData，作为以上 FB CarRefuel 的实参。



4.在循环组织块OB MainCarRefuel中调用以上 FB CarRefuel，其背景数据块命名为：InstCarRefuel，配置实参。



- 6 - 功能测试

在 TIA Portal 中仿真启动 PLC，验证计算结果。



输入续航里程 7，沿途加油站数量 7，相邻加油站间隔距离 1、2、3、4、5、1、6、6，计算结果为 4，即最少需要加油 4次。



把沿途第 2 个加油站和第 3 个加油站之间的距离从 3 改为 5，得到计算结果为 5，即最少需要加油 5 次。



把沿途第 2 个加油站和第 3 个加油站之间的距离从 5 改为 8，得到计算结果为 0，表示不能到达终点。