残缺棋盘

韩冰

<b>残缺棋盘</b>
<>残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。

* O9 X  r. U" ^, X. U残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残缺棋盘（如图1 4 - 4所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三格板总数为( 22k -1 ) / 3。可以验证( 22k -1 ) / 3是一个整数。k 为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k= 1时，正好存在3个非残缺的方格，并且这三个方格可用图1 4 - 4中的某一方向的三格板来覆盖。

用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k×2k 残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k×2k 棋盘一个很自然的划分方法就是将它划分为如图1 4 - 5 a所示的4个2k - 1×2k - 1 棋盘。注意到当完成这种划分后， 4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k×2k 棋盘仅仅有一个残缺方格）。首先覆盖其中包含残缺方格的2k - 1×2k - 1 残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图14-5b 所示，其中原2k×2k 棋盘中的残缺方格落入左上角的2k - 1×2k - 1 棋盘。可以采用这种分割技术递归地覆盖2k×2k 残缺棋盘。当棋盘的大小减为1×1时，递归过程终止。此时1×1的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。
) x1 i/ B! \) ~
2 R2 _" x8 w4 {8 B$ m, M可以将上述分而治之算法编写成一个递归的C++ 函数Ti l e B o a r d (见程序1 4 - 2 )。该函数定义了一个全局的二维整数数组变量B o a r d来表示棋盘。B o a r d [ 0 ] [ 0 ]表示棋盘中左上角的方格。该函数还定义了一个全局整数变量t i l e，其初始值为0。函数的输入参数如下：

? tr 棋盘中左上角方格所在行。

? tc 棋盘中左上角方格所在列。
& [3 E; Q1 c, l' m# Z( W8 P/ F- y
- w* ?* e; Y/ m3 k% {0 D? dr 残缺方块所在行。

? dl 残缺方块所在列。
$ O* T1 i$ C, j6 h
? size 棋盘的行数或列数。
/ q' l8 P1 R5 x( m. b' d
Ti l e B o a r d函数的调用格式为Ti l e B o a r d（0,0, dr, dc,size)，其中s i z e = 2k。覆盖残缺棋盘所需要的三格板数目为( s i z e2 -1 ) / 3。函数TileBoard 用整数1到( s i z e2-1 ) / 3来表示这些三格板，并用三格板的标号来标记被该三格板覆盖的非残缺方格。

令t (k) 为函数Ti l e B o a r d覆盖一个2k×2k 残缺棋盘所需要的时间。当k= 0时，s i z e等于1，覆盖它将花费常数时间d。当k &gt; 0时，将进行4次递归的函数调用，这些调用需花费的时间为4t (k-1 )。除了这些时间外， if 条件测试和覆盖3个非残缺方格也需要时间，假设用常数c 表示这些额外时间。可以得到以下递归表达式：
) [' F7 X" Z; x- L4 B( z
! j: ?  D' o9 S6 n/ W. v6 k. K* s程序14-2 覆盖残缺棋盘
/ e% c) A9 N; }9 N; s
void TileBoard(int tr, int tc, int dr, int dc, int size)

{// 覆盖残缺棋盘
& ]! |, g* k: Q+ p
if (size == 1) return;
; P2 x. K7 v- M
int t = tile++, // 所使用的三格板的数目

, A- z5 a. T  |' v8 g: C+ Rs = size/2; // 象限大小
$ [+ f! X) T, f" j6 u
/ /覆盖左上象限
9 F8 O0 j8 G5 b3 e
if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)

// 残缺方格位于本象限
2 l; J/ ^9 \, l4 R
# Y- w# b& o' q5 X1 w2 }) \; `Ti l e B o a r d ( t r, tc, dr, dc, s);
7 L3 `8 G0 t& p# g6 a& ]
else {// 本象限中没有残缺方格
; x' I, G, Z: d
// 把三格板t 放在右下角
- h& u$ D2 g$ @8 y6 b
# x+ H6 D& H% ^! q" BBoard[tr + s - 1][tc + s - 1] = t;
, X0 o& [# p9 _0 B  S
// 覆盖其余部分

6 u! C+ {$ Y0 q7 l" gTi l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}

/ /覆盖右上象限

0 r4 `- ~6 ^: F$ m5 A1 iif (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)
! U. t* ^3 y3 _6 W& y
: |0 K) G, Z4 h. d7 z// 残缺方格位于本象限

. t: J# p  m( v% R4 F' C2 `Ti l e B o a r d ( t r, tc+s, dr, dc, s);
' D) `  i" h8 v" g1 p# Z
else {// 本象限中没有残缺方格

$ K. i( Y+ t, Y// 把三格板t 放在左下角

5 K; d) v2 c4 \  y" }6 d/ nBoard[tr + s - 1][tc + s] = t;
+ \# p, F7 O+ W; N4 a
// 覆盖其余部分

' I: q. Y" Z4 U$ O5 q2 ]Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}

/ /覆盖左下象限

if (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)
  U5 Q: e# L# X% ~
// 残缺方格位于本象限
$ Q0 G6 e" g7 }
8 b7 {: q; B$ O) F( W/ n0 |* {& eTileBoard(tr+s, tc, dr, dc, s);
% C# a% ?" e; f
else {// 把三格板t 放在右上角
$ T* k! S1 i/ r" d9 Y
Board[tr + s][tc + s - 1] = t;

// 覆盖其余部分
) N0 u  Q7 O9 H# E! g6 Z# X
+ ?# x- v9 S% U1 t$ xTileBoard(tr+s, tc, tr+s, tc+s-1, s);}
2 u, N2 v  R8 ~6 ^/ A. g
// 覆盖右下象限

if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)
1 ]$ x7 d! K6 x
// 残缺方格位于本象限
( g0 |( F1 E, K% _) P$ f+ W* K! x
TileBoard(tr+s, tc+s, dr, dc, s);

8 W  x) k* o1 Y% l3 Oelse {// 把三格板t 放在左上角
. q2 f# M. ?5 Z3 j1 R
' t: x. m3 Z8 `Board[tr + s][tc + s] = t;

3 h0 Q* P+ J) ?, z6 b// 覆盖其余部分

TileBoard(tr+s, tc+s, tr+s, tc+s, s);}

, j/ O' {5 k, m# h" n}

void OutputBoard(int size)
1 u3 k! q* a* a6 a% [3 [. R. p
{

5 `" s& W2 i1 g5 [1 ]- Jfor (int i = 0; i &lt; size; i++) {

for (int j = 0; j &lt; size; j++)

. L7 u7 k/ \% j# ^) T: rcout &lt;&lt; setw (5) &lt;&lt; Board[j];

& X$ X0 q  T& T4 Zcout &lt;&lt; endl;

}
. d' F4 b7 u5 x# v
1 E: S4 S7 E- O' \6 r$ g4 p+ R* s: U}
! @3 F5 k( Y2 ~% d
可以用迭代的方法来计算这个表达式（见例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必须花费至少( 1 )的时间来放置每一块三格表，因此不可能得到一个比分而治之算法更快的算法。</P>

yammay

<>太感谢啦。找了好久才找到这个程序。真是真是太感谢啦。有点激动</P>

wendy28

我们学过了,很经典的一道题！

cupidvenus

没看明白，图呢？