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