《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二》由會員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二（9頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 學(xué) 號 1421050102 《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告二 學(xué) 生 姓 名 Cherish 專 業(yè) 、 班 級 地 理 指 導(dǎo) 教 師 唐 國 峰 成 績 計(jì)算機(jī)與信息工程學(xué)院軟件工程系 2017 年 3 月 28 日

2、實(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)報(bào)告模板編寫實(shí)驗(yàn)報(bào)告 。 4． 提交說明： （ 1）電子版提交說明： a 需要提交 Winrar 壓縮包，文件名為“ 《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二 _學(xué)號 _姓名”， 如“《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二 _09

3、290101_ 張三”。 b 壓縮包內(nèi)為一個(gè)“ 《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二 _學(xué)號 _姓名”命名的頂層文件夾， 其下為兩個(gè)文件夾，一個(gè)文件夾命名為“源程序” ，另一個(gè)文件夾命名為“實(shí)驗(yàn) 報(bào)告電子版” 。其下分別放置對應(yīng)實(shí)驗(yàn)成果物。 （ 2）打印版提交說明： a 不可隨意更改模板樣式。 b 字體：中文為宋體，大小為 10 號字，英文為 Time New Roman ，大小為 10 號 字。 c 行間距：單倍行距。 （ 3）提交截止時(shí)間： 2017 年 4 月 11 日 16:00。 三、 實(shí)驗(yàn)項(xiàng)

4、目 1．對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序。要求分別運(yùn)用合并排序和快速排序完成該題目要求。 2．棋盤覆蓋問題。 （要求 N 可由用戶輸入） 四、實(shí)驗(yàn)過程 （一） 題目一：對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序：快速排序題目分析 快速排序是冒泡排序的改進(jìn)，以一組雜亂無序的數(shù)字最左邊為樞軸記錄的關(guān)鍵字，最右 側(cè)指針若比關(guān)鍵字大， 則右側(cè)指針左移， 若出現(xiàn)比它小的交換兩指針指向數(shù)的排序完成。 算法實(shí)現(xiàn) #include #include void

5、quickSort(int a[],int l,int r) { int i,j,t; i=l; j=r; t=a[l];  // 樞軸元素  t 為數(shù)組最左側(cè)的元素 if(l>r) return; while(i!=j)  // i 往右移動  j 往左移動當(dāng)指向同一位置時(shí)掃描完成 { while(a[j]>=t && j>i) j--; // 如果右側(cè)指針元素比軸測元素大，指針元素左移 if(j>i) // 確保 i 在j 左邊 a[i++]=a[j]; //

6、 當(dāng)右側(cè)指針元素比軸測元素小時(shí)，交換兩指針指向數(shù)的位置 while(a[i]<=t && j>i) i++; // 如果左側(cè)指針元素比軸測元素小，指針元素右移 if(j>i) // 確保 i 在j 左邊 a[j--]=a[i]; // 當(dāng)左側(cè)指針元素比軸測元素大時(shí)，交換兩指針指向數(shù)的位置 } a[i]=t; quickSort(a,l,i-1); // 對左邊進(jìn)行排序 quickSort(a,i+1,r); // 對右邊進(jìn)行排序 } void main() { int i,n,f[100]; printf(" 請輸入要比較數(shù)字的

7、個(gè)數(shù)： \n"); scanf_s("%d",&n); for(i = 0; i

8、 經(jīng)驗(yàn)歸納 結(jié)合以前學(xué)的數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法，較容易理解。 題目二：對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序：合并排序題目分析 合并排序的基本思想是：將待排序的元素分成大小大相同的兩個(gè)子集合，分別對兩個(gè)子集合進(jìn)行排序，最終將排序好的子集合合并成所要求的拍好序的集合。 算法構(gòu)造

9、 核心代碼來自書上： MergePass(Type x[],Type y[], Merge(Type c[],Type d[], int l, int m, int r)  int s, int // 合并 c[l,m]  n) // 合并大小為 和x[m+1,r] 到y(tǒng)[l,r]  s的相鄰序列子數(shù)組 算法實(shí)現(xiàn) #include #include template void MergeSort(Type a[],int n)

10、 { Type*b=new Type[n]; int s=1; while(s void Merge(Type c[],Type d[],int l,int m,int r) // 合并 c[l,m] 和x[m+1,r] 到y(tǒng)[l,r] { int i=l,j=m+1,k=l;

11、 while((i<=m)&&(j<=r)){ if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; } if(i>m){ for(int q=j;q<=r;q++) d[k++]=c[q]; } else for(int q=i;q<=m;q++) d[k++]=c[q]; } template void MergePass(Type x[],Type y[],int s,int n){ // 合并大小為 s的相鄰序列子數(shù)組 i

12、nt i=0; while(i<=n-2*s) {  // 合并大小為 s的相鄰 2字段數(shù)組 Merge(x,y,i,i+s-1,i+2*s-1); // 合并 x[i,i+s-1]  和x[i+s,i+2*s-1]  到y(tǒng)[i,i+2*s-1] i=i+2*s; } if(i+s

13、j]; } void main() { int a[100],i,n; printf(" 請輸入要進(jìn)行合并排序的數(shù)字的個(gè)數(shù) :\n"); scanf_s("%d",&n); for( i=0;i

14、f("\n"); system("pause"); } 運(yùn)行結(jié)果 經(jīng)驗(yàn)歸納 結(jié)合以前學(xué)的數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法，用心理解還能明白。 題目三：棋盤覆蓋問題。 （要求 N 可由用戶輸入） 題目

15、分析 將棋盤平分四部分，將分割后的再一分為四，一直分，直到含有特殊方格，看特殊方格 在那一部分中，用一個(gè) L 型股牌覆蓋這 3 個(gè)較小棋盤會合處。 算法構(gòu)造 算法實(shí)現(xiàn) #include #include #include int Board[100][100]; // 用來存放棋盤元素的數(shù)組 int tile=1; //L 型骨牌的投放序號 void ChessBoard(int tr, int tc, int dr, int dc, int size) { if(s

16、ize==1){  // 棋盤方格大小為  , 說明遞歸到最里層 return; } int t=tile++; // 每次遞增 int s=size/2; // 分割棋盤 if(dr

17、; } if(dr=tc+s){ // 檢查特殊方塊是否在右上角子棋盤中 ChessBoard(tr, tc+s, dr, dc, s); } else{ // 不在，將該子棋盤左下角的方塊視為特殊方塊 Board[tr+s-1][tc+s]=t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); } if(dr>=tr+s && dc

18、e{ // 不在，將該子棋盤右上角的方塊視為特殊方塊 Board[tr+s][tc+s-1]=t; ChessBoard(tr+s, tc, tr+s, tc+s-1, s); } if(dr>=tr+s && dc>=tc+s){ // 檢查特殊方塊是否在右下角子棋盤中 ChessBoard(tr+s, tc+s, dr, dc, s); } else{ // 不在，將該子棋盤左上角的方塊視為特殊方塊 Board[tr+s][tc+s]=t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); } } vo

19、id main() { int n; int size;// 棋盤大小 printf(" 請輸入一個(gè)數(shù)字，將為您創(chuàng)建 2^n*2^n 大小的棋盤： "); scanf_s("%d",&n); int x,y; size=(int)pow(2.0,(int)n); printf(" 輸入特殊方格的橫坐標(biāo) :"); scanf_s("%d",&x); printf(" 輸入特殊方格的橫坐標(biāo) :"); scanf_s("%d",&y); ChessBoard(0,0,x,y,size); printf(" 程序運(yùn)行結(jié)果如下所示：

20、 \n"); for(int i=0;i