1、專業(yè)課程實(shí)驗(yàn)報(bào)告課程名稱：算法分析與設(shè)計(jì)開(kāi)課學(xué)期：2014 至 2015 學(xué)年第1 學(xué)期專業(yè)：軟件工程年級(jí)班級(jí)：2012級(jí)03班學(xué)生姓名：李明洋 學(xué)號(hào)：222012321062053實(shí)驗(yàn)教師：曹嚴(yán)元計(jì)算機(jī)與信息科學(xué)學(xué)院軟件學(xué)院實(shí)驗(yàn)項(xiàng)目名稱遞歸與分治策略實(shí)驗(yàn)時(shí)間2014年10月31日|實(shí)驗(yàn)類型驗(yàn)證性設(shè)計(jì)性綜合|性一、實(shí)驗(yàn)?zāi)康牧私獠⒄莆者f歸的概念，遞歸算法的基本思想；掌握分治法的基本思想方法；了解適用于用分治法求解的問(wèn)題類型，并能用遞歸或非遞歸的方式設(shè)計(jì)相應(yīng)的分治 法算法；掌握分治法復(fù)雜性分析方法，比較同一個(gè)問(wèn)題的遞歸算法與循環(huán)迭代算法的效率。二、實(shí)驗(yàn)要求預(yù)習(xí)實(shí)驗(yàn)指導(dǎo)書(shū)及教材的有關(guān)內(nèi)容，掌握分治法

2、的基本思想；嚴(yán)格按照實(shí)驗(yàn)內(nèi)容進(jìn)行實(shí)驗(yàn)，培養(yǎng)良好的算法設(shè)計(jì)和編程的習(xí)慣；認(rèn)真聽(tīng)講，服從安排，獨(dú)立思考并完成實(shí)驗(yàn)。三、實(shí)驗(yàn)內(nèi)容與設(shè)計(jì)(主要內(nèi)容，操作步驟、算法描述或程序代碼)用分治策略實(shí)現(xiàn)棋盤(pán)覆蓋問(wèn)題。選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)表示問(wèn)題；根據(jù)分治法的基本原理，寫(xiě)出棋盤(pán)覆蓋問(wèn)題的偽碼算法；編制C+或JAVA等高級(jí)語(yǔ)言程序?qū)崿F(xiàn)偽碼算法；上機(jī)運(yùn)行程序，驗(yàn)證算法的正確性，并分析算法的時(shí)空復(fù)雜性。用分治策略，可以設(shè)計(jì)解決棋盤(pán)問(wèn)題的一個(gè)簡(jiǎn)介算法。當(dāng)k0時(shí)，可以將2k *2飛棋盤(pán)分割為4個(gè)2k-1 * 2k-1子棋盤(pán)。由棋盤(pán)覆蓋問(wèn)題 得知，特殊方格必位于4個(gè)較小的子棋盤(pán)中，其余3個(gè)子棋盤(pán)中無(wú)特殊方格。為了將3個(gè)無(wú) 特

3、殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)可以將一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤(pán)的會(huì)合處，所以， 這3個(gè)子棋盤(pán)上被L型覆蓋的方格就成為給棋盤(pán)上的特殊方格，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較 小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸的使用這種分割，直至棋盤(pán)簡(jiǎn)化為1*1棋盤(pán)為止。1、數(shù)據(jù)說(shuō)明：tr :棋盤(pán)上左上角方格的行號(hào)tc :棋盤(pán)上左上角方格的列號(hào)dr：特殊方格所在的行號(hào)dc：特殊方格所在的列號(hào)定義了全局變量tile，用于進(jìn)行覆蓋。區(qū)分4種不同L類型的骨牌，初始值為0. Board口 數(shù)組用來(lái)表示棋盤(pán)2、函數(shù)說(shuō)明ChessBoard函數(shù)實(shí)現(xiàn)了遞歸的將棋盤(pán)劃分為子棋盤(pán)，并將棋盤(pán)進(jìn)行覆蓋。main()函數(shù)用來(lái)進(jìn)行輸入棋盤(pán)的大小和特殊棋盤(pán)

4、的位置。使用 memset(Board,0,sizeof(Board)將 Board數(shù)組清零使用setw()函數(shù)控制輸出格式C+代碼如下：1.#include2.using namespace std;3.int tile=1;/L型骨牌的編號(hào)(遞增)4.int board100100; 棋盤(pán)5./*6.*遞歸方式實(shí)現(xiàn)棋盤(pán)覆蓋算法7.*輸入?yún)?shù)：* tr-當(dāng)前棋盤(pán)左上角的行號(hào)* tc-當(dāng)前棋盤(pán)左上角的列號(hào)* dr-當(dāng)前特殊方格所在的行號(hào)* dc-當(dāng)前特殊方格所在的列號(hào)* size:當(dāng)前棋盤(pán)的：2W13.13.14. void chessBoard ( int tr, int tc, int d

5、r, int dc, int size )if ( size=1 )棋盤(pán)方格大小為1,說(shuō)明遞歸到最里層return;int t=tile+;每次遞增 1int s=size/2;/棋盤(pán)中間的行、列號(hào)(相等的)檢查特殊方塊是否在左上角子棋盤(pán)中 TOC o 1-5 h z if ( drtr+s & dctc+s )在chessBoard ( tr, tc, dr, dc, s );else/不在，將該子棋盤(pán)右下角的方塊視為特殊方塊boardtr+s-1tc+s-1=t;chessBoard ( tr, tc, tr+s-1, tc+s-1, s );檢查特殊方塊是否在右上角子棋盤(pán)中if ( dr

6、=tc+s )在chessBoard ( tr, tc+s, dr, dc, s );else/不在，將該子棋盤(pán)左下角的方塊視為特殊方塊boardtr+s-1tc+s=t;chessBoard ( tr, tc+s, tr+s-1, tc+s, s );檢查特殊方塊是否在左下角子棋盤(pán)中if(dr=tr+s&dc=tr+s&dc=tc+s)在chessBoard ( tr+s, tc+s, dr, dc, s );else/不在，將該子棋盤(pán)左上角的方塊視為特殊方塊boardtr+stc+s=t;chessBoard ( tr+s, tc+s, tr+s, tc+s, s );53.void ma

7、in()int size;coutsize;int index_x,index_y;coutindex_xindex_y;chessBoard ( 0,0,index_x,index_y,size );for ( int i=0; isize; i+ )64.65.for ( int j=0; jsize; j+ )66.67.coutboardij/t;coutendl;68.69. 三、測(cè)試數(shù)據(jù)和執(zhí)行結(jié)果（在給定數(shù)據(jù)下，執(zhí)行操作、算法和程序的結(jié)果，可 使用數(shù)據(jù)、圖表、截圖等給出）E:program mi“g琪坦葛蓋分治法.exe莆*%H豪臂京蠢擅坐標(biāo):2 333448893344889932248779526010107115566110111113131411181919131214141818171915121216201717211515161620202121Processreturned0 e?xection time = 10.726Pressf an0解得此遞歸方程可得T（k） =0（4飛）。由于覆蓋一個(gè)2k*2k棋盤(pán)所需的L型骨牌個(gè)數(shù)為（4”k 1）/3,故算法ChessBoard是一個(gè)在漸進(jìn)意義下最優(yōu)的算法通過(guò)這次試驗(yàn)，更多的了解了分治法解題的思路就是將