数学建模社区-数学中国

标题: 残缺棋盘 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:16
标题: 残缺棋盘
<b>残缺棋盘</b>7 K2 l2 K) c; i4 T- P
<>残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。, z& ?4 r( s* X; L9 a

$ {( Z2 L% p, m6 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中的某一方向的三格板来覆盖。
% Z4 M0 M5 \  n4 q. Z8 A! E
! y& E/ W8 d& Q7 s! G+ K用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。1 x% T+ `8 J* {1 w+ \. c
3 V, O' k/ g1 U# X$ F0 I. p
可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下：
) n% b3 H& h: @3 Z7 v
% B0 P7 I* J! v? tr 棋盘中左上角方格所在行。
* c1 W5 e# C4 i7 V8 f9 v0 U, N; I; i: i( y
? tc 棋盘中左上角方格所在列。
4 i9 e( y0 T4 V) t+ Z: ~7 N. I& u' Y6 d2 H$ }
? dr 残缺方块所在行。/ J/ g5 _2 O2 S* Z6 o  \6 b( v
; H7 ~8 W( j* T0 U3 h
? dl 残缺方块所在列。
/ d9 `0 n  w5 x" H+ w
0 G) s1 u2 ~' f? size 棋盘的行数或列数。: w; n8 F$ t, }& d
0 q0 t+ [4 I9 C. q: K* A( a! n% Y
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来表示这些三格板，并用三格板的标号来标记被该三格板覆盖的非残缺方格。7 ]  S$ a* n: N' q+ x
) U* i2 _2 P: Y
令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 表示这些额外时间。可以得到以下递归表达式：
( s1 p8 o  K  p# x2 n0 w% o6 r. ?6 V6 n( [( d" q
程序14-2 覆盖残缺棋盘
$ Z( {4 i/ N( m- \# _! m5 G
" K1 G) |5 W( mvoid TileBoard(int tr, int tc, int dr, int dc, int size)
% o& d9 Y' W8 [" N' p" T& e
5 {5 b0 y& q" B; S7 M{// 覆盖残缺棋盘; \8 D+ C% F; I" M, q, f
! O* S9 X* T3 E& b$ y
if (size == 1) return;
" b# `' x9 H1 C6 A3 b
* e7 k+ |' U. r: {! Q$ n* o0 xint t = tile++, // 所使用的三格板的数目
! y( m$ c% r; @4 z0 w$ G: ^% I2 G+ p) e6 c. F7 Q
s = size/2; // 象限大小1 f' g9 m& T; @' m5 ]" v
+ P. j+ Q# y) y: [- X
/ /覆盖左上象限% n& T+ R; X: p! n# G
8 P! D9 s0 Z7 ?+ e
if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)$ S3 j1 _9 ?- J0 y4 {" s
& L" G5 b, M2 s' E1 O
// 残缺方格位于本象限$ B, ?0 H2 d( l+ Y+ p( ^: Q5 D
6 e2 T# ~. k2 ?, D( q6 O9 a
Ti l e B o a r d ( t r, tc, dr, dc, s);
, J8 x/ s  j! S+ q2 n. v1 e8 g( ~( O3 o! b! b9 b
else {// 本象限中没有残缺方格% x8 _0 y8 b% X; f

1 v% K3 V( [6 `6 u2 C: t// 把三格板t 放在右下角
8 u. \* K& J0 g; s9 X% ^. t- }9 C) F) s/ c2 R2 q' Z
Board[tr + s - 1][tc + s - 1] = t;
; r- O8 e! T3 g$ q7 B0 S0 {% g; W
// 覆盖其余部分: e! _/ P  x' f7 ^$ T' K) K
4 W1 X7 R" S2 S3 c$ z
Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}! U# X2 z. i: ^: l3 M

" U  X) _7 j, b  Q; o( ~/ /覆盖右上象限
: Q* g8 b" z: w0 t, d) v: _1 Z3 a
8 T) q1 ~0 g0 N& n7 x- ]if (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)' |- L2 _0 r/ a+ X

& w7 R( }- f. V# K$ S// 残缺方格位于本象限5 c% e8 o# ]% ?
( u0 g6 @- Z6 P' m( g( T' T; b
Ti l e B o a r d ( t r, tc+s, dr, dc, s);" m# ?+ P' u9 F
& t  c9 C: \* @: X: H* e
else {// 本象限中没有残缺方格
# b5 J1 E; ]- g) c4 t. p. k4 p& O
* j& M4 Z% \5 f% x// 把三格板t 放在左下角
+ \6 C7 A& ]5 o) b( s' ?) N: `" S$ f# T- W/ @
Board[tr + s - 1][tc + s] = t;
, r- K, p2 E: \$ I8 i* N( f" L: v1 p, ^( j7 t7 F
// 覆盖其余部分+ r! l/ B+ k- e) X2 x; ]  ^$ I2 O; E6 v

% z6 |) O0 ?3 G% ZTi l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}
' y9 g' n" X7 R! M; H/ o/ H8 W! N3 U& T
/ /覆盖左下象限- R' \. x3 q: ]9 I5 c
: B9 ^$ d0 `8 S( P# o
if (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)0 `+ g$ ~7 E% O9 T

( g- j! e  C7 B5 `// 残缺方格位于本象限
8 T# }) y7 P7 Q9 e( q+ C5 k. T6 a0 ]! q
TileBoard(tr+s, tc, dr, dc, s);
, P, |* y; `1 v8 G3 a" e6 x
7 Z( J" d! i9 c5 V: relse {// 把三格板t 放在右上角2 @5 }2 g5 W- N! K/ R! u! }

7 u8 q* Q0 @4 E  C. LBoard[tr + s][tc + s - 1] = t;" B# _/ v& g0 q" t7 |( k

# t0 F" v: U$ v5 g: c// 覆盖其余部分2 U0 ?6 F+ q, x: ~) r  _6 P; C4 e
/ _$ w9 J3 v5 T5 r# N& _
TileBoard(tr+s, tc, tr+s, tc+s-1, s);}1 t( o  U% {3 Q- B% h) ^5 H0 K
  z( X: i" d# E
// 覆盖右下象限
5 _; u2 H3 z" S: L$ u" M4 i1 g! H% w& S0 i; S$ q% c
if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)% T8 G4 @" O( @0 ?8 c. S8 j
: ?# f6 u, j% F. E, m
// 残缺方格位于本象限
( i( O* i0 [) k9 ^! y: T8 @# V! h" O; R& y  c* U$ r$ J4 e
TileBoard(tr+s, tc+s, dr, dc, s);2 T8 Y' P- |. b2 ^$ ^& Q
: j1 E4 C% L9 T8 G
else {// 把三格板t 放在左上角
; U# ]; \' n2 e; h& i$ u, s, S) h. z2 E9 z4 \& b9 K
Board[tr + s][tc + s] = t;' ]/ n6 u# g9 l5 T/ I4 G
4 L/ K8 e. n5 W+ \5 v; V" ^3 c  q
// 覆盖其余部分
8 [. {- G$ E$ H" D# L, N- d1 S" x' C' g0 W" Q" t
TileBoard(tr+s, tc+s, tr+s, tc+s, s);}
+ `$ T4 v8 w4 a5 q- C
) V" g" L8 m3 P9 q" b( B' i}) V- A" n% e; i. L) v/ f1 w

' v* W1 X" e* n2 tvoid OutputBoard(int size). ]" m% p6 s+ ~) N0 }0 Z
  ]0 B1 Y. _0 D  ]; Q6 b
{
; j6 ^, T, J+ X9 t. {1 _! ^
6 K( x  r4 K3 V% [4 L9 qfor (int i = 0; i &lt; size; i++) {% w7 r2 C# ^' E
1 z; e4 T0 k1 b. X
for (int j = 0; j &lt; size; j++)) T1 w: V2 P' k* E- V

# v: u4 E9 s0 r7 o" Hcout &lt;&lt; setw (5) &lt;&lt; Board[j];
! `  T9 O" V# s0 Z: M5 s
) J: `: l) Q$ W0 ~$ Jcout &lt;&lt; endl;* q; e, l6 r8 V% h& E. Y* S

1 M2 c& o5 d8 x" ^& s  W; `}9 {; K3 ~/ F: b+ I3 c
7 T0 X6 W( \3 G7 b# i
}0 T/ S' g, g1 Q" f5 H& _8 i, I

9 t- V0 D! S, \可以用迭代的方法来计算这个表达式（见例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必须花费至少( 1 )的时间来放置每一块三格表，因此不可能得到一个比分而治之算法更快的算法。</P>
作者: yammay    时间: 2005-4-3 17:22
<>太感谢啦。找了好久才找到这个程序。真是真是太感谢啦。有点激动</P>
作者: cupidvenus    时间: 2005-9-27 13:13
没看明白，图呢？
作者: wendy28    时间: 2005-9-29 00:46
我们学过了,很经典的一道题！



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5