《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二分治策略運(yùn)用練習(xí)》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二分治策略運(yùn)用練習(xí)（6頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、學(xué) 號(hào) 算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告二學(xué)生姓名專業(yè)、班級(jí)指導(dǎo)教師唐國峰成績(jī)電子與信息工程系2013 年 4 月 15 日實(shí)驗(yàn)二：分治策略運(yùn)用練習(xí)一、實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)是針對(duì)分治策略運(yùn)用的算法設(shè)計(jì)及應(yīng)用練習(xí)，旨在加深學(xué)生對(duì)該部分知識(shí)點(diǎn)的理解，提高學(xué)生運(yùn)用該部分知識(shí)解決問題的能力。二、實(shí)驗(yàn)步驟與要求1實(shí)驗(yàn)前復(fù)習(xí)課程所學(xué)知識(shí)以及閱讀和理解指定的課外閱讀材料；2學(xué)生獨(dú)自完成實(shí)驗(yàn)指定內(nèi)容；3實(shí)驗(yàn)結(jié)束后，用統(tǒng)一的實(shí)驗(yàn)報(bào)告模板編寫實(shí)驗(yàn)報(bào)告。4提交說明： （1）電子版提交說明：a 需要提交Winrar壓縮包，文件名為“算法設(shè)計(jì)與分析實(shí)驗(yàn)二_學(xué)號(hào)_姓名”，如“算法設(shè)計(jì)與分析實(shí)驗(yàn)二_09290101_張三”。 b 壓縮包
2、內(nèi)為一個(gè)“算法設(shè)計(jì)與分析實(shí)驗(yàn)二_學(xué)號(hào)_姓名”命名的頂層文件夾，其下為兩個(gè)文件夾，一個(gè)文件夾命名為“源程序”，另一個(gè)文件夾命名為“實(shí)驗(yàn)報(bào)告電子版”。其下分別放置對(duì)應(yīng)實(shí)驗(yàn)成果物。 （2）打印版提交說明：a 不可隨意更改模板樣式。 b 字體：中文為宋體，大小為10號(hào)字，英文為Time New Roman，大小為10號(hào)字。 c 行間距：?jiǎn)伪缎芯?。?）提交截止時(shí)間：2012年4月29日16:00。三、 實(shí)驗(yàn)項(xiàng)目1對(duì)用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序。要求分別運(yùn)用合并排序和快速排序完成該題目要求。四、實(shí)驗(yàn)過程（一） 題目一：對(duì)于用戶隨意輸入的7個(gè)無序數(shù)字，用合并排序的方法，按照從小到大的
3、順序進(jìn)行排序。1. 題目分析：將待排序元素分成大致相同的兩個(gè)子集合，分別對(duì)兩個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成所要求的排好序的集合。2. 算法構(gòu)造：調(diào)用三個(gè)函數(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)#includetemplatevoid MergeSort(Type a,int n) Type*b=new Type; int s=1;while(sn)MergePass(a,b,s,n);/將a中的元素合并到數(shù)組bs+=s;Me
4、rgePass(b,a,s,n);/將b中的元素合并到數(shù)組as+=s;templatevoid 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(cim)for(int q=j;q=r;q+)dk+=cq;elsefor(int q=i;q=m;q+)dk+=cq;templatevoid MergePass(Type x,Type y,int s,int n)/合并大小為s的相鄰序列子數(shù)組int i=0;while(i=n-2*s) /合并大小為s的相鄰
5、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+sn)/處理剩下的元素少于2sMerge(x,y,i,i+s-1,n-1);elsefor(int j=i;j=n-1;j+)yj=xj;void main() int a7,i;printf(請(qǐng) 輸 入 7 個(gè) 數(shù) 字:n);for( i=0;i7;i+)scanf(%d,&ai); MergeSort(a,7);printf(最 終 排 序 結(jié) 果 為:n);for(int e=0;e7;e+)printf(%dt,ae);prin
6、tf(n);4. 運(yùn)行結(jié)果5. 經(jīng)驗(yàn)歸納：我主要參考書上的程序來做的，我感覺主要是做好合并數(shù)組（二）題目二：對(duì)用戶輸入的無序的數(shù)字，按照快速排序方法，由小到大的順序排序。1. 題目分析：通過一趟掃描，就能確保某個(gè)數(shù)并以它為基準(zhǔn)點(diǎn)的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理，它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止2. 算法構(gòu)造：定義軸測(cè)元素，然后從兩端各個(gè)和軸測(cè)元素比較后放在相應(yīng)的位置，相比元素一樣，將軸測(cè)元素放到中間。對(duì)排好序的兩邊，重復(fù)上述操作。3. 算法實(shí)現(xiàn)#includevoid quickSort(int a,int l,int r) int i,j,t; i
7、=l; j=r; t=al; /軸測(cè)元素t為數(shù)組最左側(cè)的元素 if(lr) return; while(i!=j) /掃描完，結(jié)束時(shí)語句 while(aj=t & ji) j-; /如果右側(cè)指針元素比軸測(cè)元素大，指針元素左移 if(ji) ai+=aj; while(aii) i+; /如果左側(cè)指針元素比軸測(cè)元素小，指針元素右移 if(ji) aj-=ai; ai=t; quickSort(a,l,i-1); /對(duì)左邊進(jìn)行排序 quickSort(a,i+1,r); /對(duì)右邊進(jìn)行排序void main() int i,f7; printf(請(qǐng) 輸 入 7 個(gè) 無 序 的 數(shù) 字：n); for(i = 0; i 7; i +) scanf(%d,&fi); quickSort(f,0,7);printf(快 速 排 序 后：n); for(i=0;i7;i+) printf(%d ,fi);printf(n);4. 運(yùn)行結(jié)果5. 經(jīng)驗(yàn)歸納：主要找出軸測(cè)元素和兩端元素進(jìn)行比較，依次進(jìn)行這樣就行五、實(shí)驗(yàn)總結(jié) 通過這次實(shí)驗(yàn)我了解并理解了合并排序和快速排序，以前只是學(xué)習(xí)了快速排序的思想并沒有編程，合并的編程我參照課本上的程序，馬馬虎虎把它做下來了，快速排序我主要是查看了一些資料，來編寫的，這次實(shí)驗(yàn)讓我在合并和快速排序上面的編程有了更加進(jìn)一步的理解。
《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二分治策略運(yùn)用練習(xí)
