《算法分析与设计》实验教学大纲

一、实验课程性质、目的与任务

《算法分析与设计》是一门理论性与实践性兼顾的课程，是软件工程、计算机科学与技术、网络工程及相关专业的基础课程。课程是“编译原理”和“软件工程”等专业核心课程的基础课，为学习专业课程及提高软件设计水平打下良好的基础。

算法分析与设计实验是学习和研究算法的重要实践环节，其目的在于通过对各种算法的实验使学生理解各种算法设计的基本思想，理解和掌握算法设计的主要方法，锻炼学生独立分析问题和解决问题的能力，为开发高效的软件系统及相关领域的研究工作奠定坚实的基础。

二、实验教学基本要求

算法分析与设计实验是学习算法分析与设计的重要实践环节，其目的是通过实验使学生掌握各种算法的基本原理，通过实验提高学生的程序设计能力和分析与解决实际问题的能力。

要求学生掌握递归与分治法、贪心法、动态规划法、回溯法、分支限界法、线性规划与网络流、近似算法，并学会使用C语言编程实现。通过对实际问题的分析与求解，进一步加深对算法设计方法的认识和理解。

上机实验要求：

1、准备好上机所需的程序；

2、上机输入和调试自己所编写的程序，并在程序设计在线测试平台上提交通过；

3、上机结束后，应整理出实验报告，实验报告应包括以下内容：实验项目名称；算法分析；程序清单；运行结果；对运行情况所作的分析以及本次调试程序所取得的经验，如果程序未能通过，应分析其原因。

三、实验项目与类型：

四、实验教学内容

实验一：递归算法

1、实验目的

（1）掌握递归的概念与基本原理

（2）通过本实验加深对递归过程的理解

（3）能够使用递归方法编程求解典型问题

2、方法原理

（1）递归法的基本思想：对于一个复杂的问题，把原问题分解为若干个相对简单的同类子问题，继续下去直到子问题能够直接求解，从而递推得到原问题的解。

（2）递归算法：一个直接或者间接调用自身的算法。

3、主要实验仪器及材料

计算机、安装如VC++6.0或者DEV C++

4、实验内容

（1）整数划分问题。任意输入一个整数，输出结果能够用递归方法实现整数的划分。

（2）棋盘覆盖问题。在一个2^k×2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

实验二：分治法

1、实验目的

（1）理解分治的概念与基本原理

（2）理解分治策略的基本原理和效率分析，掌握设计有效算法的分治策略

（3）能够使用分治方法编写程序。

2、方法原理

（1）分治法的基本思想：将一个规模大的问题分解为若干个规模较小的同类子问题，这些子问题相互独立且与原问题相同。递归地求解这些子问题，然后将各个子问题的解合并得到原问题的解。

（2）分治算法：一般使用递归算法来实现。

3、主要实验仪器及材料

计算机、VC++6.0或者DEV C++

4、实验内容

（1）设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最大元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

（2）设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i＜n，使得t[i]=i，设计一个分治算法找到这个下标。

实验三：动态规划

1、实验目的

（1）理解动态规划的概念与基本原理

（2）通过本实验加深对动态规划算法的理解

（3）能够使用动态规划方法编程求解典型问题

2、方法原理

（1）动态规划的基本思想：将一个待求解的问题分解为若干个子问题，先求解子问题，然后从子问题的解得到原问题的解。适合用动态规划求解的问题，经过分解得到的子问题通常不是相互独立的。

（2）动态规划算法：通常用来求解具有某种最优性质的问题，将子问题求出的解保存以加快原问题的求解速度。

3、主要实验仪器及材料

计算机、安装VC++6.0或者DEV C++

4、实验内容

（1） 最长公共子序列问题。若给定序列X={x₁,x₂,…,x_m}，则另一序列Z={z₁,z₂,…,z_k}，是X的子序列是指存在一个严格递增下标序列{i₁,i₂,…,i_k}使得对于所有j=1,2,…,k有：zj=xi_j。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Z，求X和Z的最长公共子序列。

（2）最大子段和问题。若给定n个整数组成的序列a₁，a₂，a₃，……a_n，求该序列形如a_i＋a_i＋1＋……＋a_n的最大值。

实验四：贪心算法

1、实验目的

（1）理解贪心的概念与基本原理

