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

学 号 1421050102算法设计与分析实验报告二学生姓名Cherish专业、班级地理指导教师唐国峰成绩计算机与信息工程学院软件工程系2017 年 3 月 28 日实验二：分治策略运用练习一、实验目的本次实验是针对分治策略运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“算法设计与分析实验二_学号_姓名”，如“算法设计与分析实验二_09290101_张三”。 b 压缩包内为一个“算法设计与分析实验二_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。 c 行间距：单倍行距。（3）提交截止时间：2017年4月11日16:00。三、 实验项目1对用户输入的杂乱无序的数字序列按照由小到大的顺序排序。要求分别运用合并排序和快速排序完成该题目要求。2棋盘覆盖问题。（要求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) 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 = 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();运行结果经验归纳结合以前学的数据结构及应用算法，较容易理解。题目二：对用户输入的杂乱无序的数字序列按照由小到大的顺序排序：合并排序题目分析合并排序的基本思想是：将待排序的元素分成大小大相同的两个子集合，分别对两个子集合进行排序，最终将排序好的子集合合并成所要求的拍好序的集合。算法构造核心代码来自书上：MergePass(Type x,Type y,int s,int n)/合并大小为s的相邻序列子数组Merge(Type c,Type d,int l,int m,int r) /合并cl,m和xm+1,r到yl,r算法实现#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 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,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(%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) if(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, tc+s, s); if(dr=tr+s & dc=tr+s & dc=tc+s) /检查特殊方块是否在右下角子棋盘中 ChessBoard(tr+s, tc+s, dr, dc, s); else /不在，将该子棋盘左上角的方块视为特殊方块 Boardtr+stc+s=t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); void main() int n; int size;/棋盘大小 printf(请输入一个数字，将为您创建2n*2n大小的棋盘：); scanf_s(%d,&n); int x,y; size=(int)pow(2.0,(int)n); printf(输入特殊方格的横坐标:); scanf_s(%d,&x); printf(输入特殊方格的横坐标:); scanf_s(%d,&y); ChessBoard(0,0,x,y,size); print