用分治法求解棋盘覆盖问题.docx

本文格式为Word版，下载可任意编辑用分治法求解棋盘覆盖问题 棋盘笼罩问题 问题描述： 在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格 为特殊方格鲜明，特殊方格在棋盘中展现的位置有4k中情形，因而有4k中不同的棋盘，图（a）所示是k=2时16种棋盘中的一个棋盘笼罩问题要求用图（b）所示的4中不同外形的L型骨牌笼罩给定棋盘上除特殊方格以外的全体方格，且热河亮哥L型骨牌不得重复笼罩 图（b） 图 （a） 问题分析： K>0时，可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘这样划分后，由于原棋盘只 有一个特殊方格，所以，这4个子棋盘中只有1个子棋盘中有特殊方格，其余3个子棋盘中没有特殊方格为了将这3个没有特殊方格的子棋盘转化成为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌笼罩这3个较小的棋盘的会合处，从而将原问题转化为4个较小规模的棋盘笼罩问题递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘 问题求解： 下面介绍棋盘笼罩问题中数据布局的设计。

（1） 棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中size=2k为了 在递归处理的过程中使用同一个棋盘，将数组board设为全局变量 （2） 子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上 角的下标tr、tc和棋盘大小s表示 （3） 特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组 board中的下标 （4） L型骨牌：一个2k×2k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数 为（4k-1）/3，将全体L型骨牌从1开头连续编号，用一个全局变量tile表示 C语言源码： /*author: 彭洪伟 *studentID:0950310006 *class:计科1班 *problem:分治法解决棋盘笼罩问题 */ #include #include int tile=1; //记录骨牌的型号 int board[20][20]={0}; //存储棋盘被笼罩的处境 void ChessBoard(int tr,int tc,int dr,int dc,int size) { //tr和tc是棋盘左上角的下标,dr和dc是特殊方格的下标,size是棋盘的大小 int t=0; int s; if (size==1)return; t=tile++; s=size/2; //划分棋盘 //笼罩左上角棋盘 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,s); } //笼罩左下角棋盘 if (dr>=tr+s else { board[tr+s][tc+s-1]=t; ChessBoard(tr+s,tc,tr+s,tc+s-1,s); } //笼罩右下角棋盘 if (dr>=tr+s else { board[tr+s][tc+s]=t; ChessBoard(tr+s,tc+s,tr+s,tc+s,s); } } int main() { int k,x,y; printf(\请输入棋盘的规模K：\ scanf(\ printf(\请输入特殊方格的下标x,y：\ scanf(\ ChessBoard(0,0,x,y,pow(2,k)); for(int i=0; i 运行结果截图： — 3 —。