算法分析实验报告.docx

算法设计与分析实验报告分治策略姓名：专业班级：学号：指导教师：完成日期：

一、试验名称：分治策略

(1)写出源程序，并编译运行

(2)详细记录程序调试及运行结果

二、实验目的(1)了解分治策略算法思想

(2)掌握快速排序、归并排序算法

(3)了解其他分治问题典型算法

三、实验内容

(1)编写一个简单的程序，实现归并排序。

(2)编写一段程序，实现快速排序。

(3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其它n-1个选手各赛一次

(2)每个选手一天只能赛一场

(3)循环赛进行n-1天

四、算法思想分析

(1)编写一个简单的程序，实现归并排序。将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

(2)编写一段程序，实现快速排序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

(3)编写程序实现循环日赛表。按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通过为个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

五、算法源代码及用户程序

(1)编写一个简单的程序，实现归并排序。ncludeostreamncludetme.hdefneMA_10usngnamespacestd;vodmerge(ntarray,ntp,ntq,ntr)nt,k;ntbegn1,end1,begn2,end2;nt_temp=newntr-p 1;begn1=p;end1=q;begn2=q 1;end2=r;k=0;whle(begn1=end1)(begn2=end2)f(arraybegn1arraybegn2)tempk=arraybegn1;begn1 ;elsetempk=arraybegn2;begn2 ;k ;whle(begn1=end1)tempk =arraybegn1 ;whle(begn2=end2)tempk =arraybegn2 ;for(=0;(r-p 1); )arrayp =temp;delete(temp);vodmerge_sort(ntdata,ntleft,ntrght)f(leftrght)ntmd=(left rght;merge_sort(data,left,md);merge_sort(data,md 1,rght);merge(data,left,md,rght);vodmanntnumberMA_=0;srand(tme(NULL);prntf(排序前：);for(nt=0;MA_; )number=rand0;prntf(%d,number);coutendl;merge_sort(number,0,9);prntf(排序后：);for(ntj=0;jMA_;j )prntf(%d,numberj);

(2)编写一段程序，实现快速排序。ncludeostreamncludetme.hdefneMA_10defneSWAP(_,y)ntt;t=_;_=y;y=t;usngnamespacestd;vodqucksort(ntnumber,ntleft,ntrght)nt,j,s;f(leftrght)s=number(left rght;=left-1;j=rght 1;whle

(1)whle(number s);whle(number-js);f(=j)break;SWAP(number,numberj);qucksort(number,left,-1);qucksort(number,j 1,rght);vodmanntnumberMA_=0;srand(tme(NULL);prntf(排序前：);for(nt=0;MA_; )number=rand0;prntf(%d,number);coutendl;qucksort(number,0,9);prntf(排序后：);for(ntj=0;jMA_;j )prntf(%d,numberj);

(3)编写程序实现循环赛日程表。defneMA_N6日程表数组ncludestdo.hncludestdlb.hdefneMA_32ntaMA_MA_;vodCopy(ntto_,nttoy,ntfrom_,ntfromy,ntn)nt,j;for(=0;n; )for(j=0;jn;j )ato_ toy j=afrom_ fromy j;vodTable(ntk,ntaMA_)nt,n=1k;ntr;for(=0;n; )a0= 1;for(r=1;rn;r=1)for(=0;n; =2_r)Copy(r, r,0,,r);Copy(r,,0, r,r);vodOut(ntaMA_,ntn)nt,j;for(=0;n; )for(j=0;jn;j )prntf(=,aj);prntf(n);prntf(n);getch;ntmannt;for(=0;5; )ntlen=1;Table(,a);Out(a,len);return0;六试验结果及分析分治策略对于解决排序，循环日赛表起着很优越的作用，应该熟练掌握归并排序和快速排序。而且应该认真搞懂递归的思想。.;