《算法分析与设计》实验指导书
（适用于计算机科学与技术、软件工程专业）
计算机科学与技术学院
软件教研室
20##-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, . . .,an>.
Output: A permutation (reordering) <a1’, a2’, . . .,an’> of the input sequence such that a1’£a2’ £ . . . £an’
四、 编程任务
给定长度为n的一个序列，对其进行插入排序和合并排序
五、 数据输入
随机产生10000以上的数据，放入输入文件input.txt，用来进行排序
六、 结果输出
排序后的结果和两种排序算法的运行时间输出到文件output.txt
七、 实验报告内容
见《算法分析与设计》实验规范。
实验二 分治策略
一、 实验目的及任务
1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；2、分治算法思想解决median问题。
二、 实验环境
c++或java或Turbo c
三、 问题描述
(1) Input: A sequence of n numbers <a1, a2, . . .,an>.
Output: A permutation (reordering) <a1’, a2’, . . .,an’> of the input sequence such that a1’£a2’ £ . . . £an’
(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背包问题背包的价值
五、 数据输入
1
i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 8 9 10 11 12 13 14
2
W={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。
七、 实验报告内容
见《算法分析与设计》实验规范。
实验七 图算法2-最小生成树和单源顶点最短路径
一、 实验目的及任务
1、应用优先队列求最小生成树的Prim 算法，了解其中的贪心算法的设计思想；2、应用优先队列求单源顶点的最短路径Dijkstra算法，了解贪心算法的设计思想，并掌握松弛技巧。
二、 实验环境
c++或java或Turbo c
三、 问题描述
1、 Given a connected, undirected graph G = (V,E), where "(u, v) ∈ E has a
weight w(u, v). We intend to find an acyclic subset T Í E that connects all the vertices and whose total weight w(T) =
is minimized. Since T is acyclic and connects all vertices, it must be a tree, called spanning tree. The problem to find such T is called minimum spanning tree (MST) problem.
2、 Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ∈ V – S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u.
四、 编程任务
1、对于给定的赋权图G，编程计算图的最大边权最小生成树。
2、对于给定的赋权图G，编程计算图的单源顶点最短路径。
五、 数据输入
1 由文件input.txt 给出输入数据。第1 行有2 个正整数n 和m，表示给定的图G 有n 个
顶点和m条边，顶点编号为1，2，…，n。接下来的m行中，每行有3 个正整数u,v,w，表
示图G 的一条边(u,v)及其边权w。
2
六、 结果输出
1 将编程计算出的最大边权最小生成树的最大边权输出到文件output1.txt。如果不存在所
要求的最大边权最小生成树，则输出-1。
输入文件示例
input.txt
7 9
1 2 28
1 6 10
2 7 14
2 3 16
6 5 25
7 5 24
7 4 18
3 4 12
5 4 22
输出文件示例
output.txt
25
2 将编程计算出单源顶点最短路径结果输出到output2.txt。
七、 实验报告内容
见《算法分析与设计》实验规范
实验八 图算法3-所有点对最短路径
一、 实验目的及任务
1、掌握Matrix multiplication 和Floyd-Warshall algorithm的实现； 2、了解这两种算法的不同； 3、进一步了解所有点对最短路径问题中的动态规划设计思想。
二、 实验环境
c++或java或Turbo c
三、 问题描述
Given a weighted, directed graph G = (V,E), for any u, v ∈ V , find a shortest path from u to v.
四、 编程任务
对于给定的赋权有向图G，编程计算图的所有点对的最短路径。
五、 数据输入
六、 结果输出
将编程计算出的所有点对的最短路径输出到文件output.txt。
七、 实验报告内容
见《算法分析与设计》实验规范
《算法分析与设计》实验规范
一、 实验课的意义
实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变"活"，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的"小"算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。
二、 实验步骤
常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然算法分析与设计课程中的实验题目的远不如从实际问题中的复杂程度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目：
1．问题分析和任务定义
在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。
2．逻辑设计和详细设计
在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。
3．编码实现和静态检查
编码是把详细设计的结果进一步求精为程序设计语言程序。如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。
然而，不管你是否写出编码的程序，在上机之前，认真的静态检查是必不可少的。静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过对程序深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。
4．上机准备和上机调试
上机准备包括以下几个方面：
(1) 注意同一高级语言文本之间的差别。
(2)熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 (3)掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。应该能够熟练运用高级语言的程序调试器DBBUG调试程序。
(4)上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。
5．总结和整理实验报告
要求采用以下模板完成实验报告
算法分析与设计程序设计上机实验报告
1．算法问题描述
明确描述所要解决的问题，强调的该问题要做什么?主要包括：
(1)输入的形式和输入值的范围；
(2)输出的形式；
(3)程序所能达到的功能；
(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2．概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
3．详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度应能够按照伪码算法在计算机键盘上直接输入高级程序设计语言程序)；画出函数的调用关系图。
4．调试分析
内容包括：
(1)调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析；
(2)算法的时间复杂性(包括基本操作和其他算法的时间复杂性的分析)和改进设想；
(3)设计过程的经验和体会。
5．用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。
6．测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
7．附录
带注释的源程序。程序文件名的清单。
值得注意的是，实验报告的各种文档资料，要在程序开发的过程中逐渐充实形成，而不是最后补写。
编 写 人： 宋玲
审 核 人： 李晓峰
批 准 人： 李盛恩
编写日期： 20##年12月30日