计算机二级C语言实例讲解(10月21日)

计算机二级C语言实例讲解(10月21日)

汽车加油问题之贪心算法

(一) 问题描述

一辆汽车加满油后可以行驶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) 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。

(2) 最优子结构：问题的整体最优解包含着它的子问题的最优解。

贪心算法的基本步骤

(1) 分解：将原问题分解为若干相互独立的阶段。

(2) 解决：对于每一个阶段求局部的最优解。

(3) 合并：将各个阶段的解合并为原问题的解。

​以上就是小编整理的计算机二级C语言实例讲解(10月21日)，想要参加二级考试的同学们都来了解一下吧。想要及时了解考试动态的小伙伴可“ 免费预约短信提醒”届时环球网校会及时为大家推送全国计算机等级考试相关信息提醒。环球网校友情提示：对于想要参加计算机二级考试的小伙伴们，环球网校特地为您准备了计算机二级考试资料，如有需要请点击文章下方“免费下载>>>计算机二级考试资料”下载学习。