C课题设计报告残缺棋阵.doc

暑假课题设计说明书题 目：残缺棋阵覆盖问题学生姓名：学 号：专 业：班 级：指导教师：2013年7月31日残缺棋阵覆盖问题摘要摘要：残缺棋阵问题要求用三格板（triominoes）覆盖残缺棋盘 在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必 须覆盖其他所有的方格用分而治之方法解决此问题，即为了解决一个大的问题，可以：1）把它分成两个或多个更小的问题；2）分别解决每个小问题；3）把各 小问题的解答组合起来，即可得到原问题的解答小问题通常与原问 题相似，可以递归地使用分而治之策略来解决选用递归算法，先构 造一个函数，专门用与递归实现棋盘补充问题第一步，取棋盘中点, 先判断残缺点的X, Y在哪一个区域，同时可覆盖三个小方格，即四 个区域分别设定每一个区域的左上角，右下角和缺点将它们分别存 入一个数组中棋盘划分一次，棋子增加3个，棋盘减少一个，同时 又新增加4个棋盘递归函数调用，直至所有的子棋盘都被覆盖关键词：残缺点，三格板，分而治之，递归数据结构课程设计任务书针对本课程设计，完成以下课程设计任务:1、 熟悉系统实现工具和上级环境2、 根据课程设计任务，查阅相关资料3、 针对所选课题完成以下工作：(1) 、需求分析(2) 、概要设计(3) 、详细设计(4) 、编写源程序(5) 、静态走查程序和上机调试程序4、 书写上述文档和撰写课程设计报告。

91344第一章问题描述问题描述：残缺棋盘是一个有2"kX2"k (k^l)个方格的棋盘，其中恰有 一个方格残缺如图给出21时各种可能的残缺棋盘，其中残缺的方 格用阴影表示问题要求：残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘在此 覆盖中要求：1) 两个三格板不能重叠2) 三格板不能覆盖残缺方格，但必须覆盖其他所有的方格在这种限制条件下,所需要的三格板总数为(2"kX2"k -1)/3可以验证(2"kX2"k -1)/3是一个整数k为0的残缺棋盘很容易被 覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0当 E1时，正好存在3个非残缺的方格，并且这三个方格可用任意一方 的三格板来覆盖第二章需求分析从问题描述可以发现：当残缺方格在第1个子棋盘,用①号三格板覆盖其余三个子棋盘 的交界方格，可以使另外三个子棋盘转化为独立子问题；当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆 盖当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆 盖当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆 盖，这样就使另外三个子棋盘转化为独立子问题1号板 2号板 3号板 4号板 田匚田•同样地k=l, 2, 3, 4 都是如此：k=l为停止条件。

• 一个4*4的残缺棋盘及其解u~im isfflffi 彳i I i丨i i;卜百讷 (第三章概要设计本程序有四个模块，调用关系如下：结束第四章 详细设计主要函数：(1 )、void chessBoard(int tr, int tc, int dr, int de, int size)//tr棋盘中左上角方格所在行，tc棋盘中左上角方格所在列，dr特殊点的行下标，de特殊 点的列下标size棋阵的行数2)、int main()；算法分析：void chessBoard(int tr, int tc, int dr, int de, int size){if (size==l)return;int t = tile++; 〃L 型骨牌号int s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr= tc + s) //特殊方格在此棋盘中chessBoard(tr, tc+s, dr, de, s);else //此棋盘中无特殊方格board[tr + s - l][tc + s] = t; 〃用t号L型骨牌覆盖左下角chessBoard(tr, tc+s, tr+s-1, tc+s, s);// 覆盖其余方格// 覆盖左下角子棋盘辻(dr >= tr + s && de < tc + s) //特殊方格在此棋盘中chessBoard(tr+s, tc, dr, de, s);else //此棋盘中无特殊方格{board[tr + s][tc + s- l]=t; 〃用t号L型骨牌覆盖右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s);// 覆盖其余方格}// 覆盖右下角子棋盘if (dr >= tr + s && de >= tc + s) //特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, de, s);else{board[tr + s][tc + s] = t; //用t号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); // 覆盖其余方格}}本问题的算法核心是找到棋阵的“中心点”，然后判断在4个矩 形区域里的格子状态，来决定用哪种3格板来填充。

递归寻找“中心 点”的算法1) 、先得到中心点，判断1234个区域中哪个有格板，假设3区 有，则在中心点周围的124区填充格板2) 、接着顺次以1234子区的中心为新的中心点，重复(1)的算法第五章调试分析输入：（lr=O,dc=l ,size=2输出：1011输入：＜ir=2,dc=3size=4• o输出：223 3211 3415 0445 5输入：＜44,dc=5size=81 o输出：3344889932248779526610107115561110111113131411801919131214141818171915121216201717211515161620202121遇到的问题：三格板的分类问题解决方法：用二维数组对所有方格进行编号，同三格板的编号相同第六章测试结果输入：（lr=O,dc=l ,size=2输出：1011输入：＜ir=2,dc=3size=4• o输出：223 3211 3415 0445 5输入：＜44,dc=5size=81 o输出：3344889932248779526610107115561110111113131411801919131214141818171915121216201717211515161620202121由这几组数据的运行结果可知，此程序运行完全正确，满足问题 需求。

第七章课题设计总结由于本程序要求所有三格板不能重叠，且必须覆盖其余方格所 以，一开始的算法构思出现一定的问题，后期考虑到问题的细化解决， 即可以采用递归方法进行解决，最终使问题得以成功克服总的来说， 此程序的理解难度并不高，整个程序的算法思想也比较简单，主要还 是初始时的算法思想需要一定时间思考通过此次课程设计，使我更加扎实的掌握了递归方面的知识，在 设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又 一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识 欠缺和经验不足在课程设计过程中，不断发现错误，不断改正，不断领悟，不断 获取最终的检测调试环节，本身就是在践行“过而能改，善莫大焉” 的知行观这次课程设计终于顺利完成了，在设计中遇到了很多问题, 最后在一些资料和书本的帮助下，终于游逆而解参考文献：[1] 谭浩强著.C++程序设计（第二版）[M].北京：清华大学出版社，2009. 5[2] 严蔚敏、吴伟民主编《数据结构（C语言版）》[M].清华大学出版社2004. 11附录（程序清单）:#include #include using namespace std;int board[100][100]; 〃存放棋盘L型的标号数组；int tile=l; 〃L型骨牌号void chessBoard(int tr, int tc, int dr, int de, int size)//tr 棋盘中左上角方格所在行。

tc 棋盘中左 上角方格所在列{if (size==l)return;intt = tile++; 〃L 型骨牌号int s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr= tc + s) //特殊方格在此棋盘中chessBoard(tr, tc+s, dr, de, s);else //此棋盘中无特殊方格board[tr + s - l][tc + s] = t; 〃用t号L型骨牌覆盖左下角chessBoard(tr, tc+s, tr+s-1, tc+s, s);// 覆盖其余方格// 覆盖左下角子棋盘if (dr >= tr + s && de < tc + s) //特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, de, s);else //此棋盘中无特殊方格{board[tr + s][。