资源描述：
《2011-2012《算法分析与设计》上机指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《算法分析与设计》实验指导书（适用于计算机科学与技术、软件工程专业）计算机科学与技术学院软件教研室2011-818目录实验一算法分析3实验二分治策略4实验三堆排序5实验四动态规划6实验五贪心算法8实验六图算法1-基本图算法10实验七图算法2-最小生成树和单源顶点最短路径12实验八图算法3-所有点对最短路径14附录一实验规范1518实验一算法分析一、实验目的及任务1、使学生通过插入排序和合并排序的算法实现，理解算法的概念并且通过运行时间比较其时间复杂度。2、体会合并排序的分治方法的三个步骤：分解、递归求解和合并。3、了解渐近记号的意义和初步分析算法复杂性。二、实验环
2、境c++或java或Turboc三、问题描述Input:Asequenceofnnumbers.Output:Apermutation(reordering)oftheinputsequencesuchthata1’£a2’£...£an’四、编程任务给定长度为n的一个序列，对其进行插入排序和合并排序五、数据输入随机产生10000以上的数据，放入输入文件input.txt，用来进行排序六、结果输出排序后的结果和两种排序算法的运行时间输出到文件output.txt七、实验报告内容见《算法分析与设计》实验规
3、范。18实验二分治策略一、实验目的及任务1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；2、分治算法思想解决median问题。二、实验环境c++或java或Turboc三、问题描述(1)Input:Asequenceofnnumbers.Output:Apermutation(reordering)oftheinputsequencesuchthata1’£a2’£...£an’(2)Input:AsetAofn(distinct)numbersandanumberi,wi
4、th1≤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。七、实验报告内容见《算法分析与设计》实验规范。18实验三堆排序一、实验目的及任务1、了解堆的性质；2利用堆构成一个优先队列，并实现相关的函数功能；3为图算法做好准备。二、实验环境c++或java
5、或Turboc三、问题描述ApriorityqueueisadatastructureformaintainingasetSofelements,eachwithanassociatedvaluecalledakey.Amax-priorityqueuesupportsthefollowingoperations..INSERT(S,x)insertstheelementxintothesetS.ThisoperationcouldbewrittenasS←S∪{x}..MAXIMUM(S)returnstheelementofSwiththelargestkey
6、..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
7、)，将结果输出到文件output.txt。七、实验报告内容见《算法分析与设计》实验规范。18实验四动态规划一、实验目的及任务1、掌握动态规划算法的基本步骤：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。2、熟悉最长公共子序列问题的算法，设计一个算法解决编辑距离问题。二、实验环境c++或java或Turboc三、问题描述 1若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2
8、,…,k有
