《算法设计与分析》实验二.doc

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

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

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

3、用户输入）四、实验过程（一）题目一：对用户输入的杂乱无序的数字序列按照由小到大的顺序排序：快速排序题目分析快速排序是冒泡排序的改进，以一组杂乱无序的数字最左边为枢轴记录的关键字，最右侧指针若比关键字大，则右侧指针左移，若出现比它小的交换两指针指向数的排序完成。算法实现#include#includevoidquickSort(inta[],intl,intr){inti,j,t;i=l;j=r;t=a[l];//枢轴元素t为数组最左侧的元素if(l>r)return;while(i!=j)//i往右移动j往左移动当指向同一位置

4、时扫描完成{while(a[j]>=t&&j>i)j--;//如果右侧指针元素比轴测元素大，指针元素左移if(j>i)//确保i在j左边a[i++]=a[j];//当右侧指针元素比轴测元素小时，交换两指针指向数的位置while(a[i]<=t&&j>i)i++;//如果左侧指针元素比轴测元素小，指针元素右移if(j>i)//确保i在j左边a[j--]=a[i];//当左侧指针元素比轴测元素大时，交换两指针指向数的位置}a[i]=t;quickSort(a,l,i-1);//对左边进行排序quickSort(a,i+1,r);//对右边进行排序}voidmain()

5、{inti,n,f[100];printf("请输入要比较数字的个数：");scanf_s("%d",&n);for(i=0;i

6、列按照由小到大的顺序排序：合并排序题目分析合并排序的基本思想是：将待排序的元素分成大小大相同的两个子集合，分别对两个子集合进行排序，最终将排序好的子集合合并成所要求的拍好序的集合。算法构造核心代码来自书上：MergePass(Typex[],Typey[],ints,intn)//合并大小为s的相邻序列子数组Merge(Typec[],Typed[],intl,intm,intr)//合并c[l,m]和x[m+1,r]到y[l,r]算法实现#include#includetemplatevoidMerge

7、Sort(Typea[],intn){Type*b=newType[n];ints=1;while(svoidMerge(Typec[],Typed[],intl,intm,intr)//合并c[l,m]和x[m+1,r]到y[l,r]{inti=l,j=m+1,k=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j])d[k++]=c[i++

8、];els