《算法分析与设计》实验指导书（适用于计算机科学与技术、软件工程专业）计算机科学与技术学院软件教研室2011-8目录实验一算法分析 (3)实验二分治策略 (4)实验三堆排序 (5)实验四动态规划 (6)实验五贪心算法 (8)实验六图算法1-基本图算法 (10)实验七图算法2-最小生成树和单源顶点最短路径 (12)实验八图算法3-所有点对最短路径.14 附录一实验规范. 15实验一算法分析一、实验目的及任务1、使学生通过插入排序和合并排序的算法实现，理解算法的概念并且通过运行时间比较其时间复杂度。
2、体会合并排序的分治方法的三个步骤：分解、递归求解和合并。
3、了解渐近记号的意义和初步分析算法复杂性。
二、实验环境c++或java或Turbo c三、问题描述Input: A sequence of n numbers <a1, a2, . . .,a n>.Output: A permutation (reordering) <a1’, a2’, . . .,a n’> of the input sequence such that a1’≤a2’≤ . . . ≤a n’四、编程任务给定长度为n的一个序列，对其进行插入排序和合并排序五、数据输入随机产生10000以上的数据，放入输入文件input.txt，用来进行排序六、结果输出排序后的结果和两种排序算法的运行时间输出到文件output.txt七、实验报告内容见《算法分析与设计》实验规范。
实验二分治策略一、实验目的及任务1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；2、分治算法思想解决median问题。
二、实验环境c++或java或Turbo c三、问题描述(1) Input: A sequence of n numbers <a1, a2, . . .,a n>.Output: A permutation (reordering) <a1’, a2’, . . .,a n’> of the input sequence such that a1’≤a2’≤ . . . ≤a n’(2) Input: A set A of n (distinct) numbers and a number i, with 1 ≤i ≤n.Output: The element x∈A that is larger than exactly i - 1 other elements of A.四、编程任务给定长度为n的一个序列，对其进行快速排序和求第i小数五、数据输入A=<13,19,9,5,12,8,7,4,11,2,6,21>六、结果输出将排序结果输出到文件output.txt。
如果不存在所要求的第i小数，则输出-1。
七、实验报告内容见《算法分析与设计》实验规范。
实验三堆排序一、实验目的及任务1、了解堆的性质； 2利用堆构成一个优先队列，并实现相关的函数功能； 3为图算法做好准备。
二、实验环境c++或java或Turbo c三、问题描述A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. A max-priority queue supports the following operations.. INSERT(S, x) inserts the element x into the set S. This operation could be written as S←S ∪ {x}.. MAXIMUM(S) returns the element of S with the largest key.. EXTRACT-MAX(S) removes and returns the element of S with the largest key.. INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k,which is assumed to be at least as large as x's current key value. 四、编程任务编程建立最大堆，构造优先队列并实现以上的相关操作。
五、数据输入A=<15，13，9，5，12，8，7，4，0，6，2，1>六、结果输出执行INSERT(A, 10)，EXTRACT-MAX(A)，将结果输出到文件output.txt。
七、实验报告内容见《算法分析与设计》实验规范。
实验四动态规划一、实验目的及任务1、掌握动态规划算法的基本步骤：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。
2、熟悉最长公共子序列问题的算法，设计一个算法解决编辑距离问题。
二、实验环境c++或java或Turbo c三、问题描述1 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
2 设A和B是2个字符串。
要用最少的字符操作将字符串A转换为字符串B。
这里所说的字符操作包括：山出一个字符、插入一个字符、将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作称为字符串A到字符串B的编辑距离，记为d(A,B)。
试设计一个有效算法，对任意给定的两个字符串，计算出它们的编辑距离d(A,B)。
四、编程任务1 求X和Y的最长公共子序列长度以及最长公共子序列2 对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。
五、数据输入1由文件input.txt提供输入数据，X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}。
2由文件input.txt提供输入数据。
文件的第1行是字符串A，文件的第2行是字符串B。
A:fxpimu B:xwrs六、结果输出1程序运行结束时，将编程计算出的最长公共子序列长度以及最长公共子序列输出到文件output.txt中。
2 程序运行结束时，将编辑距离d(A,B)输出到文件output.txt的第1行中。
七、实验报告内容见《算法分析与设计》实验规范。
实验五贪心算法一、实验目的及任务1、掌握贪心算法的基本性质。
2 贪心算法与动态规划的区别。
3 贪心算法解决活动安排问题和背包问题。
二、实验环境c++或java或Turbo c三、问题描述1 有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。
如果选择了活动i，则它在半开时间区间[si, fi]内占用资源。
若区间[si, fi]与区间[sj, fj]不相交，则称活动i与活动j是相容的。
也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。
该问题要求高效地安排一系列争用某一公共资源的活动。
贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
2 0-1背包问题：给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi，背包的容量为C。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大?背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
四、编程任务1 在所给的活动集合中选出最大的相容活动子集合。
2 计算背包问题/0-1背包问题背包的价值五、数据输入1i 1 2 3 4 5 6 7 8 9 10 11si 1 3 0 5 3 5 6 8 8 2 12fi 4 5 6 7 8 9 10 11 12 13 142W={10,100,120} V={10,20,30} C=50六、结果输出1、将编程计算出的最长最大活动安排结果输出到文件output1.txt。
2、将编程计算出的背包价值输出到文件output2.txt。
七、实验报告内容见《算法分析与设计》实验规范。
实验六图算法1-基本图算法一、实验目的及任务1、掌握图邻接表的存储方法；2、掌握深度优先遍历算法(DFS)；3、利用深度优先遍历的timestamps进行拓扑排序或计算有向图的强连通分支；二、实验环境c++或java或Turbo c三、问题描述Given G=(V,E) In DFS, edges are explored out the most recently discovered vertex v that still has unexplored edges leaving it. When v's edges have been explored, the search "backtracks" to explore edges leaving the vertex from which v was discovered. Besides creating a depth-first forest, DFS also timestamps each vertex. Each vertex v has two timestamps: the first timestamp d[v] records when v is first discovered, and the second one f[v] records when the search finishes examining v's adjacency list.A topological sort of a directed acyclic graph (DAG) G = (V;E) is a linear ordering of all its vertices such that if G contains an edge (u; v), then u appears before v in the ordering (if the graph is cyclic, then no linear ordering is possible).A strongly connected component (SCC) of a directed graph G = (V;E) is a maximal subset of vertices C ⊆ V such that ∀u, v ∈C, we have u→v and v→ u.四、编程任务1 、深度优先遍历； 2、利用深度优先遍历的timestamps进行拓扑排序；3、利用深度优先遍历的timestamps进行有向图的强连通分支；五、数据输入六、结果输出1、将编程计算出深度优先遍历结果输出到文件output1.txt；2、将编程进行拓扑排序结果输出到文件output2.txt；3、将编程进行有向图的强连通分支的结果输出到文件output3.txt。
