實(shí)驗(yàn)1歸并排序分治策略的設(shè)計(jì)與實(shí)現(xiàn)(報(bào)告)

1、實(shí)驗(yàn)1 歸并排序分治策略的設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?、熟悉分治法求解問題的抽象控制策略；2、熟悉在順序存儲(chǔ)表示下求解分類問題的遞歸算法設(shè)計(jì)；3、通過實(shí)例轉(zhuǎn)換, 掌握分治法應(yīng)用。二、實(shí)驗(yàn)內(nèi)容1、學(xué)習(xí)分治方法的原理 ；2、針對分治問題設(shè)計(jì)遞歸算法實(shí)現(xiàn)歸并排序算法；3、根據(jù)歸并排序的遞歸算法改寫成迭代算法。4、測試程序與驗(yàn)收并進(jìn)一步將程序改寫成模塊化可用程序。三、實(shí)驗(yàn)程序的功能模塊【模塊】void Merge(int r,int r1,int s,int m,int t) 實(shí)現(xiàn)數(shù)組中的已分好類的兩部分進(jìn)行合并 void MergeSort(int r,int r1,int s,int t) 對數(shù)組中從

2、下標(biāo)low開始到heigh結(jié)束的部分進(jìn)行分類 【遞歸實(shí)現(xiàn)】/合并數(shù)組void Merge(int r,int r1,int s,int m,int t) / r為待排序數(shù)列 r1用來存放排好序的數(shù)列 三個(gè)int型變量 s m t ，分別為數(shù)組的最左，中間，最右 int i=s;int j=m+1;int k=s; while(i=m & j=t) if(ri=rj) /左右兩邊的數(shù)組從頭開始比，選擇小者放入r1r1k+=ri+; else r1k+=rj+; if(i=m) /若比完之后，左邊有剩下，依次填入r1 while(i=m) r1k+=ri+; else /比完之后，右邊有剩下，依次

3、填入r1while(j=t) r1k+=rj+; for(int l=0;lt-s+1;l+) /復(fù)制會(huì)原數(shù)組，此步驟可省去 rl=r1l; /歸并算法void MergeSort(int r,int r1,int s,int t) /結(jié)束歸并條件，數(shù)組內(nèi)只有一個(gè)元素if(s=t) r1s=rs; else int m=(s+t)/2; /規(guī)定變量m，數(shù)組中間 MergeSort(r,r1,s,m); /左邊歸并MergeSort(r,r1,m+1,t); /右邊歸并Merge(r1,r,s,m,t); /合并【迭代實(shí)現(xiàn)】/合并算法 sort為合并后數(shù)組，list為待合并數(shù)組，low,cent

4、er,high分別為待合并數(shù)組的最左邊，中間，最右邊void merge(int *sort, int *list, int low, int center, int high) int i,j,k; /i,j分別代表兩個(gè)小數(shù)組的最左邊，通過比較，選擇小者放入合并后數(shù)組for(i=low,j=(center+1),k=low; i=center & j listj) /若左邊數(shù)組大，放右邊數(shù)組未用的最左邊的元素進(jìn)sortsortk = listj+; else sortk = listi+; while(i=center) /若左邊數(shù)組還有元素，依次填入sortsortk+ = listi+;

5、 while(j=high) /若右邊數(shù)組還有元素，依次填入sortsortk+ = listj+; /每次步長分組 a是分組后數(shù)組，b是待分組數(shù)組，length為步長（小組長度），n為大數(shù)組總長void merge_pass(int *a, int *b, int length, int n) int i; /從數(shù)組最左邊開始，按照步長分組，直到不夠元素達(dá)到步長可以分組（剩最后一組）for(i=0; i=n-2*length; i+=2*length) int center = (i + i + 2*length - 1)/2; /定義每個(gè)小組的中間merge(a, b, i, center

6、, i+2*length-1); /每個(gè)小組調(diào)用合并算法，最左邊就是i,最右邊是i+2*length-1 if(i+length)n) /最右邊的一個(gè)分組，若此組最右邊還未到達(dá)大數(shù)組最右邊(此數(shù)組長度大于步長) int center = (i + i + 2*length - 1)/2; /定義此小組的中間merge(a, b, i, center, n-1); /調(diào)用合并算法，最右邊是n-1 else /最后一個(gè)分組不夠元素達(dá)到步長，復(fù)制 while(in) ai = bi; +i; /歸并算法 array 為待排序數(shù)組，n為數(shù)組長度void m_sort(int *array, int n

7、) int extra30; int length = 1; while(length n) /以步長為分的標(biāo)準(zhǔn) /分組歸并，結(jié)果放到extramerge_pass(extra, array, length, n);/步長增長為兩倍length *= 2; /再次分組歸并，結(jié)果放回arraymerge_pass(array, extra, length, n); length *= 2; 四、遞歸算法改寫成迭代算法的一般方法1、遞歸一般分為三部分，開始狀態(tài)，一般狀態(tài)，結(jié)束狀態(tài)。遞歸調(diào)用的過程一般可以用循環(huán)代替。兩者的開始狀態(tài)是一樣的，結(jié)束條件也是一樣，循環(huán)需要一個(gè)變量衡量結(jié)束，可以是遞歸里的返

8、回變量把每步遞歸的操作移植到每步循環(huán)操作。以下是例子。遞歸 Fun(x)If(結(jié)束條件） Return;Else 每步遞歸操作； Fun(變量變化)迭代For（開始狀態(tài)；結(jié)束狀態(tài)；變量變化） 每步迭代操作。五、C+闡述分治法遞歸抽象控制策略問題p，子問題p，合并merge()，簡單解決ADHOc(P)void fun(p)if(p=n0)return (ADHOc(P)；elseDivide p into p0pk;For(i=0;ik;i+)Fun(pi);Merge();六、思考題1、應(yīng)用分治法抽象控制策略實(shí)現(xiàn)快速分類。解答：先分大類，再分小類，再分細(xì)節(jié)，層層細(xì)分。如單詞appeal，先按照第一個(gè)字母分類放進(jìn)開