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

算法分析与设计
课 程 设 计 报 告
课程名称 算 法 分 析 与 设 计
实验学期 2013 年至 2014 年 第 1 学期
所在学院 理学院 年级 2011
专业班级 信息与计算科学3班
学生姓名 郑松辉 学号 201130760334 自评成绩 96 教师评成绩
指导教师 赵 峰
《算法分析与设计》课程设计报告
设计题目
贪心算法解决活动安排问题
设计时间
年　月　日
设计性质
应用性　√设计性　√综合性
设计成绩
教师评阅：
□ 设计目的明确；　□ 操作步骤正确；　□ 设计文稿（表格、程序、数据库、网页）符合要求；
□ 设计结果正确；　□ 设计分析总结全面；　□ 设计报告规范；
课程设计答辩情况记录：
□ 思路清晰；语言表达准确，概念清楚。
□ 准备工作充分, 具备必要的报告资料；报告在规定的时间内完成。
□ 回答问题有理论依据，基本概念清楚; 主要问题回答简明准确；　
□ 对前人工作有改进或突破，或有独特见解。
　　　　　　　　　　　　　　　　　　　　　　　　　评阅教师签名：
目 录
1课程实验概述 4
问题概述 4
目的与任务 4
开发环境 4
参考资料 4
任务完成的一般过程 4
软件配置 5
2 个人的构思与创意 5
构思 5
特色 5
3 用贪心算法解决活动安排的问题的实验及其结果分析 5
贪心算法简介 5
贪心算法思路 6
贪心算法实现 6
算法结果 7
实验结果 8
结果分析 8
算法分析 9
关键代码及解释 9
算法流程图 10
时间复杂度分析 11
4 实验个人小结 11
11
个人经验总结 11
收获 11
不足 12
1课程实验概述
问题概述
设有n个活动的集合E={1,2，……，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交，则称活动i与活动j是相容的。也就是说，当si>=fj或者sj>=fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
目的与任务
利用贪心算法的性质，通过选择适当的贪心策略的贪心算法解决活动安排问题，且能求得活动安排的最优解。
开发环境
平台：Windows 7； 编程语言：C语言；
参考资料
[1] 算法设计与分析（第二版） 王晓东 编著 清华大学出版社 2011
[2] 标准C语言基础教程（第四版） [美]Gary 电子工业出版社 2011
任务完成的一般过程
完成过程如下图1所示：
图1 任务完成的一般过程
软件配置
编程工具：C-
2 个人的构思与创意
构思
此次课程设计的构思过程的核心是：贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。因此，这个方向非常明确，就是用贪心算法解决活动安排问题。
首先，贪心算法最大的难度在于选择贪心策略，只要选择正确的贪心策略就能通过贪心算法求得最优解，对于活动安排，以选择结束时间最早的活动为贪心策略是可以得到最优解的。
其次，既然是按照一定的顺序来选择活动，那么必将先要对活动按结束时间递增进行排序，因为排序后，编写贪心算法程序会变得十分简洁。
最后，在对所有活动进行选择完毕后，要程序中显示选择结果，以确实是否正确。
特色
本次编程，个人觉得最大的特色就是把贪心选择算法程序和结果显示程序分离开成单独的模块，这样会使得贪心选择算法变得更加简洁易懂，便于浏览阅读。
其次，在界面设计上，为了让前后衔接的更加美观，也设置的两个表格，以便显示输入是的活动表和排序后的活动表，这样可以很直观的看出此次设计的运行过程。
再者，我是通过设置全局变量，一次赋值或者排序后都可以在