《算法分析与设计》上机指导书.doc

《》实验指导书 （适用于计算机科学与技术、专业） 计算机科学与技术学院 教研室 20 目 录 实验一 3 实验二 4 实验三 5 实验四 6 实验五 8 实验六 10 实验七 12 实验 图算法3-所有点对最短路径 14 附录一 实验规范 15 实验一 一、 实验目的及任务 二、 实验环境 三、 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’ 四、 、 input.txt，用来进行排序 六、 output.txt 七、 实验 分治策略 一、 实验目的及任务 二、 实验环境 三、 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. 四、 五、 、 output.txt。如果不存在所要求的第i小数，则输出-1。 七、 实验 堆排序 一、 实验目的及任务 二、 实验环境 三、 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 xs key to the new value k, which is assumed to be at least as large as xs current key value. 四、 编程任务 编程建立最大堆，构造优先队列并实现以上的相关操作。 五、 、 INSERT(A, 10)，EXTRACT-MAX(A)，将结果输出到文件output.txt。 七、 实验 动态规划 一、 实验目的及任务 二、 实验环境 三、 ??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)。 四、 、 、 、 实验 贪心算法 一、 实验目的及任务 二、 实验环境 三、