算法分析與設計-遞歸與分治策略

1、專業(yè)課程實驗報告課程名稱：算法分析與設計開課學期：2014 至 2015 學年第1 學期專業(yè)：軟件工程年級班級：2012級03班學生姓名：李明洋 學號：222012321062053實驗教師：曹嚴元計算機與信息科學學院軟件學院實驗項目名稱遞歸與分治策略實驗時間2014年10月31日|實驗類型驗證性設計性綜合|性一、實驗目的了解并掌握遞歸的概念，遞歸算法的基本思想；掌握分治法的基本思想方法；了解適用于用分治法求解的問題類型，并能用遞歸或非遞歸的方式設計相應的分治 法算法；掌握分治法復雜性分析方法，比較同一個問題的遞歸算法與循環(huán)迭代算法的效率。二、實驗要求預習實驗指導書及教材的有關內容，掌握分治法

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

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

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

5、r, int dc, int size )if ( size=1 )棋盤方格大小為1,說明遞歸到最里層return;int t=tile+;每次遞增 1int s=size/2;/棋盤中間的行、列號(相等的)檢查特殊方塊是否在左上角子棋盤中 TOC o 1-5 h z 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

6、=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=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 );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. 三、測試數據和執(zhí)行結果（在給定數據下，執(zhí)行操作、算法和程序的結果，可 使用數據、圖表、截圖等給出）E:program mi“g琪坦葛蓋分治法.exe莆*%H豪臂京蠢擅坐標:2 333448893344889932248779526010107115566110111113131411181919131214141818171915121216201717211515161620202121Processreturned0 e?xection time = 10.726Pressf an0解得此遞歸方程可得T（k） =0（4飛）。由于覆蓋一個2k*2k棋盤所需的L型骨牌個數為（4”k 1）/3,故算法ChessBoard是一個在漸進意義下最優(yōu)的算法通過這次試驗，更多的了解了分治法解題的思路就是將