《《算法设计与分析》实验二》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验二（9页珍藏版）》请在金锄头文库上搜索。
1、学号1421050102算法设计与分析实验报告二学生姓名Cherish专业、班级地 理指导教师唐 国 峰成绩计算机与信息工程学院软件工程系2017 年 3 月 28 日实验二：分治策略运用练习一、实验目的本次实验是针对分治策略运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4 提交说明：（ 1）电子版提交说明：a 需要提交Winrar 压缩包，文件名为“算法设计与分析实验二_学号 _姓名”，如“
2、算法设计与分析实验二_09290101_ 张三”。b压缩包内为一个“ 算法设计与分析实验二其下为两个文件夹，一个文件夹命名为“源程序”报告电子版” 。其下分别放置对应实验成果物。_学号 _姓名”命名的顶层文件夹，另一个文件夹命名为“实验（ 2）打印版提交说明：a 不可随意更改模板样式。b 字体：中文为宋体，大小为10 号字，英文为Time New Roman ，大小为10 号字。c 行间距：单倍行距。（ 3）提交截止时间： 2017 年 4 月 11 日 16:00。三、 实验项目1对用户输入的杂乱无序的数字序列按照由小到大的顺序排序。要求分别运用合并排序和快速排序完成该题目要求。2棋盘覆盖问
3、题。 （要求N 可由用户输入）四、实验过程（一）题目一：对用户输入的杂乱无序的数字序列按照由小到大的顺序排序：快速排序题目分析快速排序是冒泡排序的改进，以一组杂乱无序的数字最左边为枢轴记录的关键字，最右侧指针若比关键字大，则右侧指针左移，若出现比它小的交换两指针指向数的排序完成。算法实现#include#includevoid quickSort(int a,int l,int r)int i,j,t;i=l; j=r;t=al;/ 枢轴元素t 为数组最左侧的元素if(lr)return;while(i!=j)/ i 往右移动j 往左移动当指向同一位置时扫描完成while(aj=t & ji)
4、j-;/ 如果右侧指针元素比轴测元素大，指针元素左移if(ji)/ 确保 i 在j 左边ai+=aj; / 当右侧指针元素比轴测元素小时，交换两指针指向数的位置 while(aii)i+;/ 如果左侧指针元素比轴测元素小，指针元素右移if(ji)/ 确保 i 在j 左边aj-=ai;/ 当左侧指针元素比轴测元素大时，交换两指针指向数的位置ai=t;quickSort(a,l,i-1);/ 对左边进行排序quickSort(a,i+1,r);/ 对右边进行排序void main()int i,n,f100;printf( 请输入要比较数字的个数：n);scanf_s(%d,&n);for(i =
5、 0; i n; i +)printf( 请输入第 %d个数字： n,i+1);scanf_s(%d,&fi);quickSort(f,0,n-1);printf( 快速排序的结果是：n);for(i=0;in;i+)printf(%d ,fi);printf(n);system(pause);getchar();运行结果经验归纳结合以前学的数据结构及应用算法，较容易理解。题目二：对用户输入的杂乱无序的数字序列按照由小到大的顺序排序：合并排序题目分析合并排序的基本思想是：将待排序的元素分成大小大相同的两个子集合，分别对两个子集合进行排序，最终将排序好的子集合合并成所要求的拍好序的集合。算法构造
6、核心代码来自书上：MergePass(Type x,Type y,Merge(Type c,Type d,intl,intm, intr)ints, int/ 合并 cl,mn) / 合并大小为和xm+1,r 到yl,rs的相邻序列子数组算法实现#include#includetemplatevoid MergeSort(Type a,int n)Type*b=new Typen;int s=1;while(sn)MergePass(a,b,s,n);/ 将a中的元素合并到数组bs+=s;MergePass(b,a,s,n); / 将 b中的元素合并到数组as+=s;templatevoid
7、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的相邻 2字段数组Merge(x,y,i,i+s-1,i+2*s-1);/ 合并 xi,
8、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 a100,i,n;printf( 请输入要进行合并排序的数字的个数:n);scanf_s(%d,&n);for( i=0;in;i+)printf( 请输入要进行合并排序的第%d 个数字 :n,i+1);scanf_s(%d,&ai);MergeSort(a,n);printf( 合并排序的结果:n);for(i=0;in;i+)printf(
9、%d,ai);printf(n);system(pause);运行结果经验归纳结合以前学的数据结构及应用算法，用心理解还能明白。题目三：棋盘覆盖问题。（要求 N 可由用户输入）题目分析将棋盘平分四部分，将分割后的再一分为四，一直分，直到含有特殊方格，看特殊方格在那一部分中，用一个L 型股牌覆盖这3 个较小棋盘会合处。算法构造算法实现#include#include#includeint Board100100;/ 用来存放棋盘元素的数组int tile=1;/L 型骨牌的投放序号void ChessBoard(int tr, int tc, int dr, int dc, int size)i
10、f(size=1)/ 棋盘方格大小为, 说明递归到最里层return;int t=tile+;/ 每次递增int s=size/2; / 分割棋盘if(drtr+s & dctc+s)/ 检查特殊方块是否在左上角子棋盘中ChessBoard(tr, tc, dr, dc, s);else/ 不在，将该子棋盘右下角的方块视为特殊方块Boardtr+s-1tc+s-1=t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s);if(dr=tc+s)/ 检查特殊方块是否在右上角子棋盘中ChessBoard(tr, tc+s, dr, dc, s);else/ 不在，将该子棋盘左下角的方块视为特殊方块 Boardtr+s-1tc+s=t;ChessBoard(tr, tc+s, tr+s-1, t
