《算法分析与设计》实验教学大纲.docx
算法分析与设计实验教学大纲（Analysis and Design of Algorithms）课程代码：0610008实验学时：15学时先修课程：C语言程序设计、数据结构一、目的要求目的：通过实验，使学生消化理论知识，加深对讲授内容的理解，尤其是一些算 法的实现及应用，培养学生独立编程和调试程序的能力，使学生对算法分析与设计有 更深刻的认识，并设计出应用程序的能力。要求：熟悉VC+的编程和调试环境，根据实验内容和要求，认真完成程序编写、 上机调试、运行结果分析，书写实验报告。二' 实验项目内容及学时分配实验一、分治算法（2学时）1 .实验目的要求：掌握分治算法的基本思想和解题步骤。熟悉循环赛日程表安排的分治算法。熟悉快速排序的分治算法。熟悉用c语言实现分治算法。2 .实验主要内容：编写、调试下面两个问题的C语言程序。循环赛日程安排问题。设有16个运动员将进行网球循环赛。请设计一个满足以 下要求的比赛日程表： 每个选手必须与其它15个选手各赛一场， 每个选手一天 只能赛一场，循环赛共进行15天。排序问题。用快速排序方法，对下列十个正整数：42、 96、 23、 89、 48、 75、 36、 30、 57、 61按从大到小进行排序。3 .实验类别：专业4 .实验类型：验证5 .实验要求：必做6 .主要仪器：安装VC6.0的微型计算机。实验二、贪心算法（2学时）.实验目的要求：掌握贪心算法的基本思想和解题步骤。熟悉哈夫曼(Huffman)编码问题的贪心算法。 熟悉无向连通带权图最小生成树的Prim算法和Kruskal算法。熟悉用C语言实现贪心算法。1 .实验主要内容：编写、调试下面两个问题的C语言程序。 哈夫曼(Huffman)编码问题。设信号源为s= si, s2, s3, s4, s5 ,对应的概 率为 p= 0. 25, 0. 22, 0. 20, 0. 18, 0. 15 。编程求出并显示 si, s2, s3, s4, s5 的哈夫曼 (Huffman)编码。最小生成树问题。用Prim算法(或者Kruskal算法)求下面无向连通带权图的4 .实验类型：验证5 .实验要求：必做6 .主要仪器：安装VC6.0的微型计算机。7 验三、动态规划算法(2学时).实验目的要求：掌握动态规划算法的基本思想和解题步骤。熟悉矩阵连乘问题的动态规划算法。熟悉最长公共子序列问题的动态规划算法。 熟悉用C语言实现动态规划算法。1 .实验主要内容：编写、调试下面两个问题的C语言程序。矩阵连乘问题。求矩阵 Ai(5X3)、A2(3X4)> A3(4X7)> A,(7X2)、As(2X3)和A6 (3X6)连乘的最佳计算次序。最长公共子序列问题。已知序列*= (A, B, C, A, B, D, A)和序列Y= (B, A,D, B, A),求它们的最长公共子序列S。3 .实验类别：专业4 .实验类型：验证5 .实验要求：必做6 .主要仪器：安装VC6.0的微型计算机。7 验四、回溯算法(2学时)8 .实验目的要求：掌握回溯算法的基本思想和解题步骤。掌握回溯算法的递归实现。熟悉八皇后问题的回溯算法。熟悉作业调度问题的回溯算法。熟悉用C语言实现回溯算法。9 .实验主要内容：编写、调试下面两个问题的C语言程序。 八皇后问题。在8X8的国际象棋棋盘上放置八个皇后，要求任何两个皇后都不 能处于同一条水平线、竖直线和斜线(45°或135°线)上。作业调度问题。设有5个作业 J1,J2,J3,J4,J5 要在由两台机器帆和M2组成的 流水线上完成加工。每个作业加工的顺序都是先在Mi上加工，然后在岫上加工。作业 J在此和Mz上加工所需的时间(单位：小时)分别为4和b (l<i<5),见下表：*1123453d24365bi11232如何确定这5个作业的加工顺序，使得从第一个作业在机器此上开始加工，到最后 一个作业在机器M2上加工完成所需的时间最少。10 实验类别：专业11 实验类型：验证12 实验要求：必做13 主要仪器：安装VC6.0的微型计算机。实验五' 分支限界算法(2学时)1 .实验目的要求：掌握分支限界算法的基本思想和解题步骤。掌握分支限界算法的递归实现。 熟悉0T背包问题的分支限界算法。熟悉装载问题的分支限界算法。熟悉用C语言实现分支限界算法。2 .实验主要内容：编写、调试下面两个问题的C语言程序。0-1背包问题。设有5件物品和1个负重量为C=40kg的背包。第i件物品的重 量是柏、价值是匕（l<i<5）,见下表：112345Wi (kg)85151012Vi阮）100709015060将哪些物品装入背包可使这些物品的体积总和不超过背包的负重量，且价值总和最 大。装入某物品时，要么全部装入，要么一点不装入，不允许部分装入。装载问题。设有9个集装箱要装上两艘载重量分别为。=900（吨）和C2=1000（吨）9的轮船，其中集装箱i的重量为眩（l<i<9）,且Z叱<G+C2,见下表：i=l1123456789Wi (吨)160240140180270220170150210请设计一个将这6个集装箱装上这两艘轮船的方案。3 .实验类别：专业4 .实验类型：验证5 .实验要求：必做6 .主要仪器：安装VC6.0的微型计算机。实验六、概率算法（2学时）.实验目的要求：掌握概率算法的基本思想、设计方法和解题步骤。 熟悉定积分的Monte Carlo算法。 熟悉八皇后问题的Las Vegas算法。熟悉用C语言实现概率算法。1 .实验主要内容：编写、调试下面两个问题的C语言程序。r2 sinx , 定积分问题。求定积分dx的近似值。Ji % 八皇后问题。在8X8的国际象棋棋盘上放置八个皇后，要求任何两个皇后都不 能处于同一条水平线、竖直线和斜线（45°或135°线）上。2 .实验类别：专业3 .实验类型：验证4 .实验要求：必做5 .主要仪器：安装VC6.0的微型计算机。实验七' 设计性实验项目（3学时）（另见设计性实验项目教学大纲）三' 成绩计算方法1 .每一次实验成绩按百分制计算：实验准备40%、操作过程30%、实验报告30%。2 .实验成绩为每一次实验成绩的平均值。3 .实验成绩计入课程总成绩，所占比例：20%o
