资源描述：
《算法分析解题报告--棋盘问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、河南理工大学计算机学院算法分析解题报告棋盘覆盖问题专业：软件工程.net11-03班学号：311109070314姓名：李少伟1•问题描述：在-个2"kX2"k(k20)个方格组成的棋盘中，恰有-个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能岀现的位置有42种，因而有4k种不同的棋盘，下图所示是k=2时16种棋盘中的一个。棋盘覆盖问题(chesscoverproblem)要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。Q)k二2时&田(
2、"4种1骨牌2.解题思路关键技术：分治与递归分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格(这句话很重耍)，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为11的子棋盘。3•解决方案数据结构设计：(1)棋盘：可以一个二维数组
3、board[size][size]表示一个棋盘，其中，size二2鼻。为了在递归处理的过程中使用同一个棋盘，将数组board设置为全局变量(2)子棋盘：子棋盘由原始棋盘数组board的行下标列下标tc(3)特殊方格：用board[dr][de]表示特殊方格，dr和de表示该特殊方格的在二维数组board中的下标(4)L型骨牌：一个(2飞)(2d)的棋盘中有一个特殊方格，所以用到L型骨牌的个数为(42-1)/3,将所有L型骨牌从1开始连续编号，同一个骨牌有3个方格组成，这3个方格用同一个编号。4•源代码〃问题描述：在一个
4、27X22(k^O)个方格组成的棋盘中，恰有…个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有47种，因而有4k种不同的棋盘，图4.10(a)所示是k二2时16种棋盘中的一个。棋盘覆盖问题(chesscoverproblem)要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。〃解题思路：分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个了棋盘均包含一个特殊方格（这句话很重要），从而将原问题分解为规模较小的棋盘覆盖问
5、题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为11的子棋盘。〃关键技术：分治与递归〃开发语言：C++〃运行环境：DEV-C++5〃开发日期：2014年4月10日#include#include#defineN100intboard[N][N];intt;voidC
6、hessBoard(inttr,inttc,intdr,intde,intsize)intm,s;if(size=l)return;m=++t;s=size/2;if(drtc+s)chessboard(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s]=
7、m;chessboard(tr,tc,tr+s-1,tc+s,s);}if(dr>tr+s&&dcvtc+s)chessboard(tr,tc,dr,dc,s);elseboard[tr+s][tc+s-l]=m;chessboard(tr,tc,tr4-s,tc-t-s-l,s);}if(dr>tr+s&&dc>tc+s)chessboard(tr,tc,dr,dc,s);else{board[tr+s][tc+s]=m;chessboard(tr,tc,tr+s,tc+s,s);voidprint(intn){in
8、ti,j；for(i=0;ivn;i++)for(j=O;jvn;j++)printf(n%dn,board[i][j]);printf(nn);intmain()inttr,tc,dr,dc,size;tr=O;tc=O;pringtf(n请输入棋盘的大小”)；scanf(n%d'，&size);pringtf(n请输入特殊
