分治算法实验---棋盘覆盖问题

1、课程名称：算法设计与分析班级：实验日期：姓名：学号：指导教师： 实验序号：一实验成绩：一、实验名称分治算法实验 - 棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境Visual C+ 四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的

2、不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？6、 调试过程及实验结果 调试过程中有一点点的语法错误，如定义变量tile应定义为全局的整形变量，数组Board也是。另外输入的size应是，特殊方格的行标和列标都应小于size,如果输入的size不是的话，很显然结果不是我们要的。本程序的结果中我用-1表示特殊方格。实验结果为：七、总结 此次实验的算法已经

3、从书本上得到，代码是网上找的。但是我已经读懂了。棋盘覆盖的分治策略算法也简单易懂，是我们学习分治策略的思想的典型例子。棋盘覆盖的分治策略算法利用四种L型骨牌，代码有解释。八、附录#includeint tile=0;int Board100100;void ChessBoard(int tr,int tc,int dr,int dc,int size);void main()int size,dr,dc,i,j;printf(input size,dr,dc:n);/输入scanf(%d,%d,%d,&size,&dr,&dc);Boarddrdc=-1;ChessBoard(0,0,dr,d

4、c,size);printf(output:n);/输出for(i=0;isize;i+) for(j=0;jsize;j+) printf(%d ,Boardij); printf(n); /实现算法void ChessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return;int t=tile+,s=size/2;if(drtr+s&dctc+s) ChessBoard(tr,tc,dr,dc,s);elseBoardtr+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);elseBoardtr+s-1tc+s=t;ChessBoard(tr,tc+s,tr+s-1,tc+s-1,s);if(dr=tr+s&dc=tr+s&dc=tc+s) ChessBoard(tr+