算法設(shè)計與分析試驗報告棋盤覆蓋問題1

1、貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：算法設(shè)計與分析班級：信計 101 班實驗日期： 2013-9-30姓名： 張 勝學(xué)號： 1007010162指導(dǎo)教師：程欣宇實驗序號：一實驗成績：一、實驗名稱分治算法實驗 - 棋盤覆蓋問題二、實驗?zāi)康募耙?、熟悉遞歸算法編寫；2、理解分治算法的特點；3、掌握分治算法的基本結(jié)構(gòu)。三、實驗環(huán)境Visual C+四、實驗內(nèi)容根據(jù)教材上分析的棋盤覆蓋問題的求解思路，進行驗證性實驗；要求完成棋盤覆蓋問題的輸入、分治求解、輸出。有余力的同學(xué) 嘗試消去遞歸求解。五、算法描述及實驗步驟分治算法原理： 分治算法將大的分解成形狀結(jié)構(gòu)相同的子問題

2、，并且不斷遞歸地分解，直到 子問題規(guī)模小到可以直接求解。棋盤覆蓋問題描述：在一個 2k x 2k 個方格組成的棋盤中恰有一個方格與其他的不同稱為特殊方 格，想要求利用四種 L 型骨牌（每個骨牌可覆蓋三個方格）不相互重疊覆蓋的 將除了特殊方格外的其他方格覆蓋。實驗步驟：1、定 義用 于輸 入和 輸出 的數(shù) 據(jù)結(jié) 構(gòu)；2、完 成分 治算 法的 編寫 ；3、測 試記 錄結(jié) 構(gòu)；4、有余 力的 同學(xué) 嘗試不 改變 輸入 輸出結(jié)構(gòu)，將 遞歸消除 ，并說明能 否不 用棧 ，直 接消 除 遞歸 ，為 什么 ？六、調(diào)試過程及實驗結(jié)果實驗運行結(jié)果：七、總結(jié) 通過本次實驗，我更深的理解了遞歸和分治策略。代碼是書上

3、的算法，加上主 函數(shù)就行了，用的是 C 語言編寫，很長時間沒用了，感覺有點生疏。實驗結(jié)果有 點問題，就是覆蓋棋盤時，并不是按照 1，2，3. 的字符順序，而是按照很亂 的順序輸出字符，這個我不知道怎么解決，就沒解決。八、附錄#include stdio.h#include conio.hint board88 =0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0int; int tile=0

4、; void chessBoard(int tr, int tc, int dr, dc, int size)int t=tile+, s=size/2;if (size=1) return;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 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);main()int i ,j;chessBoard(0,0,5,5,8);for(i=0;i 8;i+)for( j=0;j 8;j+) i