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

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

ID:58914219

大小:1.40 MB

页数:9页

时间:2020-10-26

《算法设计与分析》实验二.doc_第1页
《算法设计与分析》实验二.doc_第2页
《算法设计与分析》实验二.doc_第3页
《算法设计与分析》实验二.doc_第4页
《算法设计与分析》实验二.doc_第5页
资源描述:

《《算法设计与分析》实验二.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。