算法分析与设计课程设计报告

《算法分析与设计课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计课程设计报告课程名称算法分析与设计实验学期2013年至2014年第1学期所在学院理学院年级2011专业班级信息与计算科学3班学生姓名郑松辉学号201130760334自评成绩96教师评成绩指导教师赵峰12《算法分析与设计》课程设计报告设计题目贪心算法解决活动安排问题设计时间年　月　日设计性质应用性　√设计性　√综合性设计成绩教师评阅：□设计目的明确；　□操作步骤正确；　□设计文稿（表格、程序、数据库、网页）符合要求；□设计结果正确；　□设计分析总结全面；　□设计报告规范；课程设计答辩情况记录：□思路清晰；语言表达

2、准确，概念清楚。□准备工作充分,具备必要的报告资料；报告在规定的时间内完成。□回答问题有理论依据，基本概念清楚;主要问题回答简明准确；　□对前人工作有改进或突破，或有独特见解。　　　　　　　　　　　　　　　　　　　　　　　　　评阅教师签名：12目录1课程实验概述41.1问题概述41.2目的与任务41.3开发环境41.4参考资料41.5任务完成的一般过程41.6软件配置52个人的构思与创意52.1构思52.2特色53用贪心算法解决活动安排的问题的实验及其结果分析53.1贪心算法简介53.2贪心算法思路63.3贪心算法实现63.4

3、算法结果73.4.1实验结果83.4.2结果分析83.5算法分析93.5.1关键代码及解释93.5.2算法流程图103.5.3时间复杂度分析114实验个人小结114.1总体实验分析总结114.2个人经验总结114.2.1收获114.2.2不足12121课程实验概述1.1问题概述设有n个活动的集合E={1,2，……，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si

4、i]内占用资源。若区间[si,fi]与区间[sj,fj]不相交，则称活动i与活动j是相容的。也就是说，当si>=fj或者sj>=fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。1.2目的与任务利用贪心算法的性质，通过选择适当的贪心策略的贪心算法解决活动安排问题，且能求得活动安排的最优解。1.3开发环境平台：Windows7；编程语言：C语言；1.4参考资料[1]算法设计与分析（第二版）王晓东编著清华大学出版社2011[2]标准C语言基础教程（第四版）[美]GaryJ.Bronson电子

5、工业出版社20111.5任务完成的一般过程完成过程如下图1所示：图1任务完成的一般过程121.6软件配置编程工具：C-Free5.02个人的构思与创意2.1构思此次课程设计的构思过程的核心是：贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。因此，这个方向非常明确，就是用贪心算法解决活动安排问题。首先，贪心算法最大的难度在于选择贪心策略，只要选择正确的贪心策略就能通过贪心算法求得最优解，对于活动安排，以选择结束时间最早的活动为贪心策略是可以得到最

6、优解的。其次，既然是按照一定的顺序来选择活动，那么必将先要对活动按结束时间递增进行排序，因为排序后，编写贪心算法程序会变得十分简洁。最后，在对所有活动进行选择完毕后，要程序中显示选择结果，以确实是否正确。2.2特色本次编程，个人觉得最大的特色就是把贪心选择算法程序和结果显示程序分离开成单独的模块，这样会使得贪心选择算法变得更加简洁易懂，便于浏览阅读。其次，在界面设计上，为了让前后衔接的更加美观，也设置的两个表格，以便显示输入是的活动表和排序后的活动表，这样可以很直观的看出此次设计的运行过程。再者，我是通过设置全局变量，一次赋值

7、或者排序后都可以在所有函数中调用，这也使得个模块的连接更加简单，没有复杂的地址调用，是代码更具易读性。3用贪心算法解决活动安排的问题的实验及其结果分析3.1贪心算法简介12贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。3.2贪心算法思路活动安排运用贪心算法的思路为，尽可能多的使更多的事件得到资源的安排。按这种方法

8、选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。3.3贪心算法实现贪心