算法設(shè)計(jì)與分析實(shí)驗(yàn)二分治策略運(yùn)用練習(xí)

1、學(xué) 號 算法設(shè)計(jì)與分析實(shí)驗(yàn)報告二學(xué)生姓名專業(yè)、班級指導(dǎo)教師唐國峰成績電子與信息工程系2013 年 4 月 15 日實(shí)驗(yàn)二：分治策略運(yùn)用練習(xí)一、實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)是針對分治策略運(yùn)用的算法設(shè)計(jì)及應(yīng)用練習(xí)，旨在加深學(xué)生對該部分知識點(diǎn)的理解，提高學(xué)生運(yùn)用該部分知識解決問題的能力。二、實(shí)驗(yàn)步驟與要求1實(shí)驗(yàn)前復(fù)習(xí)課程所學(xué)知識以及閱讀和理解指定的課外閱讀材料；2學(xué)生獨(dú)自完成實(shí)驗(yàn)指定內(nèi)容；3實(shí)驗(yàn)結(jié)束后，用統(tǒng)一的實(shí)驗(yàn)報告模板編寫實(shí)驗(yàn)報告。4提交說明： （1）電子版提交說明：a 需要提交winrar壓縮包，文件名為“算法設(shè)計(jì)與分析實(shí)驗(yàn)二_學(xué)號_姓名”，如“算法設(shè)計(jì)與分析實(shí)驗(yàn)二_09290101_張三”。 b 壓縮包

2、內(nèi)為一個“算法設(shè)計(jì)與分析實(shí)驗(yàn)二_學(xué)號_姓名”命名的頂層文件夾，其下為兩個文件夾，一個文件夾命名為“源程序”，另一個文件夾命名為“實(shí)驗(yàn)報告電子版”。其下分別放置對應(yīng)實(shí)驗(yàn)成果物。 （2）打印版提交說明：a 不可隨意更改模板樣式。 b 字體：中文為宋體，大小為10號字，英文為time new roman，大小為10號字。 c 行間距：單倍行距。（3）提交截止時間：2012年4月29日16:00。三、 實(shí)驗(yàn)項(xiàng)目1對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序。要求分別運(yùn)用合并排序和快速排序完成該題目要求。四、實(shí)驗(yàn)過程（一） 題目一：對于用戶隨意輸入的7個無序數(shù)字，用合并排序的方法，按照從小到大的

3、順序進(jìn)行排序。1. 題目分析：將待排序元素分成大致相同的兩個子集合，分別對兩個子集合進(jìn)行排序，最終將排好序的子集合合并成所要求的排好序的集合。2. 算法構(gòu)造：調(diào)用三個函數(shù)來實(shí)現(xiàn)，mergepass用于合并排好序的相鄰數(shù)組段，具體的合并算法由merge用來實(shí)現(xiàn)，mergesort函數(shù)為合并算法，調(diào)用merge、mergepass函數(shù)來實(shí)現(xiàn)數(shù)的合并排序3. 算法實(shí)現(xiàn)#include<stdio.h>template<class type>void mergesort(type a,int n) type*b=new type; int s=1;while(s<n)me

4、rgepass(a,b,s,n);/將a中的元素合并到數(shù)組bs+=s;mergepass(b,a,s,n);/將b中的元素合并到數(shù)組as+=s;template<class type>void merge(type c,type d,int l,int m,int r) /合并cl,m和xm+1,r到y(tǒng)l,rint i=l,j=m+1,k=l;while(i<=m)&&(j<=r)if(ci<=cj)dk+=ci+;elsedk+=cj+;if(i>m)for(int q=j;q<=r;q+)dk+=cq;elsefor(int q=i

5、;q<=m;q+)dk+=cq;template<class type>void mergepass(type x,type y,int s,int n)/合并大小為s的相鄰序列子數(shù)組int i=0;while(i<=n-2*s) /合并大小為s的相鄰2字段數(shù)組merge(x,y,i,i+s-1,i+2*s-1);/合并xi,i+s-1和xi+s,i+2*s-1到y(tǒng)i,i+2*s-1i=i+2*s;if(i+s<n)/處理剩下的元素少于2smerge(x,y,i,i+s-1,n-1);elsefor(int j=i;j<=n-1;j+)yj=xj;void

6、main() int a7,i;printf("請 輸 入 7 個 數(shù) 字:n");for( i=0;i<7;i+)scanf("%d",&ai); mergesort(a,7);printf("最 終 排 序 結(jié) 果 為:n");for(int e=0;e<7;e+)printf("%dt",ae);printf("n");4. 運(yùn)行結(jié)果5. 經(jīng)驗(yàn)歸納：我主要參考書上的程序來做的，我感覺主要是做好合并數(shù)組（二）題目二：對用戶輸入的無序的數(shù)字，按照快速排序方法，由小到大的順序

7、排序。1. 題目分析：通過一趟掃描，就能確保某個數(shù)并以它為基準(zhǔn)點(diǎn)的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理，它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個元素為止2. 算法構(gòu)造：定義軸測元素，然后從兩端各個和軸測元素比較后放在相應(yīng)的位置，相比元素一樣，將軸測元素放到中間。對排好序的兩邊，重復(fù)上述操作。3. 算法實(shí)現(xiàn)#include<stdio.h>void quicksort(int a,int l,int r) int i,j,t; i=l; j=r; t=al; /軸測元素t為數(shù)組最左側(cè)的元素 if(l>r) return; while(i!=j) /掃描完，

8、結(jié)束時語句 while(aj>=t && j>i) j-; /如果右側(cè)指針元素比軸測元素大，指針元素左移 if(j>i) ai+=aj; while(ai<=t && j>i) i+; /如果左側(cè)指針元素比軸測元素小，指針元素右移 if(j>i) aj-=ai; ai=t; quicksort(a,l,i-1); /對左邊進(jìn)行排序 quicksort(a,i+1,r); /對右邊進(jìn)行排序void main() int i,f7; printf("請 輸 入 7 個 無 序 的 數(shù) 字：n"); for(i = 0; i <7; i +) scanf("%d",&fi); quicksort(f,0,7);printf("快 速 排 序 后：n"); for(i=0;i<7;i+) printf("%d ",fi);printf("n");4. 運(yùn)行結(jié)果5. 經(jīng)驗(yàn)歸納：主要找出軸測元素和兩端元素進(jìn)行比較