如果选择了活动i，则它在时间区间[si,fi]内占用资源。
若区间[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电子工业出版社2011.
1.5任务完成的一般过程
完成过程如下图1所示：
图1任务完成的一般过程
1.6软件配置....................
2个人的构思与创意
2.1构思
此次课程设计的构思过程的核心是：
贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。
因此，这个方向非常明确，就是用贪心算法解决活动安排问题。
首先，贪心算法最大的难度在于选择贪心策略，只要选择正确的贪心策略就能通过贪心算法求得最优解，对于活动安排，以选择结束时间最早的活动为贪心策略是可以得到最优解的。
其次，既然是按照一定的顺序来选择活动，那么必将先要对活动按结束时间递增进行排序，因为排序后，编写贪心算法程序会变得十分简洁。
最后，在对所有活动进行选择完毕后，要程序中显示选择结果，以确实是否正确。
2.2特色
本次编程，个人觉得最大的特色就是把贪心选择算法程序和结果显示程序分离开成单独的模块，这样会使得贪心选择算法变得更加简洁易懂，便于浏览阅读。
其次，在界面设计上，为了让前后衔接的更加美观，也设置的两个表格，以便显示输入是的活动表和排序后的活动表，这样可以很直观的看出此次设计的运行过程。
再者，我是通过设置全局变量，一次赋值或者排序后都可以在所有函数中调用，这也使得个模块的连接更加简单，没有复杂的地址调用，是代码更具易读性。
3用贪心算法解决活动安排的问题的实验及其结果分析
3.1贪心算法简介
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
3.2贪心算法思路
活动安排运用贪心算法的思路为，尽可能多的使更多的事件得到资源的安排。
按这种方法选择相容活动为未安排活动留下尽可能多的时间。
也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。
3.3贪心算法实现
贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。
这个结论可以用数学归纳法证明。
事实上，设E=｛1，2，...，n｝为所给的活动集合。
由于E中活动按结束时间的非减序列排列，故活动1具有最早的完成时间。
首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1。
设
是所给的活动安排问题的一个最优解，且A中活动也按结束时间非减序排序，A中的第一个活动是活动k。
若k=1，则A就是以贪心选择开始的最优解；若k>1，则设
。
由于f1
fk，且A中活动是相容的。
又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。
由此可见，此贪心策略能得到最优解。
由于贪心算法解决安排问题要考虑么个活动的结束时间，所以先将活动按照结束时间长短进行递增排序。
本贪心算法在处理非减序排列活动队列时可以达到极高的效率。
例：
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
活动1
活动2
活动3
活动4
活动5
活动6
活动7
活动8
活动9
活动10
活动11
起始
1
3
0
5
3
5
6
8
8
2
12
结束
4
5
6
7
8
9
10
11
12
13
14
表1已排序活动安排
贪心算法的计算过程如下图所示。
图中每行相应于算法的一次迭代。
阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
图2贪心算法的计算过程图
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。
3.4算法结果
若所需安排的活动为：
活动1
活动2
活动3
活动4
活动5
活动6
活动7
活动8
活动9
活动10
活动11
起始
3
1
0
5
3
5
6
8
8
12
2
结束
5
4
6
8
7
9
10
11
12
14
13
表2活动安排
3.4.1实验结果
图3运行结果
3.4.2结果分析
首先对以上数据以结束时间递增顺序进行排序得到以下队列：
活动2
活动1
活动3
活动5
活动4
活动6
活动7
活动8
活动9
活动11
活动10
起始时间
1
3
0
3
5
5
6
8
8
2
12
结束时间
4
5
6
7
8
9
10
11
12
13
14
表3对数据以结束时间递增顺序进行排序得到的队列
然后按照贪心算法取结束时间提前的活动以为后续活动提供更多时间，同时在保证选择的活动的结束时间提前还要保证该活动与前一个活动相容。
依次选择的活动为2、4、8、10。
3.5算法分析
3.5.1关键代码及解释
voidgreedySelect（intn）//活动的贪心选择
{a[num[1]]=true;
intj=1;
for（inti=2;i<=n;i++）
if（s[i]>=f[j]）
{a[num[i]]=true;j=i;}
else
a[num[i]]=false;}
这是整个贪心算法的核心，一个for循环，根据已经选择的贪心策略，对活动进行选择，其中布尔型数组a[]用与保存活动是否被选择，若被选择则保存为true，否则保存为false。
voidgreedySort（intn）//将活动按结束时间递增排序
{inti,j,m;
for（i=1;i<=n;i++）
for（j=i;j<=n-1;j++）
if（f[j]>f[j+1]）
{m=f[j];
f[j]=f[j+1];
f[j+1]=m;
m=s[j];
s[j]=s[j+1];
s[j+1]=m;
m=num[j];
num[j]=num[j+1];
num[j+1]=m;}
}
这是一个排序函数，这是也算法的主要部分，因为此贪心算法的贪心策略为：
选择结束时间最早的活动；所以为了让核心算法更简便更容易进行，首先对活动按结束时间递增排序。
主要是通过冒泡排序。
3.5.2算法流程图
核心算法流程图如图4所示：
图4算法流程图
3.5.3时间复杂度分析
贪心算法的效率极高，当输入的活动已按结束时间的非减序排列，算法只需O（n）的时间安排n个活动，使最多的活动能相容地使用公共资源。
如果所给出的活动未按非减序排列，只需要对队列进行递增排序，最简只要用O（nlogn）的时间。
4实验个人小结
4.1总体实验分析总结
可以看出，在解决一个活动安排的问题是，只需要两个步骤。
一、对活动队列进行排序，二、用贪心算法对队列进行安排。
运用贪心算法只要很少的时间便能实现地问题的解决。
贪心算法贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法r却总能求得的整体最优解。
所以对于某些问题贪心算法可以给出极漂亮的解决。
4.2个人经验总结
4.2.1收获
通过对活动安排问题的分析和最终解决这个问题，我确实学到了不少东西。
在这个过程中，我了解到贪心算法贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法r却总能求得的整体最优解。
所以对于某些问题贪心算法可以给出极漂亮的解决。
不仅如此，我还知道，不同的贪心选择策略会导致不同的结果，而结果可能是最优也可能不是最优的，使我进一步了解了贪心算法；
这次课程设计更多的收获是：
C语言是计算机程序语言的基础语言，内容是比较简单，但它的实践操作还是比较强的，平时上机课较少，空闲时间又没想过去编程，通过这次课程设计，每一步的实践操作，提高了自我动手编程的能力，将在课本中许多学到的知识和很多想法都在编程过程中一一实践。
4.2.2不足
因为这次是一个人做一个题目，所以在选题方面也会偏向简单一点的，这对于课程设计锻炼个人编程能力的效果大打折扣。
其次，因为是单人编程，虽然不用和别人讨论，有想法就写上去，但是少了讨论，就很难找到会比自己想法更好更简单的方法，也不能锻炼到自己的团队合作能力，这对于以后参加较大型项目开发所需的团队合作能力锻炼有一定的不好，所以，个人觉得，不管简单还是难，如果可以，团队运行是最好的。
个人觉得，这个课程设计最不好的地方就是缺少对照的贪心策略。
本来是有想到要选择其他贪心策略（比如以选择最早开始的活动的策略、以选择活动持续时间最短的策略等等）进行比较实验的，但是因为自己怕麻烦，所以没有这样做，这是非常不好的，这使得这个课程设计显得比较平凡，特色不大。
我觉得我对C语言的掌握还是不够熟悉的，因为在这次编程中没能用到比较高级的数据结构（比如栈，队列等等），只是用C语言的一些较为简单的基础语法等等再结合算法的内容。
如果使用了数据结构的话，就会让这个课程设计更具特色，也显得高级一点。
升级会员 