《《算法分析与设计》实验教学大纲new.doc》由会员分享，可在线阅读，更多相关《《算法分析与设计》实验教学大纲new.doc（10页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计实验教学大纲课程编号：10000284课程名称：算法分析与设计英文名称：Algorithm Analysis and Design适应专业：软件工程执 笔 人：刘淑英实验教材（指导书）：王晓东，计算机算法设计与分析，电子工业出版社，2007主要参考书目：张铭、刘晓丹译电子工业出版社出版的数据结构与算法分析徐士良主编清华大学出版社出版的计算机常用算法第二版卢开澄主编清华大学出版社出版的计算机指导引论设计与分析一、实验学时总学时：48 总学分：3 实验学时：10二、实验课的任务、性质与目的算法设计与分析是计算机专业的专业核心课程，其先修课程有数据结构和至少一门高级语言。算法设计与分析
2、课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力。通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法。同时，上机实习是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。本课程的主要目的是研究计算机领域及其它有关领域中的主要算法设计方法及一些常用算法，使学生掌握算法设计的常用方法，以便运用这些方法来设计解决一些常用的或较为
3、复杂的实际问题的算法，并力争做到快捷、有效，从而提高程序设计的质量。同时，还要使学生学会分析算法、估计算法的复杂性，以便理解并科学评估有一个算法的好坏。它属于技术基础课，是进行软件设计的核心内容，是一门实践性很强的课程。学生应具有C或C+、数据结构的基础知识。三、实验内容（1）分治策略算法（4学时）实验内容：用分治法实现快速排序、归并分类算法；编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天。实验要求：掌握递归算法实现的过程；了解快速排序算法的思
4、想，掌握用算法设计思想解题的思路。（2）贪心算法（2学时）实验内容：编写一个简单的程序，实现单源最短路径问题；编写一段程序，实现找零；编写程序实现多机调度问题。实验要求：掌握贪心算法的基本设计思路，并用其解决实际问题。（3）动态规划算法（2学时）实验内容：编写一个简单的程序，解决0-1背包问题；编程解决合唱队形安排。实验要求：掌握动态规划算法设计的基本策略。（4）回溯算法（2学时）实验内容：用回溯法解8皇后问题；批处理作业调度。实验要求：掌握回溯法的算法框架和算法的基本思想。四、实验要求（1）学生在完成预习报告、熟悉实验内容后才能进入实验室进行上机实验。实验1人一组，由学生独立操作完成实验。（
5、2）学生分析问题，熟悉解决问题的算法描述。要求记录上机实验过程，且得到指导教师认可后，学生方可离开实验室。（3）实验完成后提交实验报告。（4）实验过程由指导老师监督，听从老师安排和督导。五、实验项目的设置与内容提要本课程主要通过综合设计性实验，完成一个问题的算法分析设计过程，培养学生解决设计问题的能力，提高学生综合设计能力。要求学生通过查阅文献、小组讨论完成实验任务。序号实验项目名称实验学时实验类型实验要求内容提要1分治策略算法4综合设计性必做用分治策略解决排序等问题。2贪心算法2综合设计性必做掌握贪心算法的基本设计思路，并用其解决实际问题。3动态规划算法2综合设计性必做掌握动态规划算法设计的
6、基本策略。4回溯算法2综合设计性必做掌握回溯算法的基本思想。六、考核方式（1）每次任务完成后由指导老师逐个的检查实验内容、结果并评分，占实验成绩60%。（2）上机考勤评分，占实验成绩10%。（3）实验报告占实验成绩30%。实验一 排序问题求解实验目的1）以排序（分类）问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法；实验环境计算机、C语言程序设计环境实验学时4学时，必做实验。实验内容与步骤1. 生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间1,10000上的随机整数，并将这些
7、数输出到外部文件data.txt中。这些数作为后面算法的实验数据。2. 实现直接插入排序算法.要求：实现insertionsort算法。算法的输入是data.txt；输出记录为文件：resultsIS.txt；同时记录运行时间为TimeIS。直接插入算法思想：Procedure insertionsort(A,n)A(0)=-for j=2 to n doitem=A(j); i=j-1while item=v repeatloop p=p-1 until A(p)=v repeatif Ipthen call interchange(A(i), A(p)Else exitEndifRepea
8、tA(m)=A(p); A(p)=vEnd partition3. 实现快速排序算法.要求：实现QuickSort 算法。算法的输入是data.txt；输出记录为文件：resultsQS.txt；同时记录运行时间为TimeQS。快速排序算法思想：Procedure QuickSort（p,q） integer p,q；global n,A(1:n) if pcu then exit endif X(i) 1 cucu-W(i)repeatif in then X(i) cu/W(i)endifend GREEDY-KNAPSACK2. 以策略1作为量度标准求解要求问题，记录解向量为X1、目标函
9、数的值fp1（即最后装好包后背包的效益值）、背包的重量fw1；3. 以策略2作为量度标准求解要求问题，记录解向量为X21、目标函数的值fp2（即最后装好包后背包的效益值）、背包的重量fw2； 4. 以策略3作为量度标准求解要求问题，记录解向量为X3、目标函数的值fp3即最后装好包后背包的效益值）、背包的重量fw3； 实验报告： 实验报告应包括以下内容：（1）题目；（2）算法的基本思想描述；（3）程序流程图；（4）给出3个程序任意之一的程序清单；（5）实验分析；通过实验结果对比分析说明哪种策略好。（6）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。Tips：1. 解向量的表示
10、。需要注意：因为算法中涉及到排序，如何保证各种物品的原始命名（如果以第几种，即序号，来命名物品）关系需要考虑。#define MAX 200typedef struct Solution /定义的解向量 int xMAX; 表示该号物品放了多少在背包里，这里 int orderMAX; 表示物品的序号，相当于其名字 Solution;Solution X;所以，初始化时，为：for (i=0; in; i+) X.orderi=i; X.xi=0; 2. 主要函数：void GreedyKnapsack(float profit,float weight,float x,int m, int n)float cu;int i;cu=float(m);for(i=0;i
