算法设计与分析实验二分治策略运用练习

1、学 号 算法设计与分析实验报告二学生姓名专业、班级指导教师唐国峰成绩电子与信息工程系2013 年 4 月 15 日实验二：分治策略运用练习一、实验目的本次实验是针对分治策略运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交winrar压缩包，文件名为“算法设计与分析实验二_学号_姓名”，如“算法设计与分析实验二_09290101_张三”。 b 压缩包

2、内为一个“算法设计与分析实验二_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为time new roman，大小为10号字。 c 行间距：单倍行距。（3）提交截止时间：2012年4月29日16:00。三、 实验项目1对用户输入的杂乱无序的数字序列按照由小到大的顺序排序。要求分别运用合并排序和快速排序完成该题目要求。四、实验过程（一） 题目一：对于用户随意输入的7个无序数字，用合并排序的方法，按照从小到大的

3、顺序进行排序。1. 题目分析：将待排序元素分成大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。2. 算法构造：调用三个函数来实现，mergepass用于合并排好序的相邻数组段，具体的合并算法由merge用来实现，mergesort函数为合并算法，调用merge、mergepass函数来实现数的合并排序3. 算法实现#includetemplatevoid mergesort(type a,int n) type*b=new type; int s=1;while(sn)mergepass(a,b,s,n);/将a中的元素合并到数组bs+=s;me

4、rgepass(b,a,s,n);/将b中的元素合并到数组as+=s;templatevoid merge(type c,type d,int l,int m,int r) /合并cl,m和xm+1,r到yl,rint i=l,j=m+1,k=l;while(i=m)&(j=r)if(cim)for(int q=j;q=r;q+)dk+=cq;elsefor(int q=i;q=m;q+)dk+=cq;templatevoid mergepass(type x,type y,int s,int n)/合并大小为s的相邻序列子数组int i=0;while(i=n-2*s) /合并大小为s的相邻

5、2字段数组merge(x,y,i,i+s-1,i+2*s-1);/合并xi,i+s-1和xi+s,i+2*s-1到yi,i+2*s-1i=i+2*s;if(i+sn)/处理剩下的元素少于2smerge(x,y,i,i+s-1,n-1);elsefor(int j=i;j=n-1;j+)yj=xj;void main() int a7,i;printf(请 输 入 7 个 数 字:n);for( i=0;i7;i+)scanf(%d,&ai); mergesort(a,7);printf(最 终 排 序 结 果 为:n);for(int e=0;e7;e+)printf(%dt,ae);prin

6、tf(n);4. 运行结果5. 经验归纳：我主要参考书上的程序来做的，我感觉主要是做好合并数组（二）题目二：对用户输入的无序的数字，按照快速排序方法，由小到大的顺序排序。1. 题目分析：通过一趟扫描，就能确保某个数并以它为基准点的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理，它左右两边的数，直到基准点的左右只有一个元素为止2. 算法构造：定义轴测元素，然后从两端各个和轴测元素比较后放在相应的位置，相比元素一样，将轴测元素放到中间。对排好序的两边，重复上述操作。3. 算法实现#includevoid quicksort(int a,int l,int r) int i,j,t; i

7、=l; j=r; t=al; /轴测元素t为数组最左侧的元素 if(lr) return; while(i!=j) /扫描完，结束时语句 while(aj=t & ji) j-; /如果右侧指针元素比轴测元素大，指针元素左移 if(ji) ai+=aj; while(aii) i+; /如果左侧指针元素比轴测元素小，指针元素右移 if(ji) aj-=ai; ai=t; quicksort(a,l,i-1); /对左边进行排序 quicksort(a,i+1,r); /对右边进行排序void main() int i,f7; printf(请 输 入 7 个 无 序 的 数 字：n); for(i = 0; i 7; i +) scanf(%d,&fi); quicksort(f,0,7);printf(快 速 排 序 后：n); for(i=0;i7;i+) printf(%d ,fi);printf(n);4. 运行结果5. 经验归纳：主要找出轴测元素和两端元素进行比较，依次进行这样就行五、实验总结 通过