（定稿）汉源现代农业园区项目立项申报材料5（喜欢就下吧）

不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生个全局得最优解。

由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。

提出问题是解决的开始。

为了着手解决遇到的困难，取得最优方案。

我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下个加油站，我们才加次油。

在局部找到个最优的解。

每加次油我们可以看作是个新的起点，用相同的递归方法进行下去。

最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。

贪心算法正确性证明贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过系列局部最优的选择，即贪心选择来达到。

对于个具体的问题，要确定它是否具有贪心性质，我们必须证明每步所作的贪心选择最终导致问题的个整体最优解。

该题设在加满油后可行驶的千米这段路程上任取两个加油站，且距离始点比距离始点近，则若在加油不能到达终点那么在加油定不能到达终点，因为，即在点加油可行驶的路程比在点加油可行驶的路程要长千米，所以只要终点不在之间且在的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远些的加油站去加油，因此，加油次数最少满足贪心选择性质。

最优子结构性质当个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。

由于是这段路程加油次数最少的个满足贪心选择性质的最优解，则易知若在第个加油站加油时则是从到这段路程上加油次数最少且这段路程上的加油站个数为的最优解，即每次汽车中剩下的油不能在行驶到下个加油站时我们才在这个加油站加次油，每个过程从加油开始行驶到再次加油满足贪心且每次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。

贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为。

第章最优合并问题问题的提出给定个排好序的序列，用路合并算法将这个序列合并成个序列。

假设所采用的路合并算法合并个长度分别为和的序列需要次比较。

试设计个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。

为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

原理分析这个程序比较适合用堆，最优用最小堆，最差用最大堆以最优合并为例使用各序列的长度建堆两个最小的元素出堆，计算这两序列合并需要的比较次数，该次数入堆重复，直到堆只剩下个元素最后剩下的元素即为题目的解。

算法时间复杂度分析复杂度为，排序后，最小的两个序列是前两个，计算最小的两个序列的合并次数后，该次数不定是新的最小的两个序列之，所以在下次合并前，必需使数组仍旧有序，让最小的两个序列在数组的最前面，为使数组重新有序，可以使用类似插入排序的插入过程，将新得到的数字直接插入到数组，这样不需要额外的储存空间，但总复杂度是，考虑到需要计算最优与最差，实际上也必须需要额外的的空间来保存排序后的结果，如果将排序后的数组按照顺序作成个链表，那么链表的最前的两节点就是最小的两序列，计算合并次数，删除该两节点，将新得到的次数插入到链表，注意到，后面需要插入的数字肯定比前面插入的数字大，所以从上次插入的位置之后查找新的插入位置，这样插入数字的总的时间复杂度是的，总的时间复杂度仍旧是，并使用了额外的的空间。

第章会场安排问题问题的提出假设要在足够多的会场里安排批活动，并希望使用尽可能少的会场。

设计个有效的贪心算法进行安排。

这个问题实际上是著名的图着色问题。

若将每个活动作为图的个顶点，不相容活动间用边相连。

使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。

数据输入由文件给出输入数据。

第行有个正整数，表示有个待安排的活动。

接下来的行中，每行有个正整数，分别表示个待安排的活动开始时间和结束时间。

时间以点开始的分钟计。

结果输出将编程计算出的最少会场数输出到文件。

输入文件示例输出文件示例编码分析根据会场安排问题的定义，首先将问题简化为找出两个活动，若和满足或，则称这两个活动相容，即问题转化为要求找出最多相容会场集合。

问题简化为对相容会场的寻找，下面用贪心方法分析过程，根据题意，选取种量度标准，然后按量度标准对个输入排序，按顺序次输入个量。

如果这个输入和当前已构成在这种量度意义下的部分最优解加在起不能产生个可行解，则不把此输入加到这部分解中，这种能够得到种量度意义下的最优解的分级处理方法就是贪心方法。

那么问题转化为对度量标准的寻找，判断各个数据是否可以包含在解向量中去，然后根据目标函数来选择最优解。

贪心算法将所有活动按结束时间排序，得到活动集合先将选入结果集合中，即依次扫描每个活动如果的开始时间晚于最后个选入的活动的结束时间，则将选入中，否则放弃。

最优解证明若，是按结束时间排序的活动集合，则具有最早的结束时间，设存在个最优安排不包含，并以开始，则易见∪也是最优的活动安排依此类推，即可推出上述活动都为中的不相容最优活动。

俗话所的好的纸上得来终觉浅，绝知此事要躬行，那么让我们举个例子来进步清晰化问题下面表格有个活动，并给出各个活动的开始时间与结束时间，那么请用上述贪心解法分析并求解最优会场数目。

如表所示。

表会场活动安排表活动开始时间结束时间根据贪心策略现将个活动的结束时间排序为解说方便上表格已经排好排序可用快速排序。

毋庸置疑将先分配入会场集合，然后按照顺序找出下个活动，使得其开始时间小于的结束时间即满足时间不冲突，如图易知为，再将分配给，以后每步骤都重复如的选择。

经过第轮的筛选可知会场集合中包含，。

此时已经没有活动在相容于会场中，那么再继续对进行同样的选取，同理，。

那么得出总的会场数目。

算法时间复杂度分析算法的时间复杂度为。

第章贪心算法的实现语言概述据统计，目前世界上支持面向对象程序设计的语言已近百种，除了大多数是供研究用的非商业软件外，具有强大竞争力语言也很多，其中类是以和语言为代表的新的面向对象语言。

它以其号或信息。

