棋盘覆盖.docx
《棋盘覆盖.docx》由会员分享，可在线阅读，更多相关《棋盘覆盖.docx（10页珍藏版）》请在冰点文库上搜索。
棋盘覆盖
课程设计说明书
设计题目：
实现分治法求解棋盘问题
专业：
班级：
设计人：
山东科技大学
2013年11月29日
课程设计任务书
学院：
专业：
班级：
姓名：
一、课程设计题目：
实现分治法求解棋盘问题
二、课程设计主要参考资料
（1）计算机算法设计与分析（第三版）王晓东著
（2）
三、课程设计应解决的主要问题
（1）实现分治法求解棋盘问题
（2）
（3）
四、课程设计相关附件（如：
图纸、软件等）：
（1）实现分治法求解棋盘问题的流程图
（2）
五、任务发出日期：
2013-11-21课程设计完成日期：
指导教师签字：
系主任签字：
指导教师对课程设计的评语
成绩：
指导教师签字：
年月日
二分查找程序的实现
一、设计目的
算法设计与分析是计算机科学与技术专业的软件方向的必修课。
同时，算法设计与分析既有较强的理论性，也有较强的实践性。
算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。
用分治法，设计解决棋盘覆盖问题的一个简捷的算法。
通过解决棋盘覆盖问题，进一步学习分治策略。
二、设计要求
在一个2
×2
个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
显然特殊方格在棋盘上出现的位置有4
种情形。
因而对任何k>=0，有4
种不同的特殊棋盘。
图1中的特殊棋盘式当k=2时16个特殊棋盘中的一个。
图1
在棋盘覆盖问题中，要用到图2所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
图2
三、设计说明
（一）、需求分析
用分治法，设计解决棋盘覆盖问题的一个简捷的算法。
该算法的流程图如下：
（二）、概要设计
通过分析易知，在任意一个2
×2
的棋盘覆盖中，用到的L型骨牌个数恰为（4
-1）/3。
当k>0时，将2
×2
的棋盘分割为4个2
×2
子棋盘,如图（a）所示。
图（a）
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。
为将这3个无特殊方格子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图（b）所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。
递归的使用这种分割，直至棋盘简化为1×1的棋盘。
图（b）
数据结构设计：
（1）棋盘：
可以用一个二维数组来Board[size][size]表示一个棋盘，其中size=2
。
为了在递归的过程中使用同一个棋盘，将数组Board设置为全局变量。
（2）子棋盘：
子棋盘由原始棋盘数组Board的行下标tr，列下标tc表示。
（3）特殊方格：
用行下标dr，列下标dc，表示特殊方格的坐标，用Board[dr][dc]表示特殊方格。
（4）L型骨牌：
共有四种不同类型的骨牌，所以用数字1-4表示骨牌类型，同一个骨牌由三个方格组成，这三个人方格用同一个编号，如三个1表示┏，三个2表示┓，三个3表示┗，三个4表示┛。
由于只有4种类型的骨牌，所以我稍微修改了一下算法，在判断出特殊方格在左上角之后，就直接覆盖右下角，然后再递归的调用算法覆盖其他子棋盘；在判断出特殊方格在右上角之后，就直接覆盖左下角，然后再递归的调用算法覆盖其他子棋盘；在判断出特殊方格在左下角之后，就直接覆盖右上角，然后再递归的调用算法覆盖其他子棋盘；在判断出特殊方格在右下角之后，就直接覆盖左上角，然后再递归的调用算法覆盖其他子棋盘。
由于棋盘大小是用户自己定义的，所以我使用了一个二维指针，然后用malloc函数为其分配动态地址空间。
（三）、详细设计
#include
#include
#include
usingnamespacestd;
int**Board;//棋盘
voidChessBoard（inttr,inttc,intdr,intdc,intsize）{
if（size==1）
return;
ints=size/2;//分割棋盘
if（dr//特殊方格在此棋盘左上角，覆盖右下角
Board[tr+s-1][tc+s]=4;
Board[tr+s][tc+s]=4;
Board[tr+s][tc+s-1]=4;
ChessBoard（tr,tc,dr,dc,s）;
ChessBoard（tr,tc+s,tr+s-1,tc+s,s）;
ChessBoard（tr+s,tc+s,tr+s,tc+s,s）;
ChessBoard（tr+s,tc,tr+s,tc+s-1,s）;
}
if（dr=tc+s）{
//特殊方格在此棋盘右上角，覆盖左下角
Board[tr+s-1][tc+s-1]=3;
Board[tr+s][tc+s-1]=3;
Board[tr+s][tc+s]=3;
ChessBoard（tr,tc+s,dr,dc,s）;
ChessBoard（tr,tc,tr+s-1,tc+s-1,s）;
ChessBoard（tr+s,tc,tr+s,tc+s-1,s）;
ChessBoard（tr+s,tc+s,tr+s,tc+s,s）;
}
if（dr>=tr+s&&dc//特殊方格在此棋盘左下角，覆盖右上角
Board[tr+s-1][tc+s-1]=2;
Board[tr+s-1][tc+s]=2;
Board[tr+s][tc+s]=2;
ChessBoard（tr+s,tc,dr,dc,s）;
ChessBoard（tr,tc,tr+s-1,tc+s-1,s）;
ChessBoard（tr,tc+s,tr+s-1,tc+s,s）;
ChessBoard（tr+s,tc+s,tr+s,tc+s,s）;
}
if（dr>=tr+s&&dc>=tc+s）{
//特殊方格在此棋盘右下角，覆盖左上角
Board[tr+s][tc+s-1]=1;
Board[tr+s-1][tc+s-1]=1;
Board[tr+s-1][tc+s]=1;
ChessBoard（tr+s,tc+s,dr,dc,s）;
ChessBoard（tr+s,tc,tr+s,tc+s-1,s）;
ChessBoard（tr,tc,tr+s-1,tc+s-1,s）;
ChessBoard（tr,tc+s,tr+s-1,tc+s,s）;
}
}
intmain（）{
inta,b,size;
cout<<"┏用1来表示，┓用2来表示，┗用3来表示，┛用4来表示"<cout<<"请输入棋盘大小：
";
cin>>size;
cout<<"请输入特殊方格的坐标：
";
cin>>a>>b;
Board=（int**）malloc（sizeof（int*）*size）;
for（inti=0;iBoard[i]=（int*）malloc（sizeof（int）*size）;
}
ChessBoard（0,0,a,b,size）;
Board[a][b]=0;
for（inti=0;ifor（intj=0;jcout<cout<}
return0;
}
四、运行结果及分析
运行结果：
结果中分别用数字1-4来表示骨牌的类型，三个1表示┏，三个2表示┓，三个3表示┗，三个4表示┛。
分析：
设T（k）是算法ChessBoard覆盖一个棋盘所需的时间，则从算法的分治策略可知，T（k）满足如下递归方程：
解此方程可得T（k）=O（4）。
五、总结
通过这次试验，解决了棋盘覆盖问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。
升级会员 