棋盘覆盖问题算法设计与分析论文.docVIP

棋盘问题的算法分析与设计 摘要： 介绍了棋盘覆盖问题的背景知识，选题依据和程序设计目标，详细分析了程序 的设计和实现，并说明了程序的使用方式，演示了程序的运行过程，最后对开发过程中的问题进行了总结。 关键字：棋盘覆盖， 棋盘覆盖问题是分治算法的一个经典问题， 分治算法的基本思想是将一个规模较大的问题分解为若干个规模较小的子问题， 这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。 引言 问题的提出 在一个2^k×2^k （k≥0）个方格组成的棋盘中，若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有 种情形.因而对任何k≥0,有4^k种不同的特殊棋盘. 棋盘算法设计思想 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。此即为分治策略 相关程序 #includeiostream #includeiomanip usingnamespacestd; voidChessBoard(int,int,int,int,int); int **board;//棋盘 int tile = 1;//L型骨牌编号 void main() { int size = 0; int row, column; coutInput the size n of the chessboard(n*n): endl; cin size; coutInput the position of the special check: endl; cin row column; 实验分析 实验环境：操作系统WINDOWS XP, 开发工具：VC++ 6.0 2、编程任务： 在棋盘覆盖问题中,要用图2-5所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.易知,在任何一个2k×2k的棋盘覆盖中,用到的L型骨牌个数恰为(4k-1)/3. #include stdio.h #define BOARD_SIZE 4 int board[BOARD_SIZE][BOARD_SIZE]; // c1, r1: 棋盘左上角的行号和列号 // c2, r2: 特殊方格的行号和列号 // size = 2 ^ k void chessboard(int r1, int c1, int r2, int c2, int size) { if(1 == size) return; int half_size; static int domino_num = 1; int d = domino_num++; half_size = size / 2; if(r2 r1 + half_size c2 c1 + half_size) //特殊方格在左上角子棋盘 { chessboard(r1, c1, r2, c2, half_size); } else // 不在此棋盘，将此棋盘右下角设为相应的骨牌号 { board[r1 + half_size - 1][c1 + half_size - 1] = d; chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size); } if(r2 r1 + half_size c2 = c1 + half_size) //特殊方格在右上角子棋盘 { chessboard(r1, c1 + half_size, r2, c2, half_size); } else // 不在此棋盘，将此棋盘左下角设为相应的骨牌号 { board[r1 + half_size - 1][c1 + half_size] = d; chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size); } if(r2 = r1 + half_size c2 c1 +