<b>残缺棋盘</b> 5 O2 z- b4 t0 q6 r$ |: K) y8 j<>残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注意当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - 3 a所示)。事实上,对于任意k,恰好存在22k 种不同的残缺棋盘。 7 x5 c! l( g, i4 b7 S3 s; k! p, `8 P* g5 [* j. S
残缺棋盘的问题要求用三格板(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中的某一方向的三格板来覆盖。 0 \) q, U5 f, K ! V9 b d; ^ Z' t用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺,所以无需放置三格板。. z+ E1 R' R4 O9 e; ~8 i3 v
* r) I# ^, j& p7 N0 F* @; B' Q可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下: 0 M1 r: Q0 n4 Z + j) A: h5 C0 ^( x' @? tr 棋盘中左上角方格所在行。. p2 z, L! T& N1 E% O
, K: `( S: T9 x5 A+ y, j
? tc 棋盘中左上角方格所在列。 " I1 X4 N4 v# N, i3 l, Y8 d4 s: Y$ r/ ]! a7 O. i/ x7 j. Q0 }5 j
? dr 残缺方块所在行。 + h. N+ C6 m9 r# H7 d- m5 T7 h/ f) `$ R) l. a" B
? dl 残缺方块所在列。/ G: A% e# p; U3 b/ z; [& v
% q9 a$ ~" ~* ~, J3 y6 z
? size 棋盘的行数或列数。 4 A: q( D" A9 F4 ^% Y5 ^4 i+ X* O R! }0 n+ Q( l5 Q3 e2 M
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来表示这些三格板,并用三格板的标号来标记被该三格板覆盖的非残缺方格。 , V3 f& o7 n! l$ Y. E. i& H * L6 ]2 l7 Q1 s0 b9 y" B, E$ P- b令t (k) 为函数Ti l e B o a r d覆盖一个2k×2k 残缺棋盘所需要的时间。当k= 0时,s i z e等于1,覆盖它将花费常数时间d。当k > 0时,将进行4次递归的函数调用,这些调用需花费的时间为4t (k-1 )。除了这些时间外, if 条件测试和覆盖3个非残缺方格也需要时间,假设用常数c 表示这些额外时间。可以得到以下递归表达式:( ^! B# T5 E( a
3 n$ j7 Y; j$ q& t; N
程序14-2 覆盖残缺棋盘8 d9 y/ ]9 ?9 ?. I6 \
0 U" v8 b0 C8 q k" @
void TileBoard(int tr, int tc, int dr, int dc, int size) 2 U7 }" p0 T3 o8 [ f8 O$ o: w+ M' C& z$ D; f( G
{// 覆盖残缺棋盘 {2 ]* ~- X O5 z/ y
3 J% o: [# z4 [: s2 r. [
if (size == 1) return; : `% q3 s3 o' ]- d/ A7 B7 S1 r6 U" d7 h j8 b
int t = tile++, // 所使用的三格板的数目 5 l; t. a2 p& B' f; Z % Q: ~' v6 u4 Y ?s = size/2; // 象限大小% x# L! B5 o0 F2 `; U