数学建模社区-数学中国

标题: 残缺棋盘 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:16
标题: 残缺棋盘
<b>残缺棋盘</b>; q2 I7 ]. L& o& n
<>残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。
7 |* t, h9 f% Y) s5 Z+ r1 `7 _) M  a( I1 s6 y0 A
残缺棋盘的问题要求用三格板（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中的某一方向的三格板来覆盖。
7 S* S# y9 W& r9 a& w9 R. E& B- K7 E  `
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。& `* b: P, I; T" j0 E* I

! a" C  ^/ N2 t2 p, d; D可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下：, m) p- R+ P! f
9 l: U* T/ v9 m" I  H6 P
? tr 棋盘中左上角方格所在行。
7 [- [) X: s4 z
# H4 Y2 [0 i6 o: F: G. m; R? tc 棋盘中左上角方格所在列。: q8 M/ V8 C3 V$ T5 D# p
) m: i& g1 |# e1 ~, u0 J( ~  G; m) b& j
? dr 残缺方块所在行。
" \( i1 V& |, k( U. m6 o$ ^7 H+ T) s7 i0 x# d* N
? dl 残缺方块所在列。
4 L0 \/ h) T# o: c
& j) f& e- m% G. b? size 棋盘的行数或列数。  \4 f: F. M) [( C( J9 U9 |
1 @0 O* @! V" c& F
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来表示这些三格板，并用三格板的标号来标记被该三格板覆盖的非残缺方格。
% o$ e' N: K  p) ^: a) \9 a# F# ?- g
6 d' R: V9 C7 I# P令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 表示这些额外时间。可以得到以下递归表达式：
' S- a: x. }1 _; A+ I% _' U$ l; C1 r
程序14-2 覆盖残缺棋盘
7 b/ q) r& U0 a$ W( Q+ E- k3 G/ y0 Q! \1 ]  f  B
void TileBoard(int tr, int tc, int dr, int dc, int size)& o2 O$ D3 [& K2 x

0 K3 q8 f+ u% S" @0 |% o, h. h{// 覆盖残缺棋盘% n' x4 U( W% Z6 Q% F* ]0 G

, B, T- [; U5 }! sif (size == 1) return;! I' e1 |% B+ b/ d5 H& A  U5 i; D
% y" S+ |- ~- `/ R2 D& g) K1 {
int t = tile++, // 所使用的三格板的数目
7 u  E8 }" [0 M& L0 w+ v; L) t/ z: \5 l: V: j2 W( k8 ~
s = size/2; // 象限大小* M1 C1 C. v& X
  ^5 U, p$ [& b* a6 B& J
/ /覆盖左上象限
) I5 o6 a6 ?  z9 ]7 U; P- t- i& S% _/ [$ I
if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s): u. C! y/ S2 u) d, Z" C" u
( M, v. [% ^1 l, }
// 残缺方格位于本象限
- ?5 Q& \4 q( m, \& Z% H2 Y0 @* V
Ti l e B o a r d ( t r, tc, dr, dc, s);1 w1 L- D0 V, J% \
# D$ m: s. [* X  b' q
else {// 本象限中没有残缺方格
- e( B5 }; C0 L2 @, l, T1 l, G1 @4 G5 @8 C. k5 R  D
// 把三格板t 放在右下角
6 n7 T. g0 ]* z" p: a. N: [$ q9 o* f# z* _5 o. D7 t
Board[tr + s - 1][tc + s - 1] = t;
4 m$ L5 i0 y0 i$ H
" t2 Q* W2 `+ j: Y// 覆盖其余部分
5 C# I/ ~2 C& j# _$ w2 c
" {3 y, [. {8 T6 D6 pTi l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}
5 }2 M( ]! r; X( K1 f7 U- a# O4 D, `4 F' z8 y- [" l' Y
/ /覆盖右上象限7 V: u6 ^+ t* s3 ^
% C. l! T- j) `6 a+ w& F, h
if (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)# G  {9 I5 V  l5 z$ w8 }/ W% a$ D& C
5 l  _2 `* Y/ a/ M0 `: w# M% A5 {
// 残缺方格位于本象限
+ F: x8 G  s; z1 D! f. W4 v
# U" _# \  L. W/ i3 n$ n, `5 {Ti l e B o a r d ( t r, tc+s, dr, dc, s);/ q4 _. m3 U$ O
; Q8 q2 N6 b! v0 w' y2 C
else {// 本象限中没有残缺方格- Q9 n* Q& r# `' b) f/ }& b3 K

8 e# \* q* W: A/ t( s// 把三格板t 放在左下角
" q6 t3 J, E( E; J6 D  \; c# ]* o% u0 c
Board[tr + s - 1][tc + s] = t;/ @% n: c2 c5 `3 F9 ^
: P' v5 E. j. i
// 覆盖其余部分& P; \/ Q( n9 L1 F1 {7 C' R+ @5 Y! v! P
, v8 }' \. U! s* ]7 g
Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}) r# ^/ I% J: ^7 e

* S  O2 Z, s( e. V) J9 B/ /覆盖左下象限" w& R% B8 N2 H, w% x/ }8 M
5 }) q7 y* a0 s
if (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)
/ g7 M2 e( ~! f1 p! ^3 {
+ U2 x, O/ Q; Z( _! ~' [// 残缺方格位于本象限
7 y9 O! w. }4 |' |( D9 p: W/ C- y7 Y+ f; I% i4 [# q
TileBoard(tr+s, tc, dr, dc, s);" i' l/ o# I7 T6 l% R# o5 Y
/ w, R  Q1 E) A; k' |
else {// 把三格板t 放在右上角& B' c6 x3 P0 a+ y
: X0 j; A- D" J! m7 h: l
Board[tr + s][tc + s - 1] = t;
1 k- G: O0 P1 ~9 c& f. ?7 S8 ~" l8 Y
- m; w  `" J7 O// 覆盖其余部分- L. }+ ?4 S9 J3 O+ j

$ e, O4 C' N! B( m9 g5 g$ I: YTileBoard(tr+s, tc, tr+s, tc+s-1, s);}+ v# ^5 s. b3 I  I& k9 `! Q& m
* c$ P0 p5 f% O) l* ^+ ?5 \. P
// 覆盖右下象限
0 W% v6 t1 N* K! ~$ \8 s+ W# t# n
if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)
( Y( a# S! R& t" M0 Y' V
( N" z2 \* a5 I2 ~+ t4 ?$ L6 B// 残缺方格位于本象限
+ K1 i1 c2 P" F; h
8 @! S" Z& i  d! J+ G% a5 J( zTileBoard(tr+s, tc+s, dr, dc, s);
% Y( n/ L( ^  Y0 V  z! Y4 }  r6 P: u0 u  A6 H6 w- V
else {// 把三格板t 放在左上角: F/ O3 W7 n1 f1 t

/ X; f( [7 X" {' ^" f+ D- i$ K2 `6 D+ hBoard[tr + s][tc + s] = t;
* k# Q5 N- |/ T$ a$ {# c$ H/ P3 l6 k  ]
// 覆盖其余部分
3 g( e7 r) A& c) V! m
0 h* e6 X6 V' @$ D3 g3 ?( D2 ATileBoard(tr+s, tc+s, tr+s, tc+s, s);}
3 t3 @6 H0 j: c5 k
" o; d1 X* x$ @) Q# c7 E}
+ A' M# Z" x0 g% g) ]
% u: L$ O# m& r9 f! Evoid OutputBoard(int size)
2 o. ?: d. _# h9 c
) v, `% ]6 Y1 J4 L! V; Y' _{8 C3 Y5 O* ?! L3 [6 S
' `1 g9 ?) ]* J. f1 K
for (int i = 0; i &lt; size; i++) {
! L! P0 S4 [2 S! n, Z+ @( F: o1 u, c' |, y( N0 }) X9 j
for (int j = 0; j &lt; size; j++)
4 ^! s* C, ]5 k  {) L) M2 Z) b9 f+ R* B7 p
cout &lt;&lt; setw (5) &lt;&lt; Board[j];
6 N- f7 {  W: N, j' E6 O! J) }1 j  C& H; U; @  X
cout &lt;&lt; endl;
7 ~( v9 K+ x2 @7 ^- m) n
2 m7 L9 X# ^, y+ a3 M& \2 a- f. I}9 i& I% T+ s. m2 ?! [

- ~. Z0 Q' L* c8 C/ P  j}
8 \) ~0 X4 m8 [5 E0 m
" T0 {8 D$ a# y6 {  Y可以用迭代的方法来计算这个表达式（见例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