C++课题设计报告(残缺棋阵)

********大学暑假课题设计说明书题目：残缺棋阵覆盖问题学生姓名：学号：专业：班级：指导教师：2013 年7 月31日残缺棋阵覆盖问题摘要摘要：残缺棋阵问题要求用三格板（triominoes）覆盖残缺棋盘。

在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。

用分而治之方法解决此问题，即为了解决一个大的问题，可以：1)把它分成两个或多个更小的问题；2)分别解决每个小问题；3)把各小问题的解答组合起来，即可得到原问题的解答。

小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

选用递归算法，先构造一个函数，专门用与递归实现棋盘补充问题。

第一步，取棋盘中点，先判断残缺点的X，Y在哪一个区域，同时可覆盖三个小方格，即四个区域分别设定每一个区域的左上角，右下角和缺点。

将它们分别存入一个数组中。

棋盘划分一次，棋子增加3个，棋盘减少一个，同时又新增加4个棋盘。

递归函数调用，直至所有的子棋盘都被覆盖。

关键词：残缺点，三格板，分而治之，递归。

数据结构课程设计任务书针对本课程设计，完成以下课程设计任务：1、熟悉系统实现工具和上级环境。

2、根据课程设计任务，查阅相关资料。

3、针对所选课题完成以下工作：（1）、需求分析（2）、概要设计（3）、详细设计（4）、编写源程序（5）、静态走查程序和上机调试程序4、书写上述文档和撰写课程设计报告。

目录残缺棋阵覆盖问题 (I)摘要 (II)课程设计任务书 (III)课程设计正文 (Ⅳ)第一章问题描述 (5)第二章需求分析 (6)第三章概要设计 (9)第四章详细设计 (19)第五章调试分析 (21)第六章测试结果 (23)第七章课题设计总结 (24)参考文献 (24)附录（程序清单） (33)第一章问题描述问题描述：残缺棋盘是一个有2^k×2^k（k≥1）个方格的棋盘，其中恰有一个方格残缺。

如图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

问题要求：残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。

在此覆盖中要求：1）两个三格板不能重叠。

2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。

在这种限制条件下，所需要的三格板总数为(2^k×2^k -1)/3。

可以验证(2^k×2^k -1)/3是一个整数。

k为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。

当k=1时，正好存在3个非残缺的方格，并且这三个方格可用任意一方的三格板来覆盖。

第二章需求分析从问题描述可以发现：当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。

第三章概要设计本程序有四个模块，调用关系如下：本程序的流程图：第四章详细设计主要函数：（1）、void chessBoard(int tr, int tc, int dr, int dc, int size)//tr 棋盘中左上角方格所在行，tc 棋盘中左上角方格所在列，dr 特殊点的行下标，dc 特殊点的列下标size 棋阵的行数。

