数学建模社区-数学中国

标题: 残缺棋盘 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:16
标题: 残缺棋盘
<b>残缺棋盘</b>
- ~. h$ m/ r9 A+ _<>残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。4 B( n5 d6 I0 j1 I
2 [! B( J. ?0 I( T/ ?$ F
残缺棋盘的问题要求用三格板（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中的某一方向的三格板来覆盖。
9 _, n1 M7 s9 S7 n# s" W6 R4 g) Z0 P, P
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。6 F) {4 R$ n. ~) P6 p" Q
% e0 S7 X; q$ ~% W7 @
可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下：* s% k9 ?( F$ o; s7 e: F8 J9 c
0 ?. L7 k" h0 d9 w2 I2 b. R) B: d1 S# G8 u
? tr 棋盘中左上角方格所在行。7 k* t+ P& f( N7 L) s

& i1 C! O) B* K7 p  V  d? tc 棋盘中左上角方格所在列。
. b4 A) Z& |! A3 C5 E
& b0 |9 c# t5 z2 f? dr 残缺方块所在行。( u, @6 f& _7 y- ?! c% X+ n1 p
4 t) V( n. o/ c6 s. n. X$ X& E8 }
? dl 残缺方块所在列。" R3 ^) U4 k' K# G

, G  w* N! I8 Y4 p" S? size 棋盘的行数或列数。
4 O5 Z* C( t1 T; J
6 F/ H, ?4 s0 Z' nTi 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来表示这些三格板，并用三格板的标号来标记被该三格板覆盖的非残缺方格。3 X) V" w+ k3 {
$ J4 Z( j4 s) G! a0 ^; U- g2 V
令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 表示这些额外时间。可以得到以下递归表达式：
1 z! C. b) I9 h8 [' U
1 l6 O+ O# Q0 e1 q& S程序14-2 覆盖残缺棋盘' ^, T0 V' \5 x5 S2 \! x; A9 @
4 h4 q# Y! `% v- S# q
void TileBoard(int tr, int tc, int dr, int dc, int size)7 L% r" J$ v/ A. i

2 A8 {$ q" K$ y8 `{// 覆盖残缺棋盘
$ Q" b. Q8 A0 R( J  F& O9 ]% ?9 Y3 J* E( k
if (size == 1) return;) V* M/ a# n& _, x; o9 Z

  w! i* D& X# F9 o; Uint t = tile++, // 所使用的三格板的数目
/ G3 _/ I5 k" D( Z% [; G+ B
4 |( e, J0 s1 k; c) O, Z. q9 |s = size/2; // 象限大小% w  P4 f2 h% T
$ i3 v# }& ]: r! H
/ /覆盖左上象限
5 ?9 F6 ~, V- n* b  h4 y3 S9 L! Y8 i' S% N2 j+ F! Q
if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)
- _. F8 c/ \; n* P  M
5 @* @" C# d& v: j// 残缺方格位于本象限
! s) a( _6 G, ~& F) n" N. x' n  s* B& R( k, I
Ti l e B o a r d ( t r, tc, dr, dc, s);
, |. r1 N+ k: K, D9 u: p0 ?3 N9 U
else {// 本象限中没有残缺方格; k) T# U" `; O
' I/ R7 y8 V$ Q, |( Y
// 把三格板t 放在右下角
# b# O' W& @. O: J  P
# s; @: m- ]0 UBoard[tr + s - 1][tc + s - 1] = t;" Z0 K  g! C5 Z4 [3 h5 F. R
: s' G2 z( @8 u, ]3 x' k4 u
// 覆盖其余部分
% A4 ?6 S; |1 T1 f' {7 H- f- n! {' h) a4 p
Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}$ M4 q* m  {! `" C, u

1 ~3 V. H4 y+ G( j/ /覆盖右上象限
7 R6 ^6 H1 E4 s9 i7 G# [9 f( O( L2 y# A; p* H* B' a
if (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)
; q/ t7 K6 g% O7 @- n! u: W$ T
/ ^0 Q8 v8 e; g% p6 q// 残缺方格位于本象限9 V0 o# F( _& ^+ D
4 |0 n7 g8 \! j; E7 P' o: M/ `
Ti l e B o a r d ( t r, tc+s, dr, dc, s);
3 r/ a1 U, r" c  U% u' x# S. e# }9 M- E7 b  B+ K
else {// 本象限中没有残缺方格/ s5 @" T) P  Z( t* M: J) y. f

# `% Z  A: c9 `, k; J// 把三格板t 放在左下角
: M; p2 g) @! {9 S$ ]+ ?! w$ f4 x7 i& a/ d4 _- t. m6 r
Board[tr + s - 1][tc + s] = t;% \9 H# p: `5 A8 c( p1 i- Q- w

0 P9 R' f& R9 g6 a# C// 覆盖其余部分1 T- {! f8 |4 j* ?( s

2 k! k. @6 [; m: Q7 u$ _Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}
2 `. y, x! \! M) V5 Y2 D' L4 y$ t8 H3 W! Z! g
/ /覆盖左下象限
6 H  z8 N  x2 N- @, }
, {' `- E* v3 @+ Pif (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)* Q3 s2 A2 P9 v2 S1 c- O3 ?9 W
. Z1 f6 [3 r9 F: X) V
// 残缺方格位于本象限
, {( i& P1 |' d% p$ B* c( S
+ B% N% i5 \% @! t: ?9 n7 Y2 e+ LTileBoard(tr+s, tc, dr, dc, s);
# H+ H) @% X5 J: `7 c
7 t+ O5 ]) u# [7 F1 u3 ~' L/ O% G3 ielse {// 把三格板t 放在右上角/ O' S: c5 F  L  j" E; I1 X

. F) ]1 i5 t# f9 D  bBoard[tr + s][tc + s - 1] = t;( }8 F' n) i2 \8 z: r
! O8 }1 |/ T( g; h6 ^
// 覆盖其余部分5 P3 t5 C0 a; ~

8 X" L% y! c& a1 Y' ~; i7 [! cTileBoard(tr+s, tc, tr+s, tc+s-1, s);}' V* s2 i+ c( k5 T- \' ]8 h

) l7 M7 V4 x. Q' {2 E/ \) n1 v// 覆盖右下象限
8 X/ f8 F: F# `( k7 O4 |" Y: M3 c) b* b  S: q
if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)% Q  g2 n  Z: Z
; A# c/ O  l' V8 q
// 残缺方格位于本象限8 Q/ Q5 J5 U6 t. C

