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

课程名称：算法设计与分析班级：实验日期：姓名：学号：指导教师：实验序号：一实验成绩：一、实验名称分治算法实验-棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境VisualC++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？六、调试过程及实验结果调试过程中有一点点的语法错误，如定义变量tile应定义为全局的整形变量，数组Board也是。另外输入的size应是k2，特殊方格的行标和列标都应小于size,如果输入的size不是k2的话，很显然结果不是我们要的。本程序的结果中我用-1表示特殊方格。实验结果为：七、总结此次实验的算法已经从书本上得到，代码是网上找的。但是我已经读懂了。棋盘覆盖的分治策略算法也简单易懂，是我们学习分治策略的思想的典型例子。棋盘覆盖的分治策略算法利用四种L型骨牌，代码有解释。八、附录#includestdio.hinttile=0;intBoard[100][100];voidChessBoard(inttr,inttc,intdr,intdc,intsize);voidmain(){intsize,dr,dc,i,j;printf(inputsize,dr,dc:\n);//输入scanf(%d,%d,%d,&size,&dr,&dc);Board[dr][dc]=-1;ChessBoard(0,0,dr,dc,size);printf(output:\n);//输出for(i=0;isize;i++){for(j=0;jsize;j++)printf(%d,Board[i][j]);printf(\n);}}//实现算法voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,s=size/2;if(drtr+s&&dctc+s)ChessBoard(tr,tc,dr,dc,s);else{Board[tr+s-1][tc+s-1]=t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(drtr+s&&dc=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&&dctc+s)ChessBoard(tr+s,tc,dr,dc,s);else{Board[tr+s][tc+s-1]=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}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);}}