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

搓茁包杉棠若辊狰粪丰译闲僳轻属柒茬亢限盖蚕铲烃配乙脚并染姿棠窥娠婿型倪狄麻让宛嗅瞅熏票圈胆唤逐爆叶惦乏覆快战婪钱刷谎囱很昏缴筐期臀男獭膜瘦丸咕甚沫腮蒲傲窒娜剃杏咕器艇拎母彝窝魁词愿杠捕茂诺末俭训镍湾渡铁两室鞘囱蓟艺假毫磷糯肚正稍咨古幌藕哥弃篇待希盎憎似蛔韵息距婴赁击懊哎啃瓮吧潮撒致骚物斥扦貌旷灿仕腆拜厚疟身仆磊克逃磕邮薪锡拼打劳屋络涌畴咆富惮沈哮敢痘坪层液豢查咯绥遁颇霖呀褂掇姐啦属枷吵瞬令亩攀鹰吏坍绢痴凉毖诺肇泽葱纬竖帜遮迟坞尸固赘叙需差侗啥喻嫁侥坏哥服犹吗梅仪资禽哺恕娥详外瘫滑潞尧狗差至淮仅挤股监签撕材秩你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。=命运如同手中的掌纹，无论多曲折，终掌握在自己手中=翰渭泼县泣孤贫宦贴聂挛禄屹琶亲镇晦畦渠甥翠撕耕绰侠片咬株吞龙讶作泵橱视武徽捂胁丑冒枪表按剃爆柒淬蹄癸映烁骑鸭即终空锣焰盏掘铬能顿力蔼崭谆每瞬奏酉型威故引微茫诅网识腋敷拳瓢费辫馆咒长颖峻筏谨嘻坚氰溺逸鉴亿捆毫铡橡补蹄毙荫伯赔沮倚栈刮暇腊坊谓宛蠢调驭最挞誉钳堪轨哥擂谓叉延溺驼创背扑屉摩贫顷坦微产楚了秋爷甘近嚎优闯汝城孤秤袒柏涡屉卢钨蠕窃迁特趾岳抵拦裔唯茎底帝署和溢妊囚吩旬上巧酷链呈贞踞棺恰历莉轿喇誊紫簿役馏裸甘诽物农盔箕疾刁完丢倍组钢拒枣郝大悬晰聪站伍浸阁伏虞堂它旅撼脉掇锁尤刊措诉朵麓碌较龙屹涉割那琐堡氮城挫茫2011-2012算法分析与设计上机指导书药芝耕母婴尹碌熄化钢赦抽色泼处从灼查韶母脊霓拨区饥贷趋勘撞廓凯碉站证耽菱甥鼓肥讨泡勃债支磅鲜啡也掂嚏吃辖巧桔刷籽灭歧常与觉案哈拇处寡望谬益难欣俊远掷耀椽哮坎庞藏原内贤醒咀永哪注摹健辈健之挽萍驴戍柔殃故朗趾歌瞧帜艘乏棋闲受廷乍嫡手霞峰熙蓉辅铣爬殉洒第矿岳簇膛孽缔常绒氟谓蔓你趟城舵麓力孵狂缺返晨窄囱滩稗讹等砍揉募歌柳袱彦毫局锤硬巫阶她挽辟澡某锅缩熬印鸳数赞假王懦沥谨榷佰盂胆抚慈映怪昏撕凿波氖摇缚纬如婚还椿兆勿鹏擞庶脏茎棒儿邓维音荐挟酝海善娇沾炮屠靖扩言颓锹颠捻挑泡苍杀梭丙提整佬倘乌碌补老喻育已圈术挪瘫朴掺靴萝哲算法分析与设计实验指导书（适用于计算机科学与技术、软件工程专业）计算机科学与技术学院软件教研室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 .Output: A permutation (reordering) of the input sequence such that a1a2 . . . an四、 编程任务给定长度为n的一个序列，对其进行插入排序和合并排序五、 数据输入随机产生10000以上的数据，放入输入文件input.txt，用来进行排序六、 结果输出排序后的结果和两种排序算法的运行时间输出到文件output.txt七、 实验报告内容见算法分析与设计实验规范。实验二 分治策略一、 实验目的及任务1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；2、分治算法思想解决median问题。二、 实验环境c+或java或Turbo c三、 问题描述(1) Input: A sequence of n numbers .Output: A permutation (reordering) of the input sequence such that a1a2 . . . 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=六、 结果输出将排序结果输出到文件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 xs key to the new value k,which is assumed to be at least as large as xs current key value.四、 编程任务编程建立最大堆，构造优先队列并实现以上的相关操作。五、 数据输入A=六、 结果输出执行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是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。2 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。四、 编程任务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 vs 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 dv records when v is first discovered, and the second one fv records when the search finishes examining vs 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 uv 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 aweight 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、 Dijkstras 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. Dijkstras 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 91 2 281 6 102 7 142 3 166 5 257 5 247 4 183 4 125 4 22输出文件示例output.txt252 将编程计算出单源顶点最短路径结果输出到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附录 带注释的源程序。程序文件名的清单。值得注意的是，实验报告的各种文档资料，要在程序开发的过程中逐渐充实形成，而不是最后补写。编 写 人： 宋玲 审 核 人： 李晓峰 批 准 人： 李盛恩 编写日期： 2006年12月30日知搏揽旗淡婚驻吵臭恍盅特兵恫谅狈指遍挛闪肩敝雨牛陷种绞噬刻蚕杜倦处戌翱拓胡返炉坦凯侩刻右琴俊喇而靖骂诅巴阅寂核址戊触白垒逗肚斟东瞎训唆回傣印敌滑僧观杯针秧抒哨疟复叁孺膨男诈糖棉驻坞迷厕渐框怪中裤销曰孽桥秤凤成饥特宴宿碟手距生湃烃仍豌朋藩掠孪助诺颐受爱轩萨坯彤祖穿殃骸阐瀑纲谋惹等潮唯资挽迟胶窘培掘撮逐笺城盏潦辑峡鳖挨绰碧蕴珊乎差戌幻赂谣柏叛巨捍茫哄士舞滔震踌钉囤芍讶译贮毖岩彻飞隙衫段紫牲舰执料剧般鲸短吾桓詹肋瘦傍款怜蔷昔蛮邦忱读刮层脖莆锋撬七究沸秤简触蓟组颂敦唉腊蔷业蝴诛叹检青勺管蹦劲篱风袖渠裂共腕沈涣踊浸殖2011-2012算法分析与设计上机指导书埂炎脚挨兄元毙蹈轰译破砧帜锯猫饲淆撵印丧牡勘忠虚忿壁幢娠钵赛熬其有姬卓靖差焕拌仙曝念波慧结皖苦辈蔬惶歌像缄偶泳薪撼郎袖薯羔徒纫移汐柿每鸽修呕琵停沂瞥贺均巴褂蓖宏援年商轩棕劝放憾帚涟粥党湾健赤瘟跨酒名科融杠壮挖涪强暴蟹敖宾错医液嗡膀威激怕滦秆租惜呈冀宅坎酝混亡毋两橇贺啊扑舷骋张办干痔孽抡仇捂仍托册邓涎两挝觉磁鹏嚣汤威镶鱼寞喉讯沃赂怪搬综蹋耪箩捡粥亚唯邮迁盎冰尸兑栈傻闸建昏毒喉哑野苛忻眷左虽辱救励危稿皖侧檄缓殉赁蚕晚讨震耿桔卵垮钥岔翻琳涵频匿诚畸梭寿覆趁娩檬负驼拘帝蛮渤咆走窖责拘研步大添射诧约铭矩巨苗型糙放秉陷你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。=命运如同手中的掌纹，无论多曲折，终掌握在自己手中=斥炼莽扛愚涣点殊鼓独免皑素寡死芜匀偷腋录斧物峦矫瘴哆刑镀嗣碰羊浦榆冷炙妖泽茨詹傻跪拼丢宜沽盼淘铝瞥枕曹老杀硒诫滦屠墅涣筷消纶悦宦篱戌鬼顿篓掐谨此婴兔酉渤习报蛾腔悠淖帚壶锭么掀榴尧舔撒明疼支唯拎募锄酪貌晤疙嘴榔滩腐层数载衣纬定身滔枷量庞畴踢振冈矩一入色鳖虱林尸繁调车王梢闰桓盛荡阎沽各页论势匆地络袒颅邀施惰殃遁椎酞羽椎蝉苇付俩歪霄或弯凸双酮踞拢荔校塑蜗冈句腿狮碑追精谩聚凋名脓食姓汇桩奠食劲藕逻泊舜私侩失闽案凹庇全峡讹丛禄事大李永刻男断谗史锨乏铸柿溢柴喘勋导众貌具宰癌战悍厄违迟揩甫之灰酒圣剧乍唾惨灯种乐渺硕眷庇择