算法分析与设计课程设计-举例1

1、 算法分析与设计课 程 设 计 报 告 课程名称 算 法 分 析 与 设 计 学 院 专业班级 学生姓名 学 号 成 绩 指导教师 算法分析与设计课程设计报告设计题目贪心算法解决活动安排问题设计时间年月日设计性质 应用性设计性综合性设计成绩教师评阅： 设计目的明确； 操作步骤正确； 设计文稿（表格、程序、数据库、网页）符合要求； 设计结果正确； 设计分析总结全面； 设计报告规范；课程设计答辩情况记录： 思路清晰；语言表达准确，概念清楚。 准备工作充分, 具备必要的报告资料；报告在规定的时间内完成。 回答问题有理论依据，基本概念清楚; 主要问题回答简明准确； 对前人工作有改进或突破，或有独特见解

2、。评阅教师签名：目 录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 算法结果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 不足12

3、1课程实验概述 1.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相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。1.2 目的与任务利用贪心算法的性质，通过选择适当的贪心策略的贪心算法解决活动安排问题，且能求得活动

4、安排的最优解。1.3 开发环境平台：Windows 7； 编程语言：C语言；1.4 参考资料1 算法设计与分析（第二版） 王晓东 编著 清华大学出版社 20112 标准C语言基础教程（第四版） 美Gary J.Bronson 电子工业出版社 2011.1.5 任务完成的一般过程完成过程如下图1所示：图1 任务完成的一般过程1.6 软件配置 .2 个人的构思与创意2.1 构思此次课程设计的构思过程的核心是：贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。因此，这个方向非常明确，就是用贪心算法解决活动安排问题。首先

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

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

7、安排。按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。3.3 贪心算法实现贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。事实上，设E=1，2，.，n为所给的活动集合。由于E中活动按结束时间的非减序列排列，故活动1具有最早的完成时间。首先证明活动安排问题有一个最优解以贪

8、心选择开始，即该最优解中包含活动1。设是所给的活动安排问题的一个最优解，且A中活动也按结束时间非减序排序，A中的第一个活动是活动k。若k=1，则A就是以贪心选择开始的最优解；若k>1，则设。由于f1fk，且A中活动是相容的。又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。由此可见，此贪心策略能得到最优解。由于贪心算法解决安排问题要考虑么个活动的结束时间，所以先将活动按照结束时间长短进行递增排序。本贪心算法在处理非减序排列活动队列时可以达到极高的效率。例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：活动1活动2活动3活动4活动5活动6活动7活动8

9、活动9活动10活动11起始130535688212结束4567891011121314 表1 已排序活动安排贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。图2贪心算法的计算过程图若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。3.4 算法结果若所需安排的活动为：活动1活动2活动3活动4活动5活动6活动7活动8活动9活动10活动11起始310535688122结束5468791011121413表2 活动安排3.4.1 实验结果图3

10、运行结果3.4.2 结果分析首先对以上数据以结束时间递增顺序进行排序得到以下队列：活动2活动1活动3活动5活动4活动6活动7活动8活动9活动11活动10起始时间130355688212结束时间4567891011121314表3 对数据以结束时间递增顺序进行排序得到的队列然后按照贪心算法取结束时间提前的活动以为后续活动提供更多时间，同时在保证选择的活动的结束时间提前还要保证该活动与前一个活动相容。依次选择的活动为2、4、8、10。3.5 算法分析3.5.1 关键代码及解释void greedySelect(int n)/活动的贪心选择 anum1=true;int j=1;for(int i=

11、2;i<=n;i+)if(si>=fj)anumi=true; j=i; else anumi=false;这是整个贪心算法的核心，一个for循环，根据已经选择的贪心策略，对活动进行选择，其中布尔型数组a用与保存活动是否被选择，若被选择则保存为true，否则保存为false。void greedySort(int n)/将活动按结束时间递增排序 int i,j,m;for(i=1;i<=n;i+) for(j=i;j<=n-1;j+) if(fj>fj+1) m=fj; fj=fj+1; fj+1=m; m=sj; sj=sj+1; sj+1=m; m=numj;

12、 numj=numj+1; numj+1=m; 这是一个排序函数，这是也算法的主要部分，因为此贪心算法的贪心策略为：选择结束时间最早的活动；所以为了让核心算法更简便更容易进行，首先对活动按结束时间递增排序。主要是通过冒泡排序。3.5.2 算法流程图核心算法流程图如图4所示：图4 算法流程图3.5.3 时间复杂度分析贪心算法的效率极高，当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，只需要对队列进行递增排序，最简只要用O(nlogn)的时间。4 实验个人小结4.1总体实验分析总结可以看出，在解决一个活动安

13、排的问题是，只需要两个步骤。一、对活动队列进行排序，二、用贪心算法对队列进行安排。运用贪心算法只要很少的时间便能实现地问题的解决。贪心算法贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法r却总能求得的整体最优解。所以对于某些问题贪心算法可以给出极漂亮的解决。4.2 个人经验总结4.2.1 收获通过对活动安排问题的分析和最终解决这个问题，我确实学到了不少东西。在这个过程中，我了解到贪心算法贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法r却总能求得的整体最优解。所以对于某些问题贪心算法可以给出极漂亮的解决。不仅如此，我还知道，不同的贪心选择策略会导致不同的结果

14、，而结果可能是最优也可能不是最优的，使我进一步了解了贪心算法；这次课程设计更多的收获是：C语言是计算机程序语言的基础语言，内容是比较简单，但它的实践操作还是比较强的，平时上机课较少，空闲时间又没想过去编程，通过这次课程设计，每一步的实践操作，提高了自我动手编程的能力，将在课本中许多学到的知识和很多想法都在编程过程中一一实践。4.2.2 不足因为这次是一个人做一个题目，所以在选题方面也会偏向简单一点的，这对于课程设计锻炼个人编程能力的效果大打折扣。其次，因为是单人编程，虽然不用和别人讨论，有想法就写上去，但是少了讨论，就很难找到会比自己想法更好更简单的方法，也不能锻炼到自己的团队合作能力，这对于以后参加较大型项目开发所需的团队合作能力锻炼有一定的不好，所以，个人觉得，不管简单还是难，如果可以，团队运行是最好的。个人觉得，这个课程设计最不好的地方就是缺少对照的