算法設(shè)計(jì)解析總結(jié)實(shí)驗(yàn)報(bào)告模板

1、優(yōu)選文檔實(shí)驗(yàn)報(bào)告2016/2017學(xué)年第一學(xué)期）課程名稱算法解析與設(shè)計(jì)實(shí)驗(yàn)名稱分治策略實(shí)驗(yàn)時(shí)間2016年10月18日指導(dǎo)單位計(jì)算機(jī)學(xué)院軟件授課中心指導(dǎo)教師季一木學(xué)生姓名周文超班級(jí)學(xué)號(hào)B14041527學(xué)院(系)計(jì)算機(jī)學(xué)院、專業(yè)軟件工程軟件學(xué)院.優(yōu)選文檔實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱分治策略指導(dǎo)教師季一木實(shí)驗(yàn)種類考據(jù)明驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間一、實(shí)驗(yàn)?zāi)康暮腿蝿?wù)理解分治法的算法思想，閱讀實(shí)現(xiàn)書上已有的部分程序代碼并完滿程序，加深對(duì)分治法的算法原理及實(shí)現(xiàn)過程的理解。用分治法實(shí)現(xiàn)一組無序序列的兩路歸并排序和快速排序。要求清楚歸并排序及快速排序的基根源理，編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組無序序列排序?yàn)橛行蛐蛄泻筝敵觥?優(yōu)

2、選文檔二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)算法設(shè)計(jì)與解析課本筆錄本電腦VC+6.0.優(yōu)選文檔三、實(shí)驗(yàn)原理及內(nèi)容（包括操作過程、結(jié)果解析等）實(shí)驗(yàn)原理運(yùn)用分治法：無序-部分有序-整體有序歸并排序中“分”與“合”的過程是結(jié)合在一起的，即每一趟都在做“分”與“合”的工作，其實(shí)不是先“分”完再“合”基本程序（一）兩路歸并排序#includeclassSortableListpublic:SortableList(intmSize)/構(gòu)造函數(shù)maxSize=mSize;l=newintmaxSize;n=0;SortableList()deletel;/析構(gòu)函數(shù)voidInput();voidMerge(intlef

3、t,intmid,intright);voidMergeSort();voidMergeSort(intleft,intright);voidOutput();private:int*l;/動(dòng)向生成一維數(shù)組intmaxSize;/線性表的最大表長intn;/線性表的實(shí)質(zhì)長度;voidSortableList:Input()for(inti=0;ili;n+;.優(yōu)選文檔voidSortableList:Merge(intleft,intmid,intright)int*temp=newintright-left+1;inti=left,j=mid+1,k=0;while(i=mid)&(j=ri

4、ght)if(li=lj)tempk+=li+;elsetempk+=lj+;while(i=mid)tempk+=li+;while(j=right)tempk+=lj+;for(i=0,k=left;k=right;)lk+=tempi+;voidSortableList:MergeSort()MergeSort(0,n-1);voidSortableList:MergeSort(intleft,intright)if(leftright)/若序列的長度高出1，則劃分成兩個(gè)子序列intmid=(left+right)/2;/將待排序的序列一分為二MergeSort(left,mid);/對(duì)

5、左序列排序MergeSort(mid+1,right);/對(duì)右序列排序Merge(left,mid,right);/將兩個(gè)有序子序列歸并成一個(gè)有序序列voidSortableList:Output()for(inti=0;imaxSize;i+)coutli;voidmain()SortableListl(10);cout請(qǐng)輸入10個(gè)數(shù)：endl;l.Input();l.MergeSort();.優(yōu)選文檔cout排序后是：endl;l.Output();（二）快速排序#includeclassSortableListpublic:SortableList(intmSize)/構(gòu)造函數(shù)maxSi

6、ze=mSize;l=newintmaxSize;n=0;SortableList()deletel;/析構(gòu)函數(shù)voidInput();voidSwap(inti,intj);intPartition(intleft,intright);voidQuickSort(intleft,intright);voidQuickSort();voidOutput();private:int*l;/動(dòng)向生成一維數(shù)組intmaxSize;/線性表的最大表長intn;/線性表的實(shí)質(zhì)長度;voidSortableList:Input()for(inti=0;ili;n+;voidSortableList:Swa

7、p(inti,intj)intc=li;.優(yōu)選文檔li=lj;lj=c;intSortableList:Partition(intleft,intright)前置條件：left=rightinti=left,j=right+1;dodoi+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);returnj;voidSortableList:QuickSort()QuickSort(0,n-1);voidSortableList:QuickSort(intleft,intright)if(leftright)/當(dāng)序列長度大于1時(shí)，需進(jìn)行切

8、割intj=Partition(left,right);/對(duì)left,right范圍內(nèi)的序列進(jìn)行分劃QuickSort(left,j-1);/對(duì)左子序列推行快速排序QuickSort(j+1,right);/對(duì)右子序列推行快速排序voidSortableList:Output()for(inti=0;imaxSize;i+)coutli;voidmain()SortableListl(10);cout請(qǐng)輸入10個(gè)數(shù)：endl;l.Input();l.QuickSort();cout排序后是：endl;l.Output();.優(yōu)選文檔實(shí)驗(yàn)結(jié)果兩路歸并排序快速排序.優(yōu)選文檔六、實(shí)驗(yàn)小結(jié)（包括問題和解決方法、心得領(lǐng)悟等）歸并排序的基本運(yùn)算是把兩個(gè)或