算法分析与设计
课程设计报告课程名称算法分析与设计实验学期 2013 年至 2014 年第 1 学期
所在学院理学院年级 2011
专业班级信息与计算科学3班
学生姓名郑松辉学号 201130760334 自评成绩 96 教师评成绩
指导教师赵峰
《算法分析与设计》课程设计报告
目录
1课程实验概述 (4)
1.1 问题概述 (4)
1.2 目的与任务 (4)
1.3 开发环境 (4)
1.4 参考资料 (4)
1.5 任务完成的一般过程 (4)
1.6 软件配置 (5)
2 个人的构思与创意 (5)
2.1 构思 (5)
2.2 特色 (5)
3 用贪心算法解决活动安排的问题的实验及其结果分析 (6)
3.1 贪心算法简介 (6)
3.2 贪心算法思路 (6)
3.3 贪心算法实现 (6)
3.4 算法结果 (8)
3.4.1 实验结果 (8)
3.4.2 结果分析 (9)
3.5 算法分析 (9)
3.5.1 关键代码及解释 (9)
3.5.2 算法流程图 (11)
3.5.3 时间复杂度分析 (11)
4 实验个人小结 (12)
4.1总体实验分析总结 (12)
4.2 个人经验总结 (12)
4.2.1 收获 (12)
4.2.2 不足 (12)
1课程实验概述
1.1 问题概述
设有n个活动的集合E={1,2，……，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i 都有一个要求使用该资源的起始时间si和一个结束时间fi，且si
1.2 目的与任务
利用贪心算法的性质，通过选择适当的贪心策略的贪心算法解决活动安排问题，且能求得活动安排的最优解。
1.3 开发环境
平台：Windows 7；编程语言：C语言；
1.4 参考资料
[1] 算法设计与分析（第二版）王晓东编著清华大学出版社 2011
[2] 标准C语言基础教程（第四版） [美]Gary J.Bronson 电子工业出版社 2011 1.5 任务完成的一般过程
完成过程如下图1所示：
图1 任务完成的一般过程
1.6 软件配置
编程工具：C-Free5.0
2 个人的构思与创意
2.1 构思
此次课程设计的构思过程的核心是：贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。因此，这个方向非常明确，就是用贪心算法解决活动安排问题。
首先，贪心算法最大的难度在于选择贪心策略，只要选择正确的贪心策略就能通过贪心算法求得最优解，对于活动安排，以选择结束时间最早的活动为贪心策略是可以得到最优解的。
其次，既然是按照一定的顺序来选择活动，那么必将先要对活动按结束时间递增进行排序，因为排序后，编写贪心算法程序会变得十分简洁。
最后，在对所有活动进行选择完毕后，要程序中显示选择结果，以确实是否正确。
2.2 特色
本次编程，个人觉得最大的特色就是把贪心选择算法程序和结果显示程序分
离开成单独的模块，这样会使得贪心选择算法变得更加简洁易懂，便于浏览阅读。
其次，在界面设计上，为了让前后衔接的更加美观，也设置的两个表格，以便显示输入是的活动表和排序后的活动表，这样可以很直观的看出此次设计的运行过程。
再者，我是通过设置全局变量，一次赋值或者排序后都可以在所有函数中调用，这也使得个模块的连接更加简单，没有复杂的地址调用，是代码更具易读性。
3 用贪心算法解决活动安排的问题的实验及其结果分析
3.1 贪心算法简介
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
3.2 贪心算法思路
活动安排运用贪心算法的思路为，尽可能多的使更多的事件得到资源的安排。按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。
3.3 贪心算法实现
贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。事实上，设E=｛1，2，...，n｝为所给的活动集合。由于E中活动按结束时间的非减序列排列，故活动1具有最早的完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动A?是所给的活动安排问题的一个最优解，且A中活动也按结束时间非1。设E
减序排序，A中的第一个活动是活动k。若k=1，则A就是以贪心选择开始的最优解；若k>1，则设}1{
A
=k
B。由于f1≤fk，且A中活动是相容的。又由
{?
}
-
于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。由此可见，此贪心策略能得到最优解。
由于贪心算法解决安排问题要考虑么个活动的结束时间，所以先将活动按照结束时间长短进行递增排序。本贪心算法在处理非减序排列活动队列时可以达到极高的效率。
例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
表1 已排序活动安排
贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
图2贪心算法的计算过程图
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。
3.4 算法结果
若所需安排的活动为：
3.4.1 实验结果
图3 运行结果
3.4.2 结果分析
首先对以上数据以结束时间递增顺序进行排序得到以下队列：
表3 对数据以结束时间递增顺序进行排序得到的队列然后按照贪心算法取结束时间提前的活动以为后续活动提供更多时间，同时在保证选择的活动的结束时间提前还要保证该活动与前一个活动相容。依次选择的活动为2、4、8、10。
3.5 算法分析
3.5.1 关键代码及解释
void greedySelect(int n)//活动的贪心选择
{
a[num[1]]=true;
int j=1;
for(int i=2;i<=n;i++)
if(s[i]>=f[j])
{
a[num[i]]=true;
j=i;
}
else
a[num[i]]=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(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语言的一些较为简单的基础语法等等再结合算法的内容。如果使用了数据结构的话，就会让这个课程设计更具特色，也显得高级一点。
《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的
通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法：
网页制作课程设计报告 学院： 专业班级： 姓名： 学号： 成绩： 阅卷教师：
目录 1.设计目的 (1) 2.设计思想 (1) 2.1网站整体结构规划思想 (1) 2.2 主页设计思想 (1) 2.3子页的设计思想 (1) 3网页详细设计分析 (1) 4结论 (2)
1.设计目的 阐述该个人网站的设计意图和创意，简单介绍自己的个人网站。 2.设计思想 阐述网站的整体设计思想，包括： 2.1网站整体结构规划思想 要求阐述网站整体结构的选择、设计的思想，绘制网站结构草图。 2.2 主页设计思想 要求对主页的布局思路进行阐述和分析。 2.3子页的设计思想 要求对子页的设计以及网页对象的选取思路进行阐述和分析。 3网页详细设计分析 要求选取一张网页，对网页的设计实现过程进行阐述和分析，详细说明制作该网页的步骤，所使用的网页对象以及该网页对象的操作方法。
4结论 对整个设计报告做归纳性总结，并分析设计过程中的困难及如何解决的，最后提出展望。 一、设计目的 本课程的设计目的是通过实践使同学们经历Dreamweaver cs3开发的全过程和受到一次综合训练，以便能较全面地理解、掌握和综合运用所学的知识。结合具体的开发案例，理解并初步掌握运用Dreamweaver cs3可视化开发工具进行网页开发的方法；了解网页设计制作过程。通过设计达到掌握网页设计、制作的技巧。了解和熟悉网页设计的基础知识和实现技巧。根据题目的要求，给出网页设计方案，可以按要求，利用合适图文素材设计制作符合要求的网页设计作品。熟练掌握Photoshop cs3、Dreamweaver cs3等软件的的操作和应用。增强动手实践能力，进一步加强自身综合素
编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月
设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成
摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语
课程设计报告 ( 2013-- 2014年度第1学期) 名称：编译技术课程设计B 题目：简单编译程序的设计与实现院系：计算机系 班级：XXX 学号：XXX 学生姓名：XXX 指导教师：XXX 设计周数：XXX 成绩： 日期：XX 年XX 月
实验一．词法分析器的设计与实现 一、课程设计(综合实验)的目的与要求 1.1 词法分析器设计的实验目的 本实验是为计算机科学与技术专业的学生在学习《编译技术》课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。 1.2 词法分析器设计的实验要求 设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设该程序设计语言中，基本字（也称关键词）不能做一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。 单词符号及其内部表示如表1-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。 表1-1 单词符号及其内部表示
二、设计（实验）正文 1.词法分析器流程图 2.词法分析器设计程序代码 // first.cpp : 定义控制台应用程序的入口点。// #include"stdafx.h" #include
Web应用开发技术 实验报告 专业：计算机科学与技术 班级： 学号： 姓名：
一、设计题目 个人网站 二、目的 １、本次设计是学生在学完ASP动态网站开发课程后的一次实践性很强的课程设计，是对ASP进行动态网站开发所学知识的综合运用。 2、掌握使用ASP技术进行网站开发设计。 3、通过本次实习，使学生加深所学知识内容的理解，并能积极地调动学生的学习兴趣，结合实际应用操作环境，真正做到理论与实际相结合。 三、功能需求描述 此网站可以对主人留言，来发表自己的心情，也可以把自己的联系方式写入其中，达到和睦相处、心灵的驿站的目的等。 四、总体设计
五、详细设计 （一）、我的主页 此页面为网站的主页，通过发布新心情，点击通讯录可以查看通讯录好友信息，点击留言板可以查看好友留言。 主要代码：