2013-2014(2)《算法分析与设计》上机指导书

《算法分析与设计》实验指导书

（适用于计算机科学与技术、软件工程专业）

计算机科学与技术学院

软件教研室 2014.3

目 录

实验一 算法分析 ................................................ 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 <a, a, . . .,an>.

Output: A permutation (reordering) <a’, a’, . . .,an’> of the input sequence such that a’ a’ . . . an’

1

21

2

1

2

四、 编程任务

给定长度为n的一个序列，对其进行插入排序和合并排序

五、 数据输入

随机产生10000以上的数据，放入输入文件input.txt，用来进行排序

六、 结果输出

排序后的结果和两种排序算法的运行时间输出到文件output.txt

七、 实验报告内容

见《算法分析与设计》实验规范。

实验二 分治策略

一、 实验目的及任务

1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；2、分治算法思想解决median问题。

二、 实验环境

c++或java或Turbo c

三、 问题描述

(1) Input: A sequence of n numbers <a, a, . . .,an>.

Output: A permutation (reordering) <a’, a’, . . .,an’> of the input sequence such that a’ a’ . . . 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.

1

21

2

1

2

四、 编程任务

给定长度为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相容。活 …… 此处隐藏：7628字，全部文档内容请下载后查看。喜欢就下载吧 ……