2011-2012(1)《算法分析与设计》上机指导书

PAGEPAGE8《算法分析与设计》实验指导书（适用于计算机科学与技术、软件工程专业）计算机科学与技术学院软件教研室2011-8目录TOC\o"2-2"\u实验一算法分析 3实验二分治策略 4实验三堆排序 5实验四动态规划 6实验五贪心算法 8实验六图算法1-基本图算法 10实验七 图算法2-最小生成树和单源顶点最短路径 12实验八图算法3-所有点对最短路径 14附录一实验规范 15实验一算法分析一、实验目的及任务1、使学生通过插入排序和合并排序的算法实现，理解算法的概念并且通过运行时间比较其时间复杂度。2、体会合并排序的分治方法的三个步骤：分解、递归求解和合并。3、了解渐近记号的意义和初步分析算法复杂性。二、实验环境c++或java或Turboc三、问题描述Input:Asequenceofnnumbers<a1,a2,...,an>.Output:Apermutation(reordering)<a1’,a2’,...,an’>oftheinputsequencesuchthata1’a2’四、编程任务给定长度为n的一个序列，对其进行插入排序和合并排序五、数据输入随机产生10000以上的数据，放入输入文件input.txt，用来进行排序六、结果输出排序后的结果和两种排序算法的运行时间输出到文件output.txt七、实验报告内容见《算法分析与设计》实验规范。实验二分治策略一、实验目的及任务1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；2、分治算法思想解决median问题。二、实验环境c++或java或Turboc三、问题描述(1)Input:Asequenceofnnumbers<a1,a2,...,an>.Output:Apermutation(reordering)<a1’,a2’,...,an’>oftheinputsequencesuchthata1’a2’(2)Input:AsetAofn(distinct)numbersandanumberi,with1≤i≤n.Output:Theelementx∈Athatislargerthanexactlyi-1otherelementsofA.四、编程任务给定长度为n的一个序列，对其进行快速排序和求第i小数五、数据输入A=<13,19,9,5,12,8,7,4,11,2,6,21>六、结果输出将排序结果输出到文件output.txt。如果不存在所要求的第i小数，则输出-1。七、实验报告内容见《算法分析与设计》实验规范。实验三堆排序一、实验目的及任务1、了解堆的性质；2利用堆构成一个优先队列，并实现相关的函数功能；3为图算法做好准备。二、实验环境c++或java或Turboc三、问题描述ApriorityqueueisadatastructureformaintainingasetSofelements,eachwithanassociatedvaluecalledakey.Amax-priorityqueuesupportsthefollowingoperations..INSERT(S,x)insertstheelementxintothesetS.ThisoperationcouldbewrittenasS←S∪{x}..MAXIMUM(S)returnstheelementofSwiththelargestkey..EXTRACT-MAX(S)removesandreturnstheelementofSwiththelargestkey..INCREASE-KEY(S,x,k)increasesthevalueofelementx'skeytothenewvaluek,whichisassumedtobeatleastaslargeasx'scurrentkeyvalue.四、编程任务编程建立最大堆，构造优先队列并实现以上的相关操作。五、数据输入A=<15，13，9，5，12，8，7，4，0，6，2，1>六、结果输出执行INSERT(A,10)，EXTRACT-MAX(A)，将结果输出到文件output.txt。七、实验报告内容见《算法分析与设计》实验规范。实验四动态规划一、实验目的及任务掌握动态规划算法的基本步骤：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。熟悉最长公共子序列问题的算法，设计一个算法解决编辑距离问题。二、实验环境c++或java或Turboc三、问题描述

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)。五、数据输入由文件input.txt提供输入数据，X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}。由文件input.txt提供输入数据。文件的第1行是字符串A，文件的第2行是字符串B。A:fxpimuB:xwrs六、结果输出1程序运行结束时，将编程计算出的最长公共子序列长度以及最长公共子序列输出到文件output.txt中。2程序运行结束时，将编辑距离d(A,B)输出到文件output.txt的第1行中。七、实验报告内容见《算法分析与设计》实验规范。实验五贪心算法一、实验目的及任务1、掌握贪心算法的基本性质。2贪心算法与动态规划的区别。3贪心算法解决活动安排问题和背包问题。二、实验环境c++或java或Turboc三、问题描述

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相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。20-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。四、编程任务1在所给的活动集合中选出最大的相容活动子集合。2计算背包问题/0-1背包问题背包的价值五、数据输入1i1234567891011si130535688212fi45678910111213142W={10,100,120}V={10,20,30}C=50六、结果输出1、将编程计算出的最长最大活动安排结果输出到文件output1.txt。2、将编程计算出的背包价值输出到文件output2.txt。七、实验报告内容见《算法分析与设计》实验规范。实验六图算法1-基本图算法一、实验目的及任务1、掌握图邻接表的存储方法；2、掌握深度优先遍历算法(DFS)；3、利用深度优先遍历的timestamps进行拓扑排序或计算有向图的强连通分支；二、实验环境c++或java或Turboc三、问题描述GivenG=(V,E)InDFS,edgesareexploredoutthemostrecentlydiscoveredvertexvthatstillhasunexplorededgesleavingit.Whenv'sedgeshavebeenexplored,thesearch"backtracks"toexploreedgesleavingthevertexfromwhichvwasdiscovered.Besidescreatingadepth-firstforest,DFSalsotimestampseachvertex.Eachvertexvhastwotimestamps:thefirsttimestampd[v]recordswhenvisfirstdiscovered,andthesecondonef[v]recordswhenthesearchfinishesexaminingv'sadjacencylist.Atopologicalsortofadirectedacyclicgraph(DAG)G=(V;E)isalinearorderingofallitsverticessuchthatifGcontainsanedge(u;v),thenuappearsbeforevintheordering(ifthegraphiscyclic,thennolinearorderingispossible).Astronglyconnectedcomponent(SCC)ofadirectedgraphG=(V;E)isamaximalsubsetofverticesCVsuchthatu,vC,wehaveu→vandv→u.四、编程任务1、深度优先遍历；2、利用深度优先遍历的timestamps进行拓扑排序；3、利用深度优先遍历的timestamps进行有向图的强连通分支；五、数据输入六、结果输出1、将编程计算出深度优先遍历结果输出到文件output1.txt；2、将编程进行拓扑排序结果输出到文件output2.txt；3、将编程进行有向图的强连通分支的结果输出到文件output3.txt。七、实验报告内容见《算法分析与设计》实验规范。实验七图算法2-最小生成树和单源顶点最短路径一、实验目的及任务1、应用优先队列求最小生成树的Prim算法，了解其中的贪心算法的设计思想；2、应用优先队列求单源顶点的最短路径Dijkstra算法，了解贪心算法的设计思想，并掌握松弛技巧。二、实验环境c++或java或Turboc三、问题描述1、Givenaconnected,undirectedgraphG=(V,E),where(u,v)∈Ehasaweightw(u,v).WeintendtofindanacyclicsubsetTEthatconnectsalltheverticesandwhosetotalweightw(T)=isminimized.SinceTisacyclicandconnectsallvertices,itmustbeatree,calledspanningtree.TheproblemtofindsuchTiscalledminimumspanningtree(MST)problem.2、Dijkstra'salgorithmsolvesthesingle-sourceshortest-pathsproblemonaweighted,directedgraphG=(V,E)forthecaseinwhichalledgeweightsarenonnegative.Dijkstra'salgorithmmaintainsasetSofverticeswhosefinalshortest-pathweightsfromthesourceshavealreadybeendetermined.Thealgorithmrepeatedlyselectsthevertexu∈V–Swiththeminimumshortest-pathestimate,addsutoS,andrelaxesalledgesleavingu.四、编程任务对于给定的赋权图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.txt79122816102714231665257524741834125422输出文件示例output.txt252将编程计算出单源顶点最短路径结果输出到output2.txt。七、实验报告内容见《算法分析与设计》实验规范实验八图算法3-所有点对最短路径一、实验目的及任务1、掌握Matrixmultiplication和Floyd-Warshallalgorithm的实现；2、了解这两种算法的不同；3、进一步了解所有点对最短路径问题中的动态规划设计思想。二、实验环境c++或java或Turboc三、问题描述Givenaweighted,directedgraphG=(V,E),foranyu,v∈V,findashortestpathfromutov.四、编程任务对于给定的赋权有向图G，编程计算图的所有点对的最短路径。五、数据输入六、结果输出将编程计算出的所有点对的最短路径输出到文件output.txt。七、实验报告内容见《算法分析与设计》实验规范《算法分析与设计》实验规范一、实验课的意义

实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变"活"，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的"小"算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。二、实验步骤

常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然算法分析与设计课程中的实验题目的远不如从实际问题中的复杂程度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目：1．问题分析和任务定义在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。2．逻辑设计和详细设计在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。3．编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。然而，不管你是否写出编码的程序，在上机之前，认真的静态检查是必不可少的。静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过对程序深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。4．上机准备和上机调试上机准备包括以下几个方面：

(1)注意同一高级语言文本之间的差别。

(2)熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。(3)掌握调试工具，考虑调试方案，设计测试数据