而本游戏系统采用的是完整版的子集，它完全集成在的集成开发环境中。

自身仅占用字节左右的程序存储空间。

仅支持时间片轮转任务切换和使用信号进行任务切换。

不支持抢先式的任务切换，不包括消息历程，没有存储器池分配程序。

虽然比较简陋，但它还是具备了些实时操作系统的基本要素，又因为它完全集成在的集成开发环境中，可以使用户把更多的精力关注在应用本身而无需考虑复杂的底层驱动，而且整个应用软件系统结构清晰，维护方便，可节省大量的时间和人力。

当程序比较复杂时，它的优点就体现得更明显。

完全可以充当我们进入实时操作系统世界的领路者，更为重要的是，它是免费的。

无论如何，仍然是在位单片机中应用操作系统的首选。

的内核分析该小节只介绍本设计中用到系统的相关知识与配置方法。

读者若想更全面了解多任务实时操作系统，请阅读的帮助文件或其它相关文件。

程序的编写方法若要使用的内核，只需包含文件即可。

所有的运行时库常量都在这个头文件中定义。

可以采用以下方式包含它当使用时，要为每个任务建立独立的任务函数。

同时，任务必须是用声明的函数，返回值和参数都必须是类型的，黄忠南基于单片机的俄罗斯方块游戏设计程序不需要用户自已定义函数，取而代之的是，从任务开始执行。

在典型的应用中，任务简单的建立所有其他的任务。

系统调用函数简介内核完全集成在编译器中，以系统函数调用的方式运行，因此可以很容易地使用语言编写和编译个多任务程序，并嵌入到实际应用系统中，内核提供多组函数供应用程序引用。

的任务状态的用户任务具有以下几个状态任务处于运行中，同时间只有个抢占任务可以处于状态。

任务正在等待运行，在当前运行的任务时间片完成之后，运行下个处于状态的任务。

任务由于时间片用完而处于状态，并等待再次运行。

该状态与状态相似，但由于是内部操作过程使个循环任务被切换而被冠以标记。

如图所示为任务状态转换图。

图任务状态转换图的同步机制为了能保证任务在执行次序上的协调，必须采用同步机制。

内核用以下事件进行任务间的通信和同步。

用于任务之间通信的位，可以用系统函数置位或清除。

如果个任务调用函数等待而未置位，则该任务被挂起直到置位，才返回到状态，并可被再次执行。

由函数开始的时间延时，其持续时间可由定时节拍数确定。

带有值调用函数的任务将被挂起，直到延时结束，才返回到状态，并可被再次执行。

由函数开始的时间间隔，其间隔时间可由定时节拍数确定。

带信号或超时到来等待信号或超时时间片结束时间片到来贺州学院本科生毕业论文设计有值调用函数的任务将被挂起，直到间隔时间结束，然后返回到状态，并可被再次执行。

与不同的是，任务的节拍计数器不复位。

的任务切换方式任务切换是提供的基本服务。

是基于时间片调度算法的操作系统，它支持的是非抢占式的任务切换。

所以在个任务被执行时不能对其进行中断，除非该任务主动放弃的资源，中断才可以打断当前的任务，中断完成后把的控制权再交还该被中断的任务。

任务切换的流程如图所示。

图任务切换流程图寄存器组切换当前任务时间片到标志置位查找下个状态的任务们个固定的递推式，而是在每个阶段都看上去是个最优的决策在定的标准下。

不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生个全局得最优解。

由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。

提出问题是解决的开始。

为了着手解决遇到的困难，取得最优方案。

我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下个加油站，我们才加次油。

在局部找到个最优的解。

每加次油我们可以看作是个新的起点，用相同的递归方法进行下去。

最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。

贪心算法正确性证明贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过系列局部最优的选择，即贪心选择来达到。

对于个具体的问题，要确定它是否具有贪心性质，我们必须证明每步所作的贪心选择最终导致问题的个整体最优解。

该题设在加满油后可行驶的千米这段路程上任取两个加油站，且距离始点比距离始点近，则若在加油不能到达终点那么在加油定不能到达终点，因为，即在点加油可行驶的路程比在点加油可行驶的路程要长千米，所以只要终点不在之间且在的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远些的加油站去加油，因此，加油次数最少满足贪心选择性质。

最优子结构性质当个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。

由于是这段路程加油次数最少的个满足贪心选择性质的最优解，则易知若在第个加油站加油时则是从到这段路程上加油次数最少且这段路程上的加油站个数为的最优解，即每次汽车中剩下的油不能在行驶到下个加油站时我们才在这个加油站加次油，每个过程从加油开始行驶到再次加油满足贪心且每次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。

贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为。

第章最优合并问题问题的提出给定个排好序的序列，用路合并算法将这个序列合并成个序列。

假设所采用的路合并算法合并个长度分别为和的序列需要次比较。

试设计个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。

为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

原理分析这个程序比较适合用堆，最优用最小堆，最差用最大堆以最优合并为例使用各序列的长度建堆两个最小的元素出堆，计算这两序列合并需要的比较次数，该次数入堆重复，直到堆只剩下个元素最后剩下的元素即为题目的解。

算法时间复杂度分析复杂度为，排序后，最小的两个序列是前两个，计算最小的两个序列的合并次数后，该次数不定是新的最小的两个序列之，所以在下次合并前，必需使数组仍旧有序，让最小的两个序列在数组的最前面，为使数组重新有序，可以使用类似插入排序的插入过程，将新得到的数字直接插入到数组，这样不需要额外的储存空间，但总复杂度是，考虑到需要计算