算法设计与分析软件

《算法设计与分析软件》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》实验报告项目名称—分治算法实验专业班级软件工程1503学号3903150333姓名曾永豪实验成绩:批阅教师:实验1《分治算法实验》一、实验目的1.了解分治策略算法思想2.掌握快速排序、归并排序算法3.了解其他分治问题典型算法二、实验内容1.编写一个简单的程序，实现归并排序。2.编写一段程序，实现快速排序。3.编写程序实现循环赛日程表。设有n二労个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛口程表：(1)每个选手必须与其它旷1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天三、算法思想分析大问题分解为子问题，

2、这些子问题相互独立且与原问题相同。分別求解子问题，合并解，自底向上逐步求出原来问题的解。四、实验过程分析写在代码注释屮五、算法源代码及用户屏幕1、归并排序：#includeusingnamespacestd;#defineN7〃待排序数据个数voidmerge(intarray[],intp、intq,intr);voidmerge_sort(intdata[]9intp,intr);lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

3、llllllllllllllllllllllllllllllllllllvoidmain(){intdatafl={44,12,145,-123,-1,0,121);cout«HarrayH«endl;fbr(inti=0;i

4、llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllvoidmerge(intarray[],intp、intq,intr){inti,k;intbegin1,end1,begin2,end2;int*temp=newint[r-p+1];〃申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列begin1=p;endl=q;//设定两个指针，最初位置分别为两个已经排序序列的起始位置begin2=q+l;end2=r;k=0;while((beginl<=endl)&

5、&(begin2<=end2))//比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置{if(array[begin1]

6、尾{temp[k++]=array[begin2++];}for(i=0;i<(r-p+1)；i++)//将排序好的序列拷贝回数组中array[p+i]=temp[i];deletef](temp);}//////////////////////////////////////////////////////////////////////////////////////////////////////////////voidmerge_sort(intdata[],intleft,intright){if(left

7、ft+right)/2;merge_sort(data,left,mid);cout«',0-left,mid:',«left«","«mid«endl;〃观察语句，用来理解递归merge_sort(data,mid+l,right);coinvvT・left,mid:”vvleftvv”,”vvmidvvendl;//观察语句，用来理解递归merge(data,left,mid,right);inti;for(i=left;i<=right;i++)//观察语句，用来理解递归cout«data[i]«,,,H;cout«endl;12,44“0-11

8、ft/*13:0/1CT.ft“id22Hl«£t*14:2.2723,145,1-left/