算法设计与分析的实验指导书2012(李淑琴).docVIP

《算法分析与设计》实验教学大纲 一、实验课的性质与任务 算法设计与分析是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。 二、实验课程目的与要求 实验目的 本课程实验教学的目的和任务是使学生通过实践环节深入理解和掌握课堂教学内容，使学生得到数据库应用的基本训练，提高其解决实际问题的能力。 实验要求 使学生通过上机训练掌握算法设计过程与方法，并学会分析算法的时间复杂度、空间复杂度和稳定性，具有问题抽象和建模的初步能力并将所编写的算法通过上机验证得到正确的结果。 三、实验内容安排 实验一 数据的排序算法比较 （一）、实验目的： 通过上机实践，进一步理解、掌握几种著名的数据排序算法，以及算法的时间复杂性的比较计算。 （二）、实验题目与要求： （1）待排序表的长度不小于100000；其中的数据用为随机数产生程序产生。 （2）从已学过的内部排序算法中选择至少4种算法，通过比较各种算法的关键字移动次数以及比较次数。至少用五组不同的输入数据作比较。 （3）最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 （三）、实验步骤： 对于以上题目要认真分析和理解题意，设计出粗略的程序框架（算法）； 详细写出正确的C语言源程序； 上机录入并调试程序； 请指导教师审查程序和运行结果并评定成绩； 撰写并上交实验报告。 （四）、实验报告内容： 班级、学号、姓名、实验日期； 实验题目； 对于实验题目的理解与说明； 程序功能与框架； 设计说明（存储结构、特别构思等）； 用户操作指南； 调试报告（调试过程中遇到的问题及如何解决此问题，程序设计的得失，对于改进程序的设想、经验、体会等）； 附录：源程序清单（加必要的注释）、测试数据及运行结果。 实验二 递归与分治策略 （一）、实验目的： 通过编程实现递归与分治策略的有关算法，理解递归与分治策略算法的原理，掌握递归与分治策略基本思想与应用技巧。 （二）、实验题目与要求： 实验题目：给定平面上的至少n个点（n〉=20），找出其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 实验要求：认真阅读书中P124给出的最接近点对问题算法的部分程序代码。完善程序，实现该算法。 （三）、实验步骤： 同实验一。 （四）、实验报告内容： 同实验一。 　　　　实验三 动态规划 （一）、实验目的： 通过编程实现动态规划的有关算法，理解动态规划的原理，掌握动态规划基本思想与应用技巧。 （二）、实验题目与要求： 实验题目1: 　0-1背包问题。即给定n种物品（n）5）和一个背包，物品i的重量为，价值为，背包的承重量为C。编程实现选择装入背包的物品，使得装入的总价值最大。 实验题目2: 若城市路径示意图如下图所示， 图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。 实验要求：理解动态规划算法的原理，认真阅读给出的部分程序代码。完善程序，实现该算法。 （三）、实验步骤： 同实验一。 （四）、实验报告内容： 同实验一。 实验四 贪心算法 （一）、实验目的： 通过编程实现有关的贪心算法，理解贪心算法的原理，掌握贪心算法基本思想与应用技巧。 （二）、实验题目与要求： 实验题目：求解（1）最短路径 （2）最小生成树 （3）哈夫曼编/译码器，其中任意选作一题。 实验要求：理解贪心算法的原理，认真阅读给出的部分程序代码。完善程序，实现相应算法。 （三）、实验步骤： 同实验一。 （四）、实验报告内容： 同实验一。 ? 四、主要教材及参考书 1教材： 算法设计技巧与分析 [沙特]M.H.Alsuwaiyel著 吴伟 方世昌等译 电子工业出版社 2.参考书： 算法设计与分析 郑宗汉 郑晓明 清华大学出版社 数据结构习题集 严蔚敏 吴伟民 米宁 清华大学出版社 计算机算法基础 余祥宣等 华中理工大学出版社 计算机算法：设计与分析引论 [美]S.巴斯著 朱洪等译 复旦大学出版社 算法分析与设计 王晓东 清华大学出版社 算法设计和分析 朱洪等 上海科技文献出版社