汽车加油问题之贪心算法_第1页
汽车加油问题之贪心算法_第2页
汽车加油问题之贪心算法_第3页
汽车加油问题之贪心算法_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、汽车加油问题的贪婪算法(一)问题描述汽车加满油后可以行驶n公里。旅途中有几个加油站。指出为了减少沿途加油次数，设计了一种有效的算法，并指出那些加油站应该停止加油。n，加油站的数量和相邻距离以数组的形式给出。指出为了减少沿途加油次数，设计了一种有效的算法，并指出这些加油站应该停车加油。要求：算法执行得越快越好。(2)问题分析(前提是开车前给车加油)对于这个问题，我们有以下几种情况：让加油次数为k，每个加油站之间的距离为aI；i=0，1，2，3n1.如果从起点到终点的距离小于n，换料次数k=0；2.从起点到终点的距离大于n，A.如果加油站之间的距离相等，即a I=a j=l=n，加油次数至少为k=

2、n；如果B加油站之间的距离相等，即A I=A J=LN，则不可能到达终点；加油站之间的距离相等，即a I=a j=l包括int add(int b ，int m，int n)/求从m到n的数列的和。int sbfor(int I=m；iN)返回ERROR/如果两个相邻加油站之间的距离大于n，你就不能到达终点如果(加(ai，0，n) N)bk=1；m=k；返回add(bi，0，n)；如果(ai!=aj)/如果相邻两个加油站之间的距离不等且小于n，如果(加(ai，m，k) N加(ai，m，k 1) N)bk=1；m=k；返回add(bi，0，n)；viod main()int a；scanf(“% d”，a)；scanf(/n )；扫描频率(/d ，N)；谭鑫(a ，0，n)；贪婪算法正确性的证明；贪婪选择属性贪婪选择是指问题的全局最优解可以通过一系列局部最优选择来实现，即贪婪选择。对于一个特定的问题，为了确定它是否贪婪，我们必须证明在每一步做出的贪婪选择最终会导致问题的整体最优解。问题是，如果你把两个加油站，A和B，放在加油后可以行驶的N公里处，A比B更

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论