残缺棋盘完美覆盖 C++.doc

1 问题描述：残缺棋盘是有一个2kx2k (k1)个方格的棋盘，其中恰有一个方格残缺。以上为四种三格板，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：（1） 两个三个板不能重叠；（2） 三格板不能覆盖残缺方格，但必须覆盖其他所有方格。2 算法设计： 当k0时，将2k2k棋盘分割为4个2k-12k-1 。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这 根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。三代码实现：#include stdafx.h#include#includeusing namespace std;int tile=0;int *(*board) = NULL;/定义指向指针的指针用于动态的创建用于存储骨牌号的数组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)/ 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else / 此棋盘中无特殊方格/ 用 t 号L型骨牌覆盖右下角boardtr + s - 1tc + s - 1 = t;/ 覆盖其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);/ 覆盖右上角子棋盘if (dr = tc + s)/ 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else / 此棋盘中无特殊方格/ 用 t 号L型骨牌覆盖左下角boardtr + s - 1tc + s = t;/ 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);/ 覆盖左下角子棋盘if (dr = tr + s & dc = tr + s & dc = tc + s)/ 特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s);else/ 用 t 号L型骨牌覆盖左上角boardtr + stc + s = t;/ 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);int main()void chessBoard(int tr, int tc, int dr, int dc, int size);/声明函数int tx=0,ty=0,dx,dy,zsize=1,k;/定义棋盘的左上角方格、特殊方格的行号和列号以及棋盘大小coutdxdyk;/*动态的创建二维数组*/for(int i=1;i=k;+i) zsize=zsize*2;board=new int *zsize;for(int i=0;izsize;i+)boardi=new intzsize;/*动态创建数组结束*/boarddxdy=0;/特殊方格用0填充chessBoard(tx,ty,dx,dy,zsize);/输出结果for(int j=0;jzsize;j+)for(int m=0;mzsize;m+)coutsetw(4)boardjm;/用来控制输出间隔coutendl;system(pause);free(board);board = NULL;return 0;四实验截图：5 心得体会： 通过这次实践，我对分治法的理解程度又加深了很多。实现过程中碰到很多细小而繁杂的问题，这让我意识到课本上的知识终究是课本上的，要变成自己的，必须经过亲身实践。写代码是枯燥的，但是看到自己成果的那一刻又是喜