数学建模社区-数学中国

标题: 残缺棋盘 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:16
标题: 残缺棋盘
<b>残缺棋盘</b>
7 E# R* B. m/ i<>残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。
$ i+ L, n/ d. F# D$ T* C4 z
: X2 x6 A5 r" u2 h残缺棋盘的问题要求用三格板（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中的某一方向的三格板来覆盖。1 X3 H6 n& h. T: D2 d, o
0 X1 k6 u5 i+ t, N( l7 ~6 I
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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 a/ l/ z2 U7 `+ B9 A  ~
, n5 f2 d. N/ F7 p! p" 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。函数的输入参数如下：
0 h" e) V3 }1 ^/ i4 l$ L# j/ e7 M5 r! \9 X1 i4 i
? tr 棋盘中左上角方格所在行。2 |' W# P3 r5 L3 j
, b% x1 P9 q. t/ F$ }# s! y( b) Z9 j+ V
? tc 棋盘中左上角方格所在列。2 g- f2 T6 V* t! h1 I

6 _7 G0 g! E$ s* c. G? dr 残缺方块所在行。
% b# e' S  v, V* A& P5 |- y: g, V: X7 P
? dl 残缺方块所在列。
% K! h" |* d  Z; {# o. a8 q
" }5 [9 L, ?: E" H# K# ]? size 棋盘的行数或列数。
; N6 n( o/ B, b% [# W9 c, a8 P1 b% y5 l$ W6 ]% ]) B* m+ k
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 N% T4 d$ g! x* Z/ V8 P1 ]8 C' |4 M, T! L, c- \  {
令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 表示这些额外时间。可以得到以下递归表达式：
8 m0 \0 l1 _/ y! P$ v5 w; ^
# a! [  o- Q% a3 K; q1 b程序14-2 覆盖残缺棋盘& _  N9 d; |' `! Z! c
, e  |" b6 i/ s) C
void TileBoard(int tr, int tc, int dr, int dc, int size)
6 @9 c3 h* n* s: p
* ^0 @" m2 ?( g' t: Q+ `1 ~{// 覆盖残缺棋盘$ K" n, H' a( N

% I$ R- |6 Y5 P5 Gif (size == 1) return;
& ~# N5 c3 ?7 }+ w7 h/ ~% X7 ~: t5 _9 x& O4 F/ V
int t = tile++, // 所使用的三格板的数目
$ D7 f; W% V) v# A) R( J) [
# b- k; x1 c, [4 |2 u/ F# Q3 ^1 H% }# Js = size/2; // 象限大小5 k6 P1 d) s' s9 J

6 I+ I( J' M% D  b8 \/ /覆盖左上象限
% T$ n( B, i1 v$ }! h4 Z8 b
2 F6 ]0 ~8 x# X/ L& G* xif (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)' V( ]5 j' J9 Q' D5 S7 _
# }0 A, o  P" q3 s% n! G( ]5 n
// 残缺方格位于本象限
! v) \0 B- H/ ^( \' d" f
' S0 k- u6 t1 J% pTi l e B o a r d ( t r, tc, dr, dc, s);1 k' u; R7 O. \+ s" R/ }- z

0 l, f8 l/ u4 n6 w# ~7 ?else {// 本象限中没有残缺方格" K" N9 F" ^: l6 ~. u3 ?& C# m9 |

$ E& k% }8 a0 r5 R+ n+ i% U// 把三格板t 放在右下角
: d, G7 K" \4 l& s; z
: {$ n9 ?$ g0 I7 y+ q; w1 E# n2 JBoard[tr + s - 1][tc + s - 1] = t;7 A4 _% m2 I) P" e$ s3 A5 N- T

8 F" u7 v" {/ A4 R+ t. E// 覆盖其余部分
5 c1 M7 G# M( I/ K) R) X: ]5 {4 L2 i+ R6 v8 _9 v
Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}- }: W* k, i: M3 f3 h
! y7 A& m% n; t9 l+ H; R
/ /覆盖右上象限/ ?, \1 l& G7 C* r. M2 b1 g
# q3 [% X% s9 H3 }  I9 f
if (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)
7 _  d) {2 p2 E/ q7 f  u3 q5 [3 R" l
$ Z9 G3 R+ q% l- f// 残缺方格位于本象限
- C( N* m6 w/ S: V' Q, ^
. A/ g7 f3 h5 y" L) |; Y+ UTi l e B o a r d ( t r, tc+s, dr, dc, s);9 h2 e; x& |0 Q: h% b! Q6 x

+ u! e. R/ m( L, [" ^4 x5 pelse {// 本象限中没有残缺方格
9 v) o) B$ ]3 p$ J. U7 t" f- d
: |% ~) _3 x+ y, B- v* i& d: V1 }// 把三格板t 放在左下角5 D: D) l1 d3 X! L1 o8 G. H  `8 ^
$ M% z* \* C* f
Board[tr + s - 1][tc + s] = t;
8 y1 w0 x& @: @( h0 t/ ]& s( j5 z1 g5 u0 w
// 覆盖其余部分) s  n2 O/ f4 X7 X& a
( P$ ]/ `# @4 s
Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}( A+ @( M/ }- _% C

* r) G# V$ ^% |) h7 j: [9 x0 F2 d/ /覆盖左下象限
! {- c& Y4 k( ?5 {; h; l
' j7 G, g- g' F4 v, vif (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)
6 E- ^- n( Y% I/ T2 F% [( m0 T( m) Z' v+ t. Z; A5 E
// 残缺方格位于本象限
+ Y. V7 W  h+ H' E
( s7 R/ K; n' I* F5 ~! c  a4 D0 uTileBoard(tr+s, tc, dr, dc, s);+ j2 N+ z, s: N, S% X, e2 X
4 ]  Q; h0 C" c  \9 h/ ^
else {// 把三格板t 放在右上角) i: k  W' r( @  y
& d. U, k/ f0 ^, R
Board[tr + s][tc + s - 1] = t;& [: f) t9 m: d8 S! w

  p3 _- |0 j6 l# W# k3 g// 覆盖其余部分% c5 A0 S# b& M6 R4 J! g
$ g9 F% U" v" z, s" G3 B1 i- X# ~
TileBoard(tr+s, tc, tr+s, tc+s-1, s);}
7 o8 C7 H7 P$ i; `, S" o) r$ |. _1 k9 s& u6 z
// 覆盖右下象限
) @' E3 d0 Q; y+ F1 N4 z. _3 g8 l" a" i* l$ t1 e! Z) i
if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)$ o1 k# ^/ D2 ?* {+ m

' c; e- C5 t- z+ B// 残缺方格位于本象限
  C7 s! K# D4 Y# i
' f" [9 Y" H( {TileBoard(tr+s, tc+s, dr, dc, s);
, U" u0 Y! j5 ]
3 V$ p( o# L5 H5 N) A) i9 n- Aelse {// 把三格板t 放在左上角
: D* T2 S+ ~7 Q2 |
4 s8 T/ i4 K4 f( j6 KBoard[tr + s][tc + s] = t;
" H* Y- e4 D6 U" L2 R# ^% |! m. R
7 p0 \$ f2 k1 f  {- y% \// 覆盖其余部分
/ h2 A# {( E1 Z# V2 y0 w- t3 d/ w) ?; m
TileBoard(tr+s, tc+s, tr+s, tc+s, s);}: j" A% e* e& v& T3 e8 I7 r( A) L
; I6 X7 b' s$ z* v
}
/ L+ K" Y$ s9 w* K" d) \3 z! s; e3 g& g9 A$ y
void OutputBoard(int size)- N# V; E5 r6 x9 d
7 ~3 R+ |1 ~6 s! S
{
0 L4 @) x( S8 `" ^: X( G: m% I7 k+ L, }
for (int i = 0; i &lt; size; i++) {+ F- l# S& s: r  B" R
, O; k* \) i' g, d$ m+ d5 n' |4 r
for (int j = 0; j &lt; size; j++). d; }0 W; v1 i5 \. E+ |2 U
+ R3 I8 t4 T& ?  J
cout &lt;&lt; setw (5) &lt;&lt; Board[j];
- F6 X1 p1 B: Y, h1 p8 f( i
8 U7 F6 ?# j7 b' a, p  |5 p3 x" qcout &lt;&lt; endl;# L1 M$ X- B/ P, }2 V
9 _4 i- s) O7 F
}
: `* Z# w# a3 v& I- d; r+ C  V& |5 ]% n; z7 u. ^, t
}
3 P3 e: T- q& c0 V) s4 E/ R0 T3 ~6 W
5 P, Q1 U7 W% I2 |- K( K可以用迭代的方法来计算这个表达式（见例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