《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二（9頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、學(xué)號(hào)1421050102算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告二學(xué)生姓名Cherish專業(yè)、班級地 理指導(dǎo)教師唐 國 峰成績計(jì)算機(jī)與信息工程學(xué)院軟件工程系2017 年 3 月 28 日實(shí)驗(yàn)二：分治策略運(yùn)用練習(xí)一、實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)是針對分治策略運(yùn)用的算法設(shè)計(jì)及應(yīng)用練習(xí)，旨在加深學(xué)生對該部分知識(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) _姓名”，如“
2、算法設(shè)計(jì)與分析實(shí)驗(yàn)二_09290101_ 張三”。b 壓縮包內(nèi)為一個(gè)“ 算法設(shè)計(jì)與分析實(shí)驗(yàn)二_學(xué)號(hào) _姓名”命名的頂層文件夾，其下為兩個(gè)文件夾，一個(gè)文件夾命名為“源程序”，另一個(gè)文件夾命名為“實(shí)驗(yàn)報(bào)告電子版” 。其下分別放置對應(yīng)實(shí)驗(yàn)成果物。（ 2）打印版提交說明：a 不可隨意更改模板樣式。b 字體：中文為宋體，大小為10 號(hào)字，英文為Time New Roman ，大小為10 號(hào)字。c 行間距：單倍行距。（ 3）提交截止時(shí)間： 2017 年 4 月 11 日 16:00。三、 實(shí)驗(yàn)項(xiàng)目1對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序。要求分別運(yùn)用合并排序和快速排序完成該題目要求。2棋盤覆
3、蓋問題。 （要求N 可由用戶輸入）四、實(shí)驗(yàn)過程（一）題目一：對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序：快速排序題目分析快速排序是冒泡排序的改進(jìn)，以一組雜亂無序的數(shù)字最左邊為樞軸記錄的關(guān)鍵字，最右側(cè)指針若比關(guān)鍵字大，則右側(cè)指針左移，若出現(xiàn)比它小的交換兩指針指向數(shù)的排序完成。算法實(shí)現(xiàn)#include#includevoid quickSort(int a,int l,int r)int i,j,t;i=l; j=r;t=al;/ 樞軸元素t 為數(shù)組最左側(cè)的元素if(lr)return;while(i!=j)/ i 往右移動(dòng)j 往左移動(dòng)當(dāng)指向同一位置時(shí)掃描完成while(aj=t & j
4、i)j-;/ 如果右側(cè)指針元素比軸測元素大，指針元素左移if(ji)/ 確保 i 在j 左邊ai+=aj; / 當(dāng)右側(cè)指針元素比軸測元素小時(shí)，交換兩指針指向數(shù)的位置 while(aii)i+;/ 如果左側(cè)指針元素比軸測元素小，指針元素右移if(ji)/ 確保 i 在j 左邊aj-=ai;/ 當(dāng)左側(cè)指針元素比軸測元素大時(shí)，交換兩指針指向數(shù)的位置ai=t;quickSort(a,l,i-1);/ 對左邊進(jìn)行排序quickSort(a,i+1,r);/ 對右邊進(jìn)行排序void main()int i,n,f100;printf( 請輸入要比較數(shù)字的個(gè)數(shù)：n);scanf_s(%d,&n);for(i
5、 = 0; i n; i +)printf( 請輸入第 %d個(gè)數(shù)字： n,i+1);scanf_s(%d,&fi);quickSort(f,0,n-1);printf( 快速排序的結(jié)果是：n);for(i=0;in;i+)printf(%d ,fi);printf(n);system(pause);getchar();運(yùn)行結(jié)果經(jīng)驗(yàn)歸納結(jié)合以前學(xué)的數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法，較容易理解。題目二：對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序：合并排序題目分析合并排序的基本思想是：將待排序的元素分成大小大相同的兩個(gè)子集合，分別對兩個(gè)子集合進(jìn)行排序，最終將排序好的子集合合并成所要求的拍好序的集合。算法
6、構(gòu)造核心代碼來自書上：MergePass(Type x,Type y,Merge(Type c,Type d,intl,intm, intr)ints, int/ 合并 cl,mn) / 合并大小為和xm+1,r 到y(tǒng)l,rs的相鄰序列子數(shù)組算法實(shí)現(xiàn)#include#includetemplatevoid MergeSort(Type a,int n)Type*b=new Typen;int s=1;while(sn)MergePass(a,b,s,n);/ 將a中的元素合并到數(shù)組bs+=s;MergePass(b,a,s,n); / 將 b中的元素合并到數(shù)組as+=s;templatevoi
7、d 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的相鄰 2字段數(shù)組Merge(x,y,i,i+s-1,i+2*s-1);/ 合并 x
8、i,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 a100,i,n;printf( 請輸入要進(jìn)行合并排序的數(shù)字的個(gè)數(shù):n);scanf_s(%d,&n);for( i=0;in;i+)printf( 請輸入要進(jìn)行合并排序的第%d 個(gè)數(shù)字 :n,i+1);scanf_s(%d,&ai);MergeSort(a,n);printf( 合并排序的結(jié)果:n);for(i=0;in;i+)print
9、f(%d,ai);printf(n);system(pause);運(yùn)行結(jié)果經(jīng)驗(yàn)歸納結(jié)合以前學(xué)的數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法，用心理解還能明白。題目三：棋盤覆蓋問題。（要求 N 可由用戶輸入）題目分析將棋盤平分四部分，將分割后的再一分為四，一直分，直到含有特殊方格，看特殊方格在那一部分中，用一個(gè)L 型股牌覆蓋這3 個(gè)較小棋盤會(huì)合處。算法構(gòu)造算法實(shí)現(xiàn)#include#include#includeint Board100100;/ 用來存放棋盤元素的數(shù)組int tile=1;/L 型骨牌的投放序號(hào)void ChessBoard(int tr, int tc, int dr, int dc, int size
10、)if(size=1)/ 棋盤方格大小為, 說明遞歸到最里層return;int t=tile+;/ 每次遞增int s=size/2; / 分割棋盤if(drtr+s & dctc+s)/ 檢查特殊方塊是否在左上角子棋盤中ChessBoard(tr, tc, dr, dc, s);else/ 不在，將該子棋盤右下角的方塊視為特殊方塊Boardtr+s-1tc+s-1=t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s);if(dr=tc+s)/ 檢查特殊方塊是否在右上角子棋盤中ChessBoard(tr, tc+s, dr, dc, s);else/ 不在，將該子棋
11、盤左下角的方塊視為特殊方塊 Boardtr+s-1tc+s=t;ChessBoard(tr, tc+s, tr+s-1, tc+s, s);if(dr=tr+s & dc=tr+s & dc=tc+s) / 檢查特殊方塊是否在右下角子棋盤中 ChessBoard(tr+s, tc+s, dr, dc, s);else/ 不在，將該子棋盤左上角的方塊視為特殊方塊Boardtr+stc+s=t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s);void main()int n;int size;/ 棋盤大小printf( 請輸入一個(gè)數(shù)字，將為您創(chuàng)建 2n*2n 大小的棋盤
12、： ); 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é)果如下所示：n);for(int i=0;isize;i+)for(int j=0;jsize;j+)printf(%dt,Boardij);printf(n);printf(n);system(pause);運(yùn)行結(jié)果經(jīng)驗(yàn)歸納結(jié)合書上核心代碼，理解起來還是有些吃力。實(shí)驗(yàn)總結(jié)本次實(shí)驗(yàn)較上次難，也是一個(gè)循序漸進(jìn)的過程，認(rèn)真學(xué)習(xí)，受益匪淺。
《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二
