算法实验报告--棋盘覆盖.docx

《算法实验报告--棋盘覆盖.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法实验报告算法分析与设计实验报告实验名称：棋盘覆盖实验日期：2011/03/06学生姓名：学生学号：算法实验报告一、实验目的在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。二、实验环境Windows7+VisualStudio2010三、实验内容1.设计思路当k>0时，将2k*2k的棋盘分割为4个2（k-1）*2（k-1）子棋盘。特殊方格必位于4个较小棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘

2、化为特殊棋盘，我们用一个L型骨牌覆盖这3个较小的棋盘的回合处，这3个子棋盘被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题化为4个小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘化简为1*1棋盘。2.相关模块#include#includeusingnamespacestd;voidChessBoard(int,int,int,int,int);int**board;//棋盘inttile=1;//L型骨牌编号voidmain(){intsize=0;introw

3、,column;cout<<"Inputthesizenofthechessboard(n*n):"<>size;cout<<"Inputthepositionofthespecialcheck:"<>row>>column;算法实验报告board=newint*[size];for(inti=0;i

4、,column,size);cout<<"Outputthechessboard(0representsthespecialone):"<

5、,intdr,intdc,intsize){//tr:左上角行号//tc:左上角列号//dr:特殊方格行号//dr:特殊方格列号if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角棋牌if(dr

6、tr+s-1,tc+s-1,s);}算法实验报告//右上角if(dr=tc+s)ChessBoard(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s-1,s);}//左下角if(dr>=tr+s&&dc

7、/右下角if(dr>=tr+s&&dc>=tc+s)ChessBoard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}四、实验结果分析及结论由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4k-1）/3，故此算法是一个在算法实验报告渐近意义下最优的算法。