算法分析与设计实验报告

《算法分析与设计》实验报告完成日期：20011.11.10一、实验目的了解分治策略算法思想掌握快速排序、归并排序算法了解其他分治问题典型算法.实验内容：编写一个简单的程序，实现归并排序。编写一段程序，实现快速排序。编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其它n-1个选于各赛一次(2)每个选于一天只能赛一场(3)循环赛进行n-1天实验要求：写出源程序，并编译运行详细记录程序调试及运行结果算法思想分析：归并排序：将待排序元素分成大小大致相同的两个集合，分别把对两个子集合进行排序，最终将排序号的子集合合并成为所要求的排好序的集合快速排序：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。按照分治策略，将所有选于分为两组，n个选手的比赛日程就可以通过为n/2个选手设计的比赛日程表来决定。递归的对选手进行分割，直到剩下两个选手时，比赛日程表的制定就变得异常简单。这时只要让这两个选手进行比赛就可以了算法源代码：⑴归并排序：源代码如下：#include<iostream>usingnamespacestd;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(left<right){intmid=(left+right)/2;merge_sort(data,left,mid);merge_sort(data,mid+1,right);merge(data,left,mid,right);intmain(){inta[8]={10,8,98,56,42,40,7,5};merge(a,0,3,7);merge_sort(a,0,7);cout<<"归并排序后的数组为："<<endl;intz=0;for(z;z<8;z++){cout<<a[z]<<"";}cout<<endl;return0;截图如下:2・快速排序：算法实验代码如下:#include<iostream>usingnamespacestd;voidquicksort(intnumber[],intleft,intright){inti,j,s;if(left<right){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);//对右边进行递归intmain(){inta[8]={1,45,48,21,35,48,1421,98};quicksort(a,0,7);cout<<"经快速排序后的数组为："<<endl;inti=0;for(i;i<8;i++){cout<<a[i]<<"”;}cout<<endl;return0;截图如下:3.循环赛日程表:算法实验代码如下:#defineMAXN64/*日程表数组"#include<stdio.h>#include<stdlib.h>#defineMAX32inta[MAX][MAX];voidCopy(inttox,inttoy,intfromx,intfromy,intn){inti,j;for(i=0;i<n;i++){for(j=0;j<n;j++)a[tox+i][toy+j]=a[fromx+i][fromy+j];}}voidTable(intk,inta[][MAX]){inti,n=1<<k;intr;for(i=0;i<n;i++)a[0][i]=i+1;for(r=1;r<n;r<<=1){for(i=0;i<n;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;i<n;i++){for(j=0;j<n;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");}intmain(){inti;for(i=0;i<5;i++){intlen=1<<i;Table(i,a);Out(a,len);}return0;}截图所示：432134122143123487657856&5875_b784321341221431234321341221431234876578566s8767815211075i31128742315194L016113G40121111217841341511?4i±2172449101147no9014L161314601i141rrr作业：线性时间排序：#include<iostream>usingnamespacestd;voidcountsort(inta[],intn){intcount=0;intk=0;while(k<n-1)for(inti=k+1;i<n;i++){if(a[k]>a[i])count++;if(count==0)k++;if(count>0){swap(a[k],a[count]);count=0;cout<<"排序后为:"<<endl;for(intj=0;j<n;j++)cout<<a[j]<<"";}voidswap(int&x,int&y){inttemp;temp=x;x=y;y=temp;}voidmain(){intn=8;inta[8]={100,200,50,90,150,50,20,80};cout<<"排序前为:"<<endl;for(intq=0;q<=7;q++){cout<<a[q]<<””;}cout<<endl;countsort(a,8);

实验分析：上课讲分治算法讲的透彻，上课认真听讲和下课后对算法的理解。在编写