汽车加油问题实验报告
更新时间:2023-12-30 16:16:01 阅读量: 教育文库 文档下载
一、实验名称:
用贪心算法解决汽车加油次数最少问题。
二、实验目的:
一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。
若要使沿途加油次数最少,设计一个有效算法,对于给定的n和k个加油站位置,指出应在哪些加油站停靠加油才能使加油次数最少。输入数据中,第一行有2个正整数,分别表示汽车加满油后可行驶n千米,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。输出为最少的加油次数,如果无法到达目的地,则输出“No Solution”。
实验提示:
把两加油站的距离放在数组中,a[1..k]表示从起始位置开始跑,经过k个加油站,a[i]表示第i-1个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油,否则要加油。
输入数据示例 7 7
1 2 3 4 5 1 6 6 输出数据 4
。
三、使用的策略: 贪心算法、回溯算法等。
四、实验内容:
(一) 问题描述
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。
给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。
(二) 问题分析(前提行驶前车里加满油) 对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3??n
1.始点到终点的距离小于N,则加油次数k=0; 2.始点到终点的距离大于N,
A 加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n; B 加油站间的距离相等,即a[i]=a[j]=L>N,则不可能到达终点;
C 加油站间的距离相等,即a[i]=a[j]=L D 加油站间的距离不相等,即a[i]!=a[j],则加油次数k通过以下算法求解。 (三)算法描述 1.贪心算法解决方案 ? 贪心算法的基本思想 该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得最优解。 ? 贪心算法的适用的问题 贪心算法适用的问题必须满足两个属性: (1) 贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的 选择可以依赖以前做出的选择,但不能依赖于以后的选择。 (2) 最优子结构:问题的整体最优解包含着它的子问题的最优解。 ? 贪心算法的基本步骤 (1) 分解:将原问题分解为若干相互独立的阶段。 (2) 解决:对于每一个阶段求局部的最优解。 (3) 合并:将各个阶段的解合并为原问题的解。 [问题分析] 由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。 提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油,即除非我们油箱里的油不足以开到下一个加油站,我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点,用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。 加油站贪心算法设计(C): include int add(int b[ ],int m,int n) { //求一个从m到n的数列的和 int sb; for(int i=m;i int Tanxin(int a[n], int N) //a[n]表示加油站的个数,N为加满油能行驶的最远距离 { int b[n]; //若在a[i]加油站加油,则b[i]为1,否则为0 int m=0; if(a[i]>N) return ERROR; //如果某相邻的两个加油站间的距离大于N,则不能到达终点 if(add(a[i], 0, n) { //如果这段距离小于N,则不需要加油 b[i]=0; return add(b[i],0,n); } if(a[i]==a[j]&&a[i]==N) { //如果每相邻的两个加油站间的距离都是N,则每个加油站都需要加油 b[i]=1; return add(b[i],0,n); } if(a[i]==a[j]&&a[i] { //如果每相邻的两个加油站间的距离相等且都小于N if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) { b[k]=1; m+=k; } return add(b[i],0,n); } if(a[i]!=a[j]) { //如果每相邻的两个加油站间的距离不相等且都小于N if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) { b[k]=1; m+=k; } return add(b[i],0,n); } viod main( ) { int a[ ]; scanf(\ scanf(\ scanf(\ Tanxin(a[ ],0,n); } 贪心算法正确性证明: ? 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。对于一个具体的问题,要确定它是否具有贪心性质,我们 必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站A、B,且A距离始点比B距离始点近,则若在B加油不能到达终点那么在A加油一定不能到达终点,如图: 由图知:因为m+N 当一个问题大的最优解包含着它的子问题的最优解时,称该问题具有最优子结构性质。由于(b[1],b[2],??b[n])是这段路程加油次数最少的一个满足贪心选择性质的最优解,则易知若在第一个加油站加油时,b[1]=1,则(b[2],b[3],??b[n])是从 a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为(a[2],a[3],??a[n])的最优解,即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油,每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件,每个过程都是相同且独立,也就是说加油次数最少具有最优子结构性质。 贪心算法时间复杂度分析 由于若想知道该在哪个加油站加油就必须遍历所有的加油站,且不需要重复遍历,所以时间复杂度为O(n)。 五、实验心得: 在贪心算法中,每次做出的选择仅在当前的状态下做出的最好的选择,即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。不是每个问题用贪心算法都可以一定得到最优解,除非该问题具有贪心选择性质(所求问题的整体最优解可以通过一系列局部最优的选择而得到)和最优子结构性质。 通过实验对贪心算法和回溯算法以及动态规划算法有了更深一步的理解,知道了它们适合解决哪类的问题,锻炼和提高了我们分析问题解决问题的能力,同时让我们更体会到团结一致协作的重要性。
正在阅读:
汽车加油问题实验报告12-30
2020年乡镇精神文明建设工作总结08-31
关于RDW在缺铁性贫血(IDA)中的鉴别诊断的外文翻译08-06
南大网院 大学语文 三届课程考试试卷答案(95分以上卷)02-02
数学必修1-必修4单元测试题精品,共8003-08
PB 编码规范10-22
县农业农村局上半年农业综合执法工作计划07-30
企业执行力存在问题及对策研究09-11
净化水处理设计方案02-29
数学建模思想在高等数学教学中的渗透12-08
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 加油
- 实验
- 报告
- 汽车
- 问题
- 土石方工程常见问题
- Does Wechat change our life? Is it good or bad?
- 外国法制史简答题
- 端午节的作文600字
- solidworks批量处理文件工具
- 防洪评价报告编制导则
- 语文七年级(上)第一单元测试卷(A卷)
- 合作框架协议(增资扩股)
- 医疗机构不良执业行为记分一览表 - 图文
- 会计制度设计简答 idoc
- 九年级物理全册 18.3测量小灯泡的电功率教案(新版)新人教版
- 北师大版九年级历史下册第一单元测试题及答案
- 钢结构轴力构件 - 附答案
- 高中物理竞赛教程(超详细) - 第二讲 - 恒定电流
- 数据库系统概论试题及答案4
- 脚手架方案 - 图文
- 太阳能空调
- 建筑工程造价审核论文
- 教案一
- 载波恢复技术(带图)