《原创王大庆-残缺棋盘课件》由会员分享，可在线阅读，更多相关《原创王大庆-残缺棋盘课件（14页珍藏版）》请在金锄头文库上搜索。
1、姓名：王大庆 专业：计算机技术 学号：残缺棋盘问题一个有2k2k个方格的棋盘， 其中恰有一个方格残缺。图1 给出k2时各种可能的残缺棋 盘，其中残缺的方格用阴影表 示。 要求用三格板（triominoes） 覆盖残缺棋盘（如图2所示） 。在此覆盖中，两个三格板不 能重叠，三格板不能覆盖残缺 方格，但必须覆盖其他所有的 方格。什么是残缺棋盘问题？图1图2问题初步分析由简入繁kTableDefectionRemainNum01*110012*213124*4115538*816321k=0k=0k=1k=1k=2?分治原理化大为小当k0时，将2k2k棋盘分割为 4个2k-12k-1 子棋盘(a)所
2、示 。 特殊方格必位于4个较小子棋 盘之一中，其余3个子棋盘中 无特殊方格。为了将这3个无 特殊方格的子棋盘转化为特殊 棋盘，可以用一个L型骨牌覆 盖这3个较小棋盘的会合处， 如 (b)所示，从而将原问题转 化为4个较小规模的棋盘覆盖 问题。递归地使用这种分割， 直至棋盘简化为棋盘11。k=2k=3k=3k=3k=3public 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
3、 = 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 else / 用 t 号L型骨牌覆盖左上角boardtr + stc + s = t;/ 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);运行结果16*16的棋盘，数字 相同的三个地方组 成一块棋盘(注：为 了保持显示的一致 性，棋盘放置的先 后顺序没有表明)。 2k2k的棋盘，其递归方程为 根据递归张开，其复杂度O(4n-1) T(n)=O(4k) 渐进意义下的最优算法效能分析/复杂度分析T H A N K S
