《算法設(shè)計(jì)與分析》實(shí)驗(yàn)二

學(xué)號(hào)1421050102算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告二學(xué)生姓名Cherish專業(yè)、班級(jí)地 理指導(dǎo)教師唐 國 峰成績計(jì)算機(jī)與信息工程學(xué)院軟件工程系2017 年 3 月 28 日實(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壓縮包內(nèi)為一個(gè)“ 算法設(shè)計(jì)與分析實(shí)驗(yàn)二其下為兩個(gè)文件夾，一個(gè)文件夾命名為“源程序”報(bào)告電子版” 。其下分別放置對(duì)應(yīng)實(shí)驗(yàn)成果物。_學(xué)號(hào) _姓名”命名的頂層文件夾，另一個(gè)文件夾命名為“實(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對(duì)用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序。要求分別運(yùn)用合并排序和快速排序完成該題目要求。2棋盤覆蓋問題。 （要求N 可由用戶輸入）四、實(shí)驗(yàn)過程（一）題目一：對(duì)用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序：快速排序題目分析快速排序是冒泡排序的改進(jìn)，以一組雜亂無序的數(shù)字最左邊為樞軸記錄的關(guān)鍵字，最右側(cè)指針若比關(guān)鍵字大，則右側(cè)指針左移，若出現(xiàn)比它小的交換兩指針指向數(shù)的排序完成。算法實(shí)現(xiàn)#include<stdio.h>#include<stdlib.h>void quickSort(int a,int l,int r)int i,j,t;i=l; j=r;t=al;/ 樞軸元素t 為數(shù)組最左側(cè)的元素if(l>r)return;while(i!=j)/ i 往右移動(dòng)j 往左移動(dòng)當(dāng)指向同一位置時(shí)掃描完成while(aj>=t && j>i)j-;/ 如果右側(cè)指針元素比軸測(cè)元素大，指針元素左移if(j>i)/ 確保 i 在j 左邊ai+=aj; / 當(dāng)右側(cè)指針元素比軸測(cè)元素小時(shí)，交換兩指針指向數(shù)的位置 while(ai<=t && j>i)i+;/ 如果左側(cè)指針元素比軸測(cè)元素小，指針元素右移if(j>i)/ 確保 i 在j 左邊aj-=ai;/ 當(dāng)左側(cè)指針元素比軸測(cè)元素大時(shí)，交換兩指針指向數(shù)的位置ai=t;quickSort(a,l,i-1);/ 對(duì)左邊進(jìn)行排序quickSort(a,i+1,r);/ 對(duì)右邊進(jìn)行排序void main()int i,n,f100;printf(" 請(qǐng)輸入要比較數(shù)字的個(gè)數(shù)：n");scanf_s("%d",&n);for(i = 0; i <n; i +)printf(" 請(qǐng)輸入第 %d個(gè)數(shù)字： n",i+1);scanf_s("%d",&fi);quickSort(f,0,n-1);printf(" 快速排序的結(jié)果是：n");for(i=0;i<n;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)用算法，較容易理解。題目二：對(duì)用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序：合并排序題目分析合并排序的基本思想是：將待排序的元素分成大小大相同的兩個(gè)子集合，分別對(duì)兩個(gè)子集合進(jìn)行排序，最終將排序好的子集合合并成所要求的拍好序的集合。算法構(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<stdio.h>#include<stdlib.h>template<class Type>void MergeSort(Type a,int n)Type*b=new Typen;int s=1;while(s<n)MergePass(a,b,s,n);/ 將a中的元素合并到數(shù)組bs+=s;MergePass(b,a,s,n); / 將 b中的元素合并到數(shù)組as+=s;template<class Type>void 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(ci<=cj)dk+=ci+;elsedk+=cj+;if(i>m)for(int q=j;q<=r;q+)dk+=cq;elsefor(int q=i;q<=m;q+)dk+=cq;template<class Type>void 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,i+s-1和xi+s,i+2*s-1到y(tǒng)i,i+2*s-1i=i+2*s;if(i+s<n) /處理剩下的元素少于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(" 請(qǐng)輸入要進(jìn)行合并排序的數(shù)字的個(gè)數(shù):n");scanf_s("%d",&n);for( i=0;i<n;i+)printf(" 請(qǐng)輸入要進(jìn)行合并排序的第%d 個(gè)數(shù)字 :n",i+1);scanf_s("%d",&ai);MergeSort(a,n);printf(" 合并排序的結(jié)果:n");for(i=0;i<n;i+)printf("%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<stdio.h>#include<stdlib.h>#include<cmath>int Board100100;/ 用來存放棋盤元素的數(shù)組int tile=1;/L 型骨牌的投放序號(hào)void ChessBoard(int tr, int tc, int dr, int dc, int size)if(size=1)/ 棋盤方格大小為, 說明遞歸到最里層return;int t=tile+;/ 每次遞增int s=size/2; / 分割棋盤if(dr<tr+s && dc<tc+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<tr+s && dc>=tc+s)/ 檢查特殊方塊是否在右上角子棋盤中ChessBoard(tr, tc+s, dr, dc, s);else/ 不在，將該子棋盤左下角的方塊視為特殊方塊 Boardtr+s-1tc+s=t;ChessBoard(tr, tc+s, tr+s-1, tc+s, s);if(dr>=tr+s && dc<tc+s) / 檢查特殊方塊是否在左下角子棋盤中 ChessBoard(tr+s, tc, dr, dc, s);else/ 不在，將該子棋盤右上角的方塊視為特殊方塊 Boardtr+stc+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/ 不在，將該子棋盤左上角的方塊視為特殊方塊Boardtr+stc+s=t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s);void main()int n;int size;/ 棋盤大小printf(" 請(qǐng)輸入一個(gè)數(shù)字，將為您創(chuàng)建 2n*2n 大小的棋盤： "); 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;i<size;i+)for(int j=0;j<size;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í)，受益匪淺。