实验 分治法算法设计

《实验 分治法算法设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验报告实验2分治法算法设计姓名XXX学号XXX班级XXXXXX时间：XXXX-XX-XX地点：XXX同组人：无指导教师：XXX实验目的a)掌握分治法算法设计的一般思想和方法。b)理解并掌握二分查找、归并分类、快速分类算法。c)能熟练运用分治法求解问题。d)实验中所准备的数据是有代表性的。实验内容a)写一个顺序查找算法，将其与二分查找算法一起转换成程序，上机验证。b)选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。c)归并分类、快速分类算法转换成程序并验证之。d)选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。e

2、)准备一定规模的数据集用于实验。此数据集越大越有得于验证算法，可以考虑最终的数据个数超过10000个。f)编写归并分类、快速分类程序，将上数据集中的数据分类。可以使用较少的数据调试程序时。g)用规模从小到大的数据集运行上述程序，统计它们的运行时间，并作对比分析。h)编写顺序查找、二分查找程序。i)将查找程序与分类程序结合起来，用不同规模的数据集运行，统计程序运行时间。实验环境硬件：Intel(R)Pentium(R)CPURAM:4G软件：Myeclipse2013实验前准备1、算法设计：（1）分治策略的抽象化控制ProcedureDANDC(p,q)1

3、8Globaln,A(1:n);integerm,p,q//1≤p≤q≤n//IfSMALL(p,q)Thenreturn(G(p,q))Elsem←DIVIDE(p,q)//p≤m＜q//Return(COMBINE(DANDC(p,m),DANDC(m+1,q)))EndifendDANDC（2）二分检索算法ProcedureBINSRCH(A,n,x,j)//给定一个按非降次序排列的元素数组A(1:n)，n≥1，判断x是否出现。////若是，置j，使得x=A(j)，若非，j=0//Integerlow,high,mid,j,n;low←1;high

4、←nwhilelow≤highdomid←int((low+high)/2)case:xA(mid):low←mid+1:else:j←mid;returnEndcaseRepeatj←0endBINSRCH（3）归并分类算法ProcedureMERGESORT(low,high)//A(low:high)是一个全程数组，它含有high-low+1≥0个待分类的元素//Integerlow,high;Iflow

5、SORT(low,mid)//将一个子集合分类//callMERGESORT(mid+1,high)//将另一个子集合分类//CALLMERGE(low,mid,high)//归并两个已分类的子集合//EndifendMERGESORTProcedureMERGE(low,mid,high)//A(low:high)是一个全程数组，它含有两个放在A（low:mid）和A（mid+1:high）中的已分类的子集合。目标是将这两个已分类的集合归并成一个集合，并存放到A(low:high)中////使用一个辅助数组B(low:high)//Integerh,I

6、,j,k,low,mid,high;//low≤midmidthenfork←jtohighdo//处理剩余的元素//B(i)←A(k);i←i+1repeatElsefork←htomiddoB(i)←A(k);i←i+1

7、repeatendiffork←lowtohighdo//将已归并的集合复制到A//A(k)←B(k)repeatendMERGE（4）改进的归并分类算法ProcedureMERGESORT1(low,high,p)//利用辅助数组LINK(low:high)将全程数组A(low:high)按降序分类。LINK中的值表示按分类次序给出A的下标的表，并把p置于指示这表的开始处//GlobalA(low:high),LINK(low:high)Ifhigh-low+1<16ThencallINSERTIONSORT(A,LONK,low,high,p)Els

8、emid←int((low+high)/2)callMERGESORT(low,