汽车加油问题实验报告
3页1、汽车加油问题实验报告一、实验名称:用贪心算法解决汽车加油次数最少问题。二、实验目的:一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法,对于给定的n和k个加油站位置,指出应在哪些加油站停靠加油才能使加油次数最少。输入数据中,第一行有2个正整数,分别表示汽车加满油后可行驶n千米,旦旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-l个加油站之间的距离。第。个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。输出为最少的加油次数,如果无法到达目的地,则输出“NoSolution0o实验提示:把两加油站的距离放在数组中,表示从起始位置开始跑,经过k个加油站,ai表示第il个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油,否则要加油。输入数据示例7712345166输出数据4三、使用的策略:贪心算法、回溯算法等。四、实验内容:(一)问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。给出N,并以数组的形
2、式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。(二)问题分析(前提行驶前车里加满油)对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为ai;i=0,1,2,3?n1.始点到终点的距离小于N,则加油次数k=0;2.始点到终点的距离大于N,A加油站间的距离相等,即ai=aj=L=N,则加油次数最少k=n;B加油站间的距离相等,BPai=aj=LN,则不可能到达终点;C加油站间的距离相等,BPai=aj=LD加油站间的距离不相等,即ai!=aj,则加油次数k通过以下算法求解。(三)算法描述1.贪心算法解决方案?贪心算法的基本思想该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为
《汽车加油问题实验报告》由会员pu****.1分享,可在线阅读,更多相关《汽车加油问题实验报告》请在金锄头文库上搜索。
农行创先争优活动总结5篇
有关小学生写乌龟的作文400字集合五篇
万能考试试卷(含答案)
常规离婚协议书范本
B2B——B2C电子商务网站建设及运营策划书1
产后抑郁患者心理状态分析及心理护理开题报告
办公室卫生管理制度电子版(8篇)
广东:2010广东省行政职业能力测试真题及答案
河南各地区药品可销产品
陕旅版五年级下册单元测试卷
隧道综合智能监控系统解决方案
某住建局综合服务中心可研报告
【施工管理】水电安装施工工艺流程
文明礼仪从我做起演讲稿
经济师个人工作总结(4篇).doc
机场改扩建工程新航站区附属工程施工组织设计
万科物业管理
降低HKM231型往复式隔膜泵故障率QC成果
2023年校园文艺晚会结束语(必备5篇)
机械租赁协议简洁电子版(九篇).doc
2022-09-27 5页
2024-01-11 3页
2024-02-16 88页
2023-07-03 7页
2023-01-31 14页
2023-06-17 15页
2023-04-24 14页
2024-02-27 8页
2022-07-31 3页
2022-12-20 22页