（2）通过本实验加深对贪心算法的理解

（3）能够使用贪心算法编程求解典型问题

2、方法原理

（1）贪心法的基本思想：通过一系列的选择来得到一个问题的解，所作的选择都是当前状态下的最好状态。

（2）贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。贪心选择可以依赖于以往所作的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。

3、主要实验仪器及材料

计算机、安装VC++6.0或者DEV C++

4、实验内容

（1）作业调度。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。

（2）汽车加油问题。一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。

实验五：回溯法

1、实验目的

（1）理解回溯法的基本原理和效率分析。

（2）通过本实验加深对回溯法的理解

（3）能够使用回溯法编程求解典型问题

2、方法原理

（1）回溯法的基本思想：在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

（2）回溯法搜索策略：在搜索至解空间树的任一结点时，总是先判断该结点是否包含问题的解。如果不包含，则忽略对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入该子树继续按照深度优先的策略进行搜索。当回溯到根结点，并且根结点的所有子树都已搜索完才结束。

3、主要实验仪器及材料

计算机、安装C++(如VC++6.0或者DEV C++ )

4、实验内容

（1）0-1背包问题。给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

（2）图的m着色问题。给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

实验六：分支限界法

1、实验目的

（1）理解分支限界算法的基本原理

（2）理解分支限界算法与回溯算法的区别

（3）能够使用分支限界法编程求解典型问题

2、方法原理

（1）分支限界法的基本思想：在问题的解空间树中搜索问题的解，它一般不是搜索问题的所有解，它通常用于找出满足约束条件的一个解，或者是在满足约束条件的解中找出使某一目标函数达到极值的解，即在某种意义下的最优解。

（2）分支限界法的搜索策略：在搜索解时是以广度优先或以最小耗费优先的方式搜索解空间树。在扩展结点处，先生成其所有分支结点然后再从当前的活动结点中选择下一个扩展结点。在选择结点时，计算一个函数值（限界），并且根据已计算出的函数值，从当前的活动结点中选择下一个最有利的结点作为扩展结点，使搜索朝解空间树上有最优解的分支推进，以便尽快找出最优解。

3、主要实验仪器及材料

计算机、安装VC++6.0或者DEV C++

4、实验内容

旅行商售货员问题。某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。

实验七：网络最大流

1、实验目的

（1）理解网络流的概念与网络最大流算法的基本原理

（2）通过本实验加深对网络最大流算法的理解

（3）能够使用网络最大流算法编程求解典型问题

2、方法原理

求解网络最大流的算法有二类：增广路算法和预流推进算法。

（1）增广路算法的基本思想：从一个可行流开始，沿着增广路对网络流进行增广，直到网络中不存在增广路为止。

（2）预流推进算法的基本思想：从一个预流出发对活跃顶点沿着允许弧进行流量增广，每次增广称为一次推进。

3、主要实验仪器及材料

计算机、安装C++(如VC++6.0或者DEV C++ )

4、实验内容

某物资有m个生产基地A1，A2，…，Am要通过铁路运到n个销地B1，B2，…，Bn去。把铁路网上的车站看作是顶点，两个车站间的铁路线看作是弧。可以认为在某条铁路线上可运送的物资数量是有限的，我们把某条线路上的允许最大运送量称为容量。这时要考虑如何安排运输方案，使得由产地运到销地的物资总量达到最大。

五、考核方法

1．教师对学生实验过程完成情况进行详细登记，记入实验成绩中。

2．学生完成实验后按要求撰写实验报告，根据实验报告确定每次实验的等级。

3．实验成绩按20%比例计入课程期评总成绩中。

六、实验指导书及主要参考书目

[1] 王晓东.《计算机算法分析与设计（第4版）》.北京：电子工业出版社，2012.

[2] 赵端阳 编著.《算法分析与设计》.北京：清华大学出版社，2012.

[3] 石志国，刘冀伟，姚亦飞 编著.《算法分析与设计（C++描述）》.北京：清华大学出版社，2010.

[4] 霍红卫 译.《算法分析与设计》.北京：人民邮电出版社，2006.

[5] 吴伟旭 方世昌译.《算法分析与设计》.北京：电子工业出版社，2004.

主 撰 人： 袁辉勇

审 核 人： 罗如为

2012.6