3 v  X: p' ]. C7 a; r; \& X  fTileBoard(tr+s, tc+s, dr, dc, s);
6 o3 S2 |, v( q5 L/ C7 {  \& q* o/ U: e) ^. ]
else {// 把三格板t 放在左上角
9 [. w0 i8 K. j4 z: ~; ^2 a7 Y- t: `7 [; T7 }8 H
Board[tr + s][tc + s] = t;
+ r1 x: u( `: o. K; d5 {$ p2 {+ g3 ~% Q
$ X. Z; r+ p/ Z# u6 p! Z% {// 覆盖其余部分
; [0 |# N* z' b3 e$ p9 m( I  o( N0 c  n
TileBoard(tr+s, tc+s, tr+s, tc+s, s);}
# x8 c$ w, `/ v! ?) a1 j* e8 d& O( S& X3 x4 x) G2 H
}
/ }+ y) ]4 R. V6 f* H' Z
! I5 d& M8 z! \void OutputBoard(int size)
- V; n3 X# M. L6 Z2 ]1 p0 ?! a* D" v
{
- [8 b5 L; z* R9 A: }8 N* \) C! s& y, E
* Z2 I3 O. N$ F4 Q8 m3 |$ L/ dfor (int i = 0; i &lt; size; i++) {
8 p2 y" Q, ^5 e& q- {: J+ y3 }# R. b" H2 m* q' O* p
for (int j = 0; j &lt; size; j++)/ b. Z6 p. x7 @5 s& u

4 }. B5 s. Y3 `cout &lt;&lt; setw (5) &lt;&lt; Board[j];5 c3 P8 z8 X, n4 i* B% |# x
( Y  f- Z% M1 P9 L# E: M6 E/ {2 e% ]
cout &lt;&lt; endl;, O. O2 O0 d) ^2 B7 C+ p' t3 q
' m* `2 {- G& K' z
}+ y7 A* |5 h9 B7 u& X+ G, Y, H
2 s$ t1 E3 j" C& n. ?6 _
}
7 q: i: G8 v- a$ M: E# Z
2 v. i/ c- s" f* _4 F可以用迭代的方法来计算这个表达式（见例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