汽车加油问题实验报告
5页1、一、实验名称: 用贪心算法解决汽车加油次数最少问题。 二、实验目的: 一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法,对于给定的n和k个加油站位置,指出应在哪些加油站停靠加油才能使加油次数最少。输入数据中,第一行有2个正整数,分别表示汽车加满油后可行驶n千米,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。输出为最少的加油次数,如果无法到达目的地,则输出“No Solution”。实验提示:把两加油站的距离放在数组中,a1.k表示从起始位置开始跑,经过k个加油站,ai表示第i1个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油,否则要加油。输入数据示例7 71 2 3 4 5 1 6 6输出数据4。 三、使用的策略: 贪心算法、回溯算法等。四、实验内容:(一) 问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。
2、给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。(二) 问题分析(前提行驶前车里加满油)对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为ai;i=0,1,2,3n1.始点到终点的距离小于,则加油次数k=0;2.始点到终点的距离大于N, A 加油站间的距离相等,即i=aj=L=N,则加油次数最少k=n;B 加油站间的距离相等,即i=aj=LN,则不可能到达终点;C 加油站间的距离相等,即i=aj=LN,则加油次数k=n/N(n%N=0)或k=n/N+1(n%N!=0);D 加油站间的距离不相等,即i!=aj,则加油次数k通过以下算法求解。(三)算法描述1.贪心算法解决方案l 贪心算法的基本思想该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的
《汽车加油问题实验报告》由会员m****分享,可在线阅读,更多相关《汽车加油问题实验报告》请在金锄头文库上搜索。
专技天下2018网络效应
浙江温州市生态环境保护行政执法队招考聘用笔试题库含答案解析
幼儿园毕业班老师致辞优秀5篇
荐我的初中生活作文
材料员考试专业基础知识典例考试历年真题汇总含答案参考52
2023年夫妻自愿离婚协议书模板合集(精选文档)
电话营销和销售帮助你获得更多利润
2023年财务年度个人总结(2篇).doc
采购员年终个人总结标准模板(5篇).doc
f低等级村道公路施工总结
2019年科教版五年级科学下教案
空调维护保养三措两案
部编人教版一年级上册数学期中考试必考题
领导工作失职检讨书
春季开学典礼老师发言稿
结婚女方家长讲话稿
工程跨越XX通航河流施工及方案
校园兼职平台营销策划书
2022开学典礼发言稿_128
《巧手制作机器人》教案
2023-02-11 21页
2022-09-02 2页
2023-07-31 8页
2023-07-08 8页
2022-10-04 3页
2023-06-30 14页
2022-07-18 15页
2024-02-12 65页
2023-10-26 8页
2022-09-15 11页