实验2 分治法算法设计.docVIP

《算法分析与设计》实验报告 实验2 分治法算法设计 姓名 XXX 学号 XXX 班级 XXXXXX 时间：XXXX-XX-XX 地点：XXX 同 组 人：无 指导教师：XXX 实验目的 掌握分治法算法设计的一般思想和方法。 理解并掌握二分查找、归并分类、快速分类算法。 能熟练运用分治法求解问题。 实验中所准备的数据是有代表性的。 实验内容 写一个顺序查找算法，将其与二分查找算法一起转换成程序，上机验证。 选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。 归并分类、快速分类算法转换成程序并验证之。 选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。 准备一定规模的数据集用于实验。此数据集越大越有得于验证算法，可以考虑最终的数据个数超过10000个。 编写归并分类、快速分类程序，将上数据集中的数据分类。可以使用较少的数据调试程序时。 用规模从小到大的数据集运行上述程序，统计它们的运行时间，并作对比分析。 编写顺序查找、二分查找程序。 将查找程序与分类程序结合起来，用不同规模的数据集运行，统计程序运行时间。 实验环境 硬件： Intel(R) Pentium(R) CPU RAM:4G 软件：Myeclipse2013 实验前准备 算法设计： （1）分治策略的抽象化控制 Procedure DANDC(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＜q// Return(COMBINE(DANDC(p,m),DANDC(m+1,q))) Endif endDANDC （2）二分检索算法 Procedure BINSRCH(A,n,x,j) //给定一个按非降次序排列的元素数组A(1:n)，n≥1，判断x是否出现。// //若是，置j，使得x=A(j)，若非，j=0// Integer low, high, mid, j, n ; low←1;high←n while low≤high do mid←int((low+high)/2) case :xA(mid): high←mid-1 :XA(mid): low←mid+1 :else: j←mid; return Endcase Repeat j←0 endBINSRCH （3）归并分类算法 Procedure MERGESORT(low, high) //A(low : high)是一个全程数组，它含有high-low+1≥0个待分类的元素// Integer low, high; If low high then mid ← int((low+high)/2) //求这个集合的分割点// call MERGESORT(low, mid) //将一个子集合分类// call MERGESORT(mid+1, high)//将另一个子集合分类// CALL MERGE(low,mid,high) //归并两个已分类的子集合// Endif endMERGESORT Procedure MERGE(low, mid, high) //A(low : high)是一个全程数组，它含有两个放在A（low : mid）和A（mid+1 : high）中的已分类的子集合。目标是将这两个已分类的集合归并成一个集合，并存放到A(low : high)中// //使用一个辅助数组B(low : high)// Integer h, I, j, k, low, mid, high; //low≤midhigh// Global A(low : high); local B(low : high) 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 hmid then for k←j to high do //处理剩余的元素// B(i) ←A(k);i←i+1 repeat Else for k←h to mid do