（2）、int main( )；算法分析：void chessBoard(int tr, int tc, int dr, int dc, int size){if (size==1)return;int t = tile++; // L型骨牌号int s = size/2; // 分割棋盘//________________________________________________ 覆盖左上角子棋盘if (dr<tr+s&&dc<tc+s) // 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else // 此棋盘中无特殊方格{board[tr+s-1][tc+s-1]=t; // 用t 号L型骨牌覆盖右下角chessBoard(tr,tc,tr+s-1, tc+s-1, s);// 覆盖其余方格}//________________________________________________ 覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else // 此棋盘中无特殊方格{board[tr + s - 1][tc + s] = t; //用t号L型骨牌覆盖左下角chessBoard(tr, tc+s, tr+s-1, tc+s, s);// 覆盖其余方格}//_______________________________________________ 覆盖左下角子棋盘if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中chessBoard(tr+s, tc, dr, dc, s);else // 此棋盘中无特殊方格{board[tr + s][tc + s - 1] = t; // 用t 号L型骨牌覆盖右上角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; // 用t 号L型骨牌覆盖左上角chessBoard(tr+s, tc+s, tr+s, tc+s, s); // 覆盖其余方格}}本问题的算法核心是找到棋阵的“中心点”，然后判断在4个矩形区域里的格子状态，来决定用哪种3格板来填充。

递归寻找“中心点”的算法。

(1)、先得到中心点，判断1234个区域中哪个有格板，假设3区有，则在中心点周围的124区填充格板。

(2)、接着顺次以1234子区的中心为新的中心点，重复（1）的算法。

第五章调试分析输入：dr=0，dc=1 ，size=2。

输出：1 01 1输入：dr=2，dc=3 ，size=4。

输出：2 2 3 32 1 1 34 15 04 45 5输入：dr=4，dc=5 ，size=8。

输出：3 3 4 4 8 8 9 93 2 24 8 7 7 95 26 6 10 107 115 56 1 1 10 11 1113 13 14 1 18 0 19 1913 12 14 14 18 18 17 1915 12 12 16 20 17 17 2115 15 16 16 20 20 21 21遇到的问题：三格板的分类问题。

解决方法：用二维数组对所有方格进行编号，同三格板的编号相同。

第六章测试结果输入：dr=0，dc=1 ，size=2。

输出：1 01 1输入：dr=2，dc=3 ，size=4。

输出：2 2 3 32 1 1 34 15 04 45 5输入：dr=4，dc=5 ，size=8。

输出：3 3 4 4 8 8 9 93 2 24 8 7 7 95 26 6 10 107 115 56 1 1 10 11 1113 13 14 1 18 0 19 1913 12 14 14 18 18 17 1915 12 12 16 20 17 17 2115 15 16 16 20 20 21 21由这几组数据的运行结果可知，此程序运行完全正确，满足问题需求。

第七章课题设计总结由于本程序要求所有三格板不能重叠，且必须覆盖其余方格。

所以，一开始的算法构思出现一定的问题，后期考虑到问题的细化解决，即可以采用递归方法进行解决，最终使问题得以成功克服。

总的来说，此程序的理解难度并不高，整个程序的算法思想也比较简单，主要还是初始时的算法思想需要一定时间思考。

通过此次课程设计，使我更加扎实的掌握了递归方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。

在课程设计过程中，不断发现错误，不断改正，不断领悟，不断获取。

最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。

这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在一些资料和书本的帮助下，终于游逆而解。

参考文献：[1]谭浩强著.C++程序设计（第二版）[M].北京：清华大学出版社，2009.5[2]严蔚敏、吴伟民主编《数据结构（C语言版）》[M]. 清华大学出版社 2004.11附录（程序清单）：#include <iostream>#include <iomanip>using namespace std;int board[100][100]; //存放棋盘L型的标号数组；int tile=1; // L型骨牌号void chessBoard(int tr, int tc, int dr, int dc, int size)//tr 棋盘中左上角方格所在行。

tc 棋盘中左上角方格所在列。

{if (size==1)return;int t = tile++; // L型骨牌号int s = size/2; // 分割棋盘//________________________________________________ 覆盖左上角子棋盘if (dr<tr+s&&dc<tc+s) // 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else // 此棋盘中无特殊方格{board[tr+s-1][tc+s-1]=t; // 用t 号L型骨牌覆盖右下角chessBoard(tr,tc,tr+s-1, tc+s-1, s);// 覆盖其余方格}//________________________________________________ 覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else // 此棋盘中无特殊方格{board[tr + s - 1][tc + s] = t; //用t号L型骨牌覆盖左下角chessBoard(tr, tc+s, tr+s-1, tc+s, s);// 覆盖其余方格}//_______________________________________________ 覆盖左下角子棋盘if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中chessBoard(tr+s, tc, dr, dc, s);else // 此棋盘中无特殊方格{board[tr + s][tc + s - 1] = t; // 用t 号L型骨牌覆盖右上角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; // 用t 号L型骨牌覆盖左上角chessBoard(tr+s, tc+s, tr+s, tc+s, s); // 覆盖其余方格}}int main(){int size,dr,dc;cout<<"\t\t\t"<<"棋盘覆盖问题\n";cout<<"输入形式为2^k×2^k的棋阵的边长size(size=2,4,8,16,32,64...)：";cin>>size;cout<<"输入特殊点的行下标,列下标(0-"<<(size-1)<<"):";cin>>dr>>dc;board[dr][dc]=0;cout<<"棋盘覆盖图(0为特殊点)：\n";chessBoard(0, 0, dr, dc, size);int i,j;for( i=0;i<size;i++){for( j=0;j<size;j++)cout<<setw(6)<<board[i][j];//setw(6),输出量不足6个字符时在左面填充空白cout<<endl<<endl;}return 0;}。