内容发布更新时间 : 2024/11/5 10:53:28星期一 下面是文章的全部内容请认真阅读。

《算法设计与分析》实验指导书

课程编号：09110112

课程名称：算法设计与分析

英文名称：Algorithms Design and Analysis

适应专业：计算机科学与技术 执 笔 人：沙莎

实验指导书名称：计算机算法基础

实验一 分治法

1、 基本要求

1）了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1

2）掌握分治法的一般控制流程 DanC(p,q)

global n，A[1:n]; integer m,p,q; // 1?p?q?n if Small(p,q) then return G(p,q); else m=Divide(p,q); // p?m

return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC

3）实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

2、 实验内容

1） 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。

2） 输入10组相同的数据，验证排序结果和完成排序的比较次数。 3） 与复杂性函数所计算的比较次数比较。 4） 用表格列出比较结果。 5） 给出文字分析。

3、 归并排序算法和快速排序算法 归并排序算法

procedure MERGESORT(low，high) //A(low；high)是一个全程数组，它含 有high-low+1≥0个待排序的元素// integer low，high； if low

1

then mid← ， //求这个集合的分割点// call MERGESORT(low，mid) //将一个子集合排序//

call MERGESORT(mid+1，high) //将另一个子集合排序 call MERGE(low，mid，high) //归并两个已排序的子集合// endif end MERGESORT 归并两个已排序的集合

procedure MERGE(low，mid，high) //A(low：high)是一个全程数组// //辅助数组B(low；high)// integer h，i，j，k； h←low；i←low；j←mid+1；

while h≤mid and j≤high do //当两个集合都没取尽时// if A(h)≤A(j) then B(i) ←A(h)；h←h+1 else B(i) ←A(j)；j←j+1 endif i←i+1 repeat if h>mid then

for k←j to high do //处理剩余的元素// B(i) ←A(k)；i←i+1 repeat

else for k←h to mid do B(i) ←A(k)；i←i+1 repeat endif

将已归并的集合复制到A end MERGE

快速排序算法 QuickSort(p,q) //将数组A[1:n]中的元素

A[p], A[p+1], ? , A[q]按不降次序排列， 并假定A[n+1]是一个确定的、且大于 A[1:n]中所有的数。// int p,q; global n, A[1:n]; if p

j=Partition(p, q+1); // 划分后j成为划分元素的位置 QuickSort(p,j-1);

2

QuickSort(j+1,q); endif end QuickSort

procedure PARTITION(m，p)

//退出过程时，p带着划分元素所在的下标位置。// integer m，p，i；global A(m：p-1) v←A(m)；i←m //A(m)是划分元素// loop

loop i←i+1 until A(i)≥v repeat //i由左向右移// loop p←p-1 until A(p)≤v repeat //p由右向左移// if i

then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)换位// else exit endif repeat

A(m) ←A(p)；A(p) ←v //划分元素在位置p// End PARTITION

实验二 贪心法

1、 基本要求 1） 优化问题

有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。 2） 贪心法求优化问题

算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。

2）一般方法

① 根据题意，选取一种量度标准。 ② 按这种量度标准对这n个输入排序

③ 依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

procedure GREEDY(A，n) /*贪心法一般控制流程*/ //A(1：n)包含n个输入//

solutions←φ //将解向量solution初始化为空／ for i←1 to n do x←SELECT(A)

3