《算法分析與設(shè)計(jì)》實(shí)驗(yàn)報(bào)告完成日期：20011.11.10一、實(shí)驗(yàn)?zāi)康牧私夥种尾呗运惴ㄋ枷胝莆湛焖倥判?、歸并排序算法了解其他分治問題典型算法.實(shí)驗(yàn)內(nèi)容：編寫一個(gè)簡(jiǎn)單的程序，實(shí)現(xiàn)歸并排序。編寫一段程序，實(shí)現(xiàn)快速排序。編寫程序?qū)崿F(xiàn)循環(huán)賽日程表。設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽。現(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其它n-1個(gè)選于各賽一次(2)每個(gè)選于一天只能賽一場(chǎng)(3)循環(huán)賽進(jìn)行n-1天實(shí)驗(yàn)要求：寫出源程序，并編譯運(yùn)行詳細(xì)記錄程序調(diào)試及運(yùn)行結(jié)果算法思想分析：歸并排序：將待排序元素分成大小大致相同的兩個(gè)集合，分別把對(duì)兩個(gè)子集合進(jìn)行排序，最終將排序號(hào)的子集合合并成為所要求的排好序的集合快速排序：通過一次排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。按照分治策略，將所有選于分為兩組，n個(gè)選手的比賽日程就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸的對(duì)選手進(jìn)行分割，直到剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得異常簡(jiǎn)單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了算法源代碼：⑴歸并排序：源代碼如下：#include<iostream>usingnamespacestd;voidmerge(intarray[],intp,intq,intr){inti,k;intbegin1,end1,begin2,end2;int*temp=newint[r-p+1];//申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后、〃的序列//設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起止位置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++;}//若第一個(gè)序列有剩余，拷貝出來粘到合并序列尾while(begin1<=end1)temp[k++]=array[begin1++];//若第二個(gè)序列有剩余，拷貝出來粘到合并序列尾while(begin2<=end2)temp[k++]=array[begin2++];for(i=0;i<(r-p+1);i++) 〃將排序好的序列拷貝回?cái)?shù)組中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<<"歸并排序后的數(shù)組為："<<endl;intz=0;for(z;z<8;z++){cout<<a[z]<<"";}cout<<endl;return0;截圖如下:2?快速排序：算法實(shí)驗(yàn)代碼如下:#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);//向右找第一個(gè)大于軸的數(shù)while(number[--j]>s);〃向左找第一個(gè)小于軸的數(shù)if(i>=j)break;swap(number[i],number[j]);}quicksort(number,left,i-1);//對(duì)左邊進(jìn)行遞歸quicksort(number,j+1,right);//對(duì)右邊進(jìn)行遞歸intmain(){inta[8]={1,45,48,21,35,48,1421,98};quicksort(a,0,7);cout<<"經(jīng)快速排序后的數(shù)組為："<<endl;inti=0;for(i;i<8;i++){cout<<a[i]<<"”;}cout<<endl;return0;截圖如下:3.循環(huán)賽日程表:算法實(shí)驗(yàn)代碼如下:#defineMAXN64/*日程表數(shù)組"#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作業(yè)：線性時(shí)間排序：#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);

實(shí)驗(yàn)分析：上課講分治算法講的透徹，上課認(rèn)真聽講和下課后對(duì)算法的理解。在編寫