信息工程学院计算机科与技术专业.doc

信息工程学院计算机科学与技术专业 软件课程设计论文 棋盘覆盖 学生姓名：张 忠 学 号指导教师：王湘桃 完成时间：2005-1-21 棋盘覆盖 一、 课程设计目的和意义 学会如何用软件工程的思想和理论将现实世界中的复杂问题通过抽象用计算机解决。使理论和实践有机的结合并选择合理的编程语言,培养编程思想，及独立完成编程工作的能力,学会设计最优的算法。 通过此次应用软件课程设计，培养了我们应用软件工程的基本思想分析问题和解决问题的能力，提高我们的编程水平，掌握了一些编程技巧，了解了学科领域的发展动向，为以后的工作奠定了坚实的理论基础。 二 、要求与任务 在一个2k*2k方格组成的棋盘中，若有一个方格与其他的方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4^k中情形。因而对任何k=0，有4^k中不同的特殊棋盘。在棋盘覆盖问题中，我们要用4种不同形态的L型骨牌覆,盖一个给定的特殊棋盘上除特殊方格以外的所以方格且任何两个L型骨牌不得重复覆盖。 三、算法实现 3.1 算法描述 在棋盘覆盖问题中，我们要用4种不同形态的L型骨牌(如图1-1所示)覆盖一个给定的特殊棋盘上除特殊方格以外的所以方格且任何两个L型骨牌不得重复覆盖。则可知道，在任何一个2^k*2^k的棋盘覆盖中，用到的L型骨牌个数恰好为：(4^k-1)/3。  (a) (b) (c) (d) 图 1-1 用分治策略，我们可以设计出解决棋盘覆盖问题的一个简洁的算法。 当k0时，我们将2^k*2^k棋盘分割为4个2^(k-1)*2^(k-1)子棋盘如图1-2(a)所示。 (b) 图 1-2 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖者个较小棋盘的汇合处，如图1-2(b)所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至期盼简化为1×1棋盘。 实现这种分治策略的算法ChessBoard可实现如下: void ChessBoard(int tr, int tc, int dr, int dc, int size){ // 覆盖棋盘if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 / /覆盖左上if (dr tr + s dc tc + s)// 特殊方格Board ( t r, tc, dr, dc, s);else { // 此棋盘中没有方格// 用t 号L型骨牌覆盖右下角Board[tr + s - 1][tc + s - 1] = t; // 覆盖其余 ChessBoard ( t r, tc, tr+s-1, tc+s-1, s);} //覆盖上if (dr tr + s dc = tc + s)//特殊方格Board ( t r, tc+s, dr, dc, s);else { //此棋盘中没有方格//用t 号L型骨牌覆盖左下角Board[tr + s - 1][tc + s] = t; //覆盖其余 ChessBoard ( t r, tc+s, tr+s-1, tc+s, s);} //覆盖if (dr = tr + s dc tc + s) //特殊方格Board (tr+s, tc, dr, dc, s); else { //用t 号L型骨牌覆盖右上角Board[tr + s][tc + s - 1] = t;//覆盖其余ChessBoard (tr+s, tc, tr+s, tc+s-1, s);} // 覆盖右下象限 if (dr = tr + s dc = tc + s)//方格Board (tr+s, tc+s, dr, dc, s); else { //用t 号L型骨牌覆盖左上角Board[tr + s][tc + s] = t; //覆盖其余部分Board (tr+s, tc+s, tr+s,