《算法设计及分析实验指导书》由会员分享，可在线阅读，更多相关《算法设计及分析实验指导书（8页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验指导书课程编号：09110112课程名称：算法设计与分析英文名称：Algorithms Design and Analysis适应专业：计算机科学与技术执 笔 人：沙莎实验指导书名称：计算机算法基础实验一 分治法1、 基本要求1）了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2）掌握分治法的一般控制流程DanC(p,q) global n，A1:n; intege
2、r m,p,q; / 1pqn if Small(p,q) then return G(p,q); else m=Divide(p,q); / pmq return Combine(DanC(p,m),DanC(m+1,q); endifend DanC3）实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。2、 实验内容1） 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2） 输入10组相同的数据，验证排序结果和完成排序的比较次数。3） 与复杂性函数所计算的比较次数比较。4） 用表格列出比较结果。5） 给出文字分析。3、 归并排序算法和快
3、速排序算法归并排序算法procedure MERGESORT(low，high) /A(low；high)是一个全程数组，它含有high-low+10个待排序的元素/ integer low，high； if lowmid then for kj to high do /处理剩余的元素/ B(i) A(k)；ii+1 repeat else for kh to mid do B(i) A(k)；ii+1 repeat endif 将已归并的集合复制到A end MERGE快速排序算法QuickSort(p,q) /将数组A1:n中的元素 Ap, Ap+1, , Aq按不降次序排列， 并假定An
4、+1是一个确定的、且大于 A1:n中所有的数。/ int p,q; global n, A1:n; if pq then j=Partition(p, q+1); / 划分后j成为划分元素的位置 QuickSort(p,j-1); QuickSort(j+1,q); endif end QuickSortprocedure PARTITION(m，p) /退出过程时，p带着划分元素所在的下标位置。/ integer m，p，i；global A(m：p-1) vA(m)；im /A(m)是划分元素/ loop loop ii+1 until A(i)v repeat /i由左向右移/ loop
5、 pp-1 until A(p)v repeat /p由右向左移/ if icu then exit endif X(i) 1 cucu-W(i) repeat if in then X(i) cu/ W(i) endif end GREEDY-KNAPSACKprocedure prim(G,)status“unseen” / T为空 status1“tree node” / 将1放入Tfor each edge(1,w) do statusw“fringe” / 找到T的邻接点 dadw 1; /w通过1与T建立联系 distw weight(1,w) /w到T的距离 repeatwhil
6、e statust “tree node” do pick a fringe u with min distw / 选取到T最近的节点 statusu“tree node” for each edge(u,w) do 修改w和T的关系 repeatrepeat实验三 动态规划1、 基本要求1） 理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新
7、的算法设计方法动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2） 理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。us 初始值，uj第j段的最优值。3） 一般方法 找出最优解的性质，并刻画其结构特征； 递归地定义最优值（写出动态规划方程）； 以
8、自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。2、 实验内容1） 编程实现多段图的最短路经问题的动态规划算法。2） 图的数据结构采用邻接表。3） 要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4） 验证算法的时间复杂性。3、 多段图算法procedure FGRAPH(E，k，n，P) /输入是按段的顺序给结点编号的，有n个结点 的k段图。E是边集，c(i，j)是边的成本。 P(1：k)是最小成本路径。/ real COST(n)，integerD(n一1)，P(k)，r，j，k，n COST(n) 0 for jn-1to 1by1do /计算COST(j)/ 设r是一个这样的结点，(j，r)E且使c(j，r)+COST(r)取最
