《《算法設(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í),受益匪淺。