算法設(shè)計(jì)與分析試驗(yàn)報(bào)告棋盤(pán)覆蓋問(wèn)題1

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

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

3、的算法，加上主 函數(shù)就行了，用的是 C 語(yǔ)言編寫(xiě)，很長(zhǎng)時(shí)間沒(méi)用了，感覺(jué)有點(diǎn)生疏。實(shí)驗(yàn)結(jié)果有 點(diǎn)問(wèn)題，就是覆蓋棋盤(pán)時(shí)，并不是按照 1，2，3. 的字符順序，而是按照很亂 的順序輸出字符，這個(gè)我不知道怎么解決，就沒(méi)解決。八、附錄#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