tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

贪心算法C语言


(一) 问题描述 一辆汽车加满油后可以行驶 N 千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计 一个有效的算法,指出应在那些加油站停靠加油。 给出 N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个 有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。 (二) 问题分析(前提行驶前车里加满油) 对于这个问题我们有

以下几种情况:设加油次数为 k,每个加油站间距离为 a[i];i=0,1,2,3……n 1.始点到终点的距离小于N,则加油次数 k=0; 2.始点到终点的距离大于 N, A B C D 加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少 k=n; 加油站间的距离相等,即a[i]=a[j]=L>N,则不可能到达终点; 加油站间的距离相等,即a[i]=a[j]=L<N,则加油次数 k=n/N(n%N==0)或 k=[n/N]+1(n%N!=0); 加油站间的距离不相等,即a[i]!=a[j],则加油次数 k 通过以下算法求解。

(三)算法描述 贪心算法的基本思想 该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定 是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程 看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定 的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为 更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得最优解。 贪心算法的适用的问题 贪心算法适用的问题必须满足两个属性: (1) 贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前做出

的选择,但不能依赖于以后的选择。 (2) 最优子结构:问题的整体最优解包含着它的子问题的最优解。

贪心算法的基本步骤 (1) 分解:将原问题分解为若干相互独立的阶段。

(2) (3)

解决:对于每一个阶段求局部的最优解。 合并:将各个阶段的解合并为原问题的解。

[问题分析] 由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到 达终点又可以使我们加油次数最少。 提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不 加油,即除非我们油箱里的油不足以开到下一个加油站,我们才加一次油。在局部找到一个最优的解。却 每加一次油我们可以看作是一个新的起点,用相同的递归方法进行下去。最终将各个阶段的最优解合并为 原问题的解得到我们原问题的求解。 加油站贪心算法设计(C): include<math.h> include<studio.h> int add(int b[ ],int m,int n) { //求一个从 m 到 n 的数列的和 int sb; for(int i=m;i<n;i++) sb+=b[i]; return sb; } int Tanxin(int a[n], int N) { int b[n]; //若在 a[i]加油站加油,则 b[i]为 1,否则为 0 int m=0; if(a[i]>N) return ERROR; if(add(a[i], 0, n)<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) { //如果每相邻的两个加油站间的距离相等且都小于 N if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) { b[k]=1; m+=k; //如果某相邻的两个加油站间的距离大于 N,则不能到达终点 //a[n]表示加油站的个数,N 为加满油能行驶的最远距离

} 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("%d",a); scanf("/n"); scanf("/d",&N); Tanxin(a[ ],0,n); } 贪心算法正确性证明: 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。 对于一个具体的问题,要确定它是否具有贪心性质,我们必须证明每一步所作的贪心选择最终导致问题的 一个整体最优解。该题设在加满油后可行驶的 N 千米这段路程上任取两个加油站A、B,且A距离始点比 B距离始点近,则若在B加油不能到达终点那么在A加油一定不能到达终点,因为 m+N<n+N,即在 B 点加 油可行驶的路程比在 A 点加油可行驶的路程要长 n-m 千米, 所以只要终点不在 B、 C 之间且在 C 的右边的话, 根据贪心选择,为使加油次数最少就会选择距离加满油得点远一些的加油站去加油,因此,加油次数最少 满足贪心选择性质。


推荐相关:

贪心算法C语言

贪心算法C语言_学科竞赛_高中教育_教育专区。(一) 问题描述 一辆汽车加满油后可以行驶 N 千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计 一个...


贪婪法C语言例子解析

贪婪法C语言例子解析_电脑基础知识_IT/计算机_专业资料。贪婪法 贪婪法是一种不...按贪婪算法,应找 1 个 11 单 位面值的硬币和 4 个 1 单位面值的硬币, ...


贪心算法求解背包问题C语言描述

贪心算法求解背包问题C语言描述_工学_高等教育_教育专区。用C语言描述的贪心算法求解背包问题的程序,已调试过,能正确执行。贪心算法求解背包问题: 贪心算法求解背包问...


EDF模拟实现-C语言-贪心算法

EDF模拟实现-C语言-贪心算法_计算机软件及应用_IT/计算机_专业资料。算法实验,不足之处请指教啊!工程包含多个.c 文件。建个工程就可以了。 代码在下面: //EDF...


贪心法-C语言-霍夫曼编码

贪心法-C语言-霍夫曼编码_计算机软件及应用_IT/计算机_专业资料。贪心法-C语言-霍夫曼编码 实验报告 计算机算法设计与分析贪心算法 霍夫曼编码学 姓班学院名级号...


贪心法解决活动安排问题

[2] 吴伟明.严蔚敏.数据结构/c语言版.北京:清华大学出版社,2007; 附录: 附录:贪心算法的实现具体程序如下: // 贪心算法实现代码 n 为活动个数 s 为活动...


贪心算法多机调度问题C参考程序

java实现贪心算法中的多... 5页 2下载券 贪心法 多机调度问题 暂无评价 3页...贪​心​算​法​多​机​调​度​问​题​C​参​考...


贪心算法解决会场安排问题、多处最优服务次序问题(含源代码)

回溯法之N皇后问题(C语言... 2页 免费贪​心​算​法​解​决​...2. 五.心得体会 通过本次实验,我了解了贪心算法的性质与解题思路。会场安排...


C语言经典四种算法详解

C语言经典四种算法详解_工学_高等教育_教育专区。一 分而治之算法 分而治之方法...备注: 备注: 贪心算法当然也有正确的时候。 求最小生成树的 Prim 算法和 ...


c语言算法--贪婪算法---01背包问题

c语言算法--贪婪算法---01背包问题_IT/计算机_专业资料。c语言算法--贪婪算法---01背包问题,很不错的一本书c 语言算法--贪婪算法---0/1 背包问题在 0 /...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com