算法分析实验报告--分治策略

《算法设计与分析》实验报告分治策略姓名：XXX专业班级：XXX学号：XXX指导教师：XXX完成日期：XXX一、试验名称：分治策略（1）写出源程序，并编译运行（2）详细记录程序调试及运行结果二、实验目的(1)了解分治策略算法思想(2)掌握快速排序、归并排序算法(3)了解其他分治问题典型算法三、实验内容(1)编写一个简单的程序，实现归并排序。(2)编写一段程序，实现快速排序。(3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天四、算法思想分析(1)编写一个简单的程序，实现归并排序。将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。(2)编写一段程序，实现快速排序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。(3)编写程序实现循环日赛表。按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。五、算法源代码及用户程序(1)编写一个简单的程序，实现归并排序。#includeiostream#includetime.h#defineMAX10usingnamespacestd;voidmerge(intarray[],intp,intq,intr){inti,k;intbegin1,end1,begin2,end2;int*temp=newint[r-p+1];begin1=p;end1=q;begin2=q+1;end2=r;k=0;while((begin1=end1)&&(begin2=end2)){if(array[begin1]array[begin2]){temp[k]=array[begin1];begin1++;}else{temp[k]=array[begin2];begin2++;}k++;}while(begin1=end1){temp[k++]=array[begin1++];}while(begin2=end2){temp[k++]=array[begin2++];}for(i=0;i(r-p+1);i++){array[p+i]=temp[i];}delete[](temp);}voidmerge_sort(intdata[],intleft,intright){if(leftright){intmid=(left+right)/2;merge_sort(data,left,mid);merge_sort(data,mid+1,right);merge(data,left,mid,right);}}voidmain(){intnumber[MAX]={0};srand(time(NULL));printf(排序前：);for(inti=0;iMAX;i++){number[i]=rand()%100;printf(%d,number[i]);}coutendl;merge_sort(number,0,9);printf(排序后：);for(intj=0;jMAX;j++){printf(%d,number[j]);}}(2)编写一段程序，实现快速排序。#includeiostream#includetime.h#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}usingnamespacestd;voidquicksort(intnumber[],intleft,intright){inti,j,s;if(leftright){s=number[(left+right)/2];i=left-1;j=right+1;while(1){while(number[++i]s);while(number[--j]s);if(i=j)break;SWAP(number[i],number[j]);}quicksort(number,left,i-1);quicksort(number,j+1,right);}}voidmain(){intnumber[MAX]={0};srand(time(NULL));printf(排序前：);for(inti=0;iMAX;i++){number[i]=rand()%100;printf(%d,number[i]);coutendl;}quicksort(number,0,9);printf(排序后：);for(intj=0;jMAX;j++){printf(%d,number[j]);}}(3)编写程序实现循环赛日程表。#defineMAXN64/*日程表数组*/#includestdio.h#includestdlib.h#defineMAX32inta[MAX][MAX];voidCopy(inttox,inttoy,intfromx,intfromy,intn){inti,j;for(i=0;in;i++){for(j=0;jn;j++)a[tox+i][toy+j]=a[fromx+i][fromy+j];}}voidTable(intk,inta[][MAX]){inti,n=1k;intr;for(i=0;in;i++)a[0][i]=i+1;for(r=1;rn;r=1){for(i=0;in;i+=2*r){Copy(r,i+r,0,i,r);Copy(r,i,0,i+r,r);}}}voidOut(inta[][MAX],intn){inti,j;for(i=0;in;i++){for(j=0;jn;j++)printf(%3d,a[i][j]);printf(\n);}printf(\n);getch();}intmain(){inti;for(i=0;i5;i++){intlen=1i;Table(i,a);Out(a,len);}return0;}六试验结果及分析分治策略对于解决排序，循环日赛表起着很优越的作用，应该熟练掌握归并排序和快速排序。而且应该认真搞懂递归的思想。