<b>残缺棋盘</b>- @* ]% N1 O/ J, i$ A/ }
<>残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注意当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - 3 a所示)。事实上,对于任意k,恰好存在22k 种不同的残缺棋盘。7 _4 f6 B) ^" j9 j# m& z
6 s" ~7 f2 u2 f7 c
残缺棋盘的问题要求用三格板(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中的某一方向的三格板来覆盖。 ; c. D* y* Z$ _8 g u- Z! D( u1 `/ Y
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺,所以无需放置三格板。: _% x5 `! I, G) q, b
0 p+ D9 O% K7 q! K* o
可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下:4 D- O; @5 _5 y$ ~( N& q$ a- ?
' X; O- e" r- D+ ~: @? size 棋盘的行数或列数。; s' P6 D3 ~4 U5 t
. j) [$ a; w& h+ {8 l: @
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来表示这些三格板,并用三格板的标号来标记被该三格板覆盖的非残缺方格。+ z3 e$ @, D9 F7 j9 J; N
$ j$ t. G; N: B0 B7 P
令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 表示这些额外时间。可以得到以下递归表达式:7 {/ e$ p- ~0 ~) ~+ B6 K5 S& l
9 @9 A' X+ X1 c( h程序14-2 覆盖残缺棋盘 & U/ l( x$ c( Q9 J, N. I$ h : a* Z. n+ B. q8 v5 H) V, Yvoid TileBoard(int tr, int tc, int dr, int dc, int size)7 B" A+ ^7 \3 T4 |9 }, G
0 N" j, p4 l& w* ~8 g8 [
{// 覆盖残缺棋盘 7 U# C C: N! @( V8 b! y p - u6 W4 ^( _" yif (size == 1) return;& L% @; M5 C8 j% Y1 s
5 o& ]' ]8 g3 u$ N% H. p) z
int t = tile++, // 所使用的三格板的数目" ^8 W& M3 y' A6 s- c8 @* r/ @& }
9 t0 y, z) U8 u; E
s = size/2; // 象限大小 1 I' K0 `9 Q7 T5 M1 }* E5 s4 x0 b( K/ x$ Z5 b- h3 O) C2 i% h
/ /覆盖左上象限" i& \; S4 u$ w, T
2 M2 _# h: F0 \* `6 @/ P g* rif (dr < tr + s && dc < tc + s) {9 W, b0 W1 Q 1 o8 \; N4 ~# i9 @// 残缺方格位于本象限) W7 i/ w2 t3 P3 d
5 Z2 r+ r8 w: Z. i C* ]Ti l e B o a r d ( t r, tc, dr, dc, s); 8 _/ o+ \' D4 E, w6 r8 o' q& Y. L, I/ w) ^& J" s( q% d% _3 e
else {// 本象限中没有残缺方格, `! F# V2 E- u4 S
: ^3 c0 T6 _- G// 把三格板t 放在右下角. }9 u' i7 {& s6 j# {. w& @
* @* R* ]- }3 I
Board[tr + s - 1][tc + s - 1] = t; / a+ P% a& C+ m8 Y8 O $ [0 i! t/ U, m7 Z: r, }0 I9 n// 覆盖其余部分 8 u# J' z6 H. Q% `1 ~' H& Y) F; e1 m 8 x2 ]& |" N5 f- D9 \Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);} 6 r$ O" T0 `% a1 l ( y9 T! t) w. s$ }) ^/ /覆盖右上象限1 `7 h/ l- d& ]0 S' @" H) {4 @
3 Q% U- L5 R& y' I% `
if (dr < tr + s && dc >= tc + s) + d6 w2 |8 y& u/ E, l ) o3 R0 M4 R$ T' V$ ^, K1 }$ G// 残缺方格位于本象限, t7 U4 v: H; \) E) K$ d. Z, q
; l% Y" c( m" \5 y
Ti l e B o a r d ( t r, tc+s, dr, dc, s); 3 G0 U8 O4 e3 i0 q1 \4 F- ^! ?9 t 5 H) d% f+ j- c- _2 P. B5 felse {// 本象限中没有残缺方格0 ^3 r7 c, U7 C" c5 A9 A
! E# [+ A) O2 A s; [// 把三格板t 放在左下角/ m5 d# X/ U" e( q, A0 i
5 \2 l1 M# v9 P5 R) z& P9 U
Board[tr + s - 1][tc + s] = t;; v$ ~' R7 p1 Z' e
! c% Y5 A: H. ]0 m! Q
// 覆盖其余部分! @4 O& x7 y5 D% C, ?% A+ E
6 ^+ Y- K) v* O$ q" u# }/ dTi l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);} 1 C3 J. R8 y# e: a7 o % V; r% t8 \+ J5 w/ /覆盖左下象限 . b5 C8 w& V* T% X & ^) c$ R$ K. N( s( @6 Y% |4 N& P0 oif (dr >= tr + s && dc < tc + s)9 A n) `3 V8 _1 N