QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3773|回复: 3
打印 上一主题 下一主题

残缺棋盘

[复制链接]
字体大小: 正常 放大
韩冰        

823

主题

3

听众

4048

积分

我的地盘我做主

该用户从未签到

发帖功臣 元老勋章

跳转到指定楼层
1#
发表于 2004-10-4 05:16 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
<b>残缺棋盘</b>0 s( |# k- `7 v5 J$ U+ |& g7 F% Q
<>残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注意当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - 3 a所示)。事实上,对于任意k,恰好存在22k 种不同的残缺棋盘。; r" V0 B% I8 c
: u6 v# E7 T( l+ [) d- I: ~
残缺棋盘的问题要求用三格板(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 l5 q7 q2 @; S* q* l7 x" p% g: u) b
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺,所以无需放置三格板。
/ Q' W, R. q# {( u: a4 t) T8 q# F. M, q0 Q" g
可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下:  l. d  l% t# F$ v1 o) u
. _+ K$ i: [/ i# N7 P8 N0 n; N# d( a
? tr 棋盘中左上角方格所在行。2 O9 s+ T  f, n1 g* W/ m4 a5 }1 D
+ L. W# q4 j( U5 i( b
? tc 棋盘中左上角方格所在列。
6 O" l+ e. F: z! X
; U4 h! |; ~: I8 C% V* H0 [7 u, p? dr 残缺方块所在行。
% E+ l' l: u- x% n
) W: k, V  z  z/ H% a" V9 I? dl 残缺方块所在列。- v% W. }4 B3 @, f

% C' u0 J; S* X& ^1 ~+ g/ N) w? size 棋盘的行数或列数。0 m1 ]& f6 r2 B7 |4 \! G

; j1 P" ], c0 V' BTi 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来表示这些三格板,并用三格板的标号来标记被该三格板覆盖的非残缺方格。2 u  A+ b7 {0 ]+ f' Z: R

0 @8 g4 Y3 q6 H' Z  |; C1 ^) q令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 表示这些额外时间。可以得到以下递归表达式:
( g; v( x) \* M4 P4 E  ^# P) ?/ a2 d
程序14-2 覆盖残缺棋盘% E' z/ h' F7 q/ V* K  u! Y0 ]

; `& G1 R( L3 q  v& Q3 b% X2 t8 I4 Wvoid TileBoard(int tr, int tc, int dr, int dc, int size)
) F( j( {* n& ?7 @5 T" x/ `. p8 z9 U- b* p) h1 Z3 a+ P! q
{// 覆盖残缺棋盘
8 ?2 G: I1 b- m* V/ B* g$ D# {; [$ |/ |# }$ U: K
if (size == 1) return;$ H1 N, X0 R6 b" J! _8 s$ y
, i3 m1 q! h# v: t5 P6 G" v$ f
int t = tile++, // 所使用的三格板的数目9 B8 X6 h+ y8 d) G
' Z( V  C4 f( a. t4 r: G# E
s = size/2; // 象限大小  B  V0 ^: w0 @- n: c* Q
3 r. y& V5 ]& X2 {
/ /覆盖左上象限
& d5 l7 X+ Y5 T. V& i- E' x; a& x- K# v2 ~
if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)0 f3 G/ O1 t6 y1 ^

" g. ]) a7 O8 W0 l// 残缺方格位于本象限
3 Z4 F; a, M2 r" w4 E8 v9 e7 M6 E6 P! q) Y
Ti l e B o a r d ( t r, tc, dr, dc, s);
6 t. i: c( ?- W5 N5 o
9 l/ T" @1 H: w. @9 A5 X$ y6 q4 z2 kelse {// 本象限中没有残缺方格
, @4 Q) {4 ^" Z! p8 o) Z( a$ t$ c3 Z# [( P& Q- P
// 把三格板t 放在右下角& u* Y8 l, t) r* L/ z% |
  K% P7 ^9 X4 j1 @) H
Board[tr + s - 1][tc + s - 1] = t;
+ |- K, f8 v4 t# e" }) V5 {0 [8 Z9 p0 j! y* N
// 覆盖其余部分
5 E) b) Y) `2 ~" y1 f+ Q/ q! ]) W8 x; |5 ~( t  b
Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}
. {8 y6 r$ y# d0 S7 ^
: \6 C3 I3 ^1 ]* d& E9 O; s( i9 H  H/ /覆盖右上象限
0 R+ R8 s) F8 {$ L8 B7 Q1 x, Y* k, _7 ^- F1 ]3 P5 l
if (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)
$ R2 W& `! ~' d$ z3 [
) [8 m( W/ M6 K; `$ d3 d// 残缺方格位于本象限
7 c; k  l- {/ s4 k7 O
( O) v. R! x' l. a- tTi l e B o a r d ( t r, tc+s, dr, dc, s);3 r9 m3 p% `9 ]6 ^5 u' V
+ N9 D  m9 g3 n- ^! b7 N9 W: Z
else {// 本象限中没有残缺方格
7 o! W3 J+ K5 g% ~, q7 p" z2 X9 R. l
// 把三格板t 放在左下角* p; u: T$ ~( Y& A- S
( n7 o- f' X$ E" W: G4 Z
Board[tr + s - 1][tc + s] = t;1 R- O$ P# r* K! r. g, E% O/ F) R
" f1 x, |" O- Z$ Z4 @3 A4 c! F6 M! o$ p
// 覆盖其余部分* [6 J- s9 t0 Y# d, O
# O4 y# a3 o+ u  `  V' \/ Z
Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}
) D& B% }9 k0 N0 q; B) E
8 `# F  F# p7 d. j/ /覆盖左下象限  d. N% H) L% P1 F. \2 B
. V# X  `7 b: b1 o
if (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)
: I0 a# P) O; E
$ I/ t4 h9 m2 `  O// 残缺方格位于本象限
% d  `7 n- H+ U0 {
9 [; J2 C1 `( r* O$ gTileBoard(tr+s, tc, dr, dc, s);
# r' ]  z! K  Q) W- S4 A# v, ~" r# V
else {// 把三格板t 放在右上角8 F/ F, f  e. _3 e

7 Q+ a  F5 X4 K  s8 X. m" XBoard[tr + s][tc + s - 1] = t;
* Q# e$ q. b  r& L4 l) V4 Q3 d
8 F1 N. r: Q& \: `8 S$ \// 覆盖其余部分
3 p& v& E' G) x/ w( L
3 c; D( G7 U( v9 r' mTileBoard(tr+s, tc, tr+s, tc+s-1, s);}/ v5 K: j0 Z- X3 @
. q0 S* @& ~! Q+ `! O( R- X1 S
// 覆盖右下象限
) t$ Z9 g# j4 H+ b
) |2 `3 A4 |2 m- ?( o$ J/ b4 y. tif (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)3 `4 o0 \3 `" {2 T4 A3 O# r
3 j  h6 ^6 F/ }- s1 h
// 残缺方格位于本象限& B, Z- o* I% Y/ Y& Z
, N% d6 Y+ a' B* D" N: V
TileBoard(tr+s, tc+s, dr, dc, s);9 v2 N. B. u+ n0 S/ u4 b
7 A8 q+ p1 i' z5 D' K
else {// 把三格板t 放在左上角
/ Z$ Z7 ]% ]( `) r1 o: E$ Q% R8 v4 B8 s
Board[tr + s][tc + s] = t;$ B, M0 C$ [9 m# M* P: d
" [9 v( D/ }; u% g4 a) {
// 覆盖其余部分4 }0 z' v, c' p( }5 c8 W

( R3 r0 D& A$ V0 XTileBoard(tr+s, tc+s, tr+s, tc+s, s);}7 d" H$ v4 R6 G! S: p! ^5 u0 `1 n

; {  T, O! ~( X7 G2 q$ r  L2 q1 W}
' q0 p, j7 p7 `8 ]4 T. z' d8 h! b
void OutputBoard(int size)
* o4 b& m& t& w7 i* ~
. S: b" X9 n; k# q6 c. C) l{! ^1 `( I- D( K
  E( {) K3 B9 ?* A/ T) D
for (int i = 0; i &lt; size; i++) {( t$ l/ v& R6 l* O/ n
1 b% V; i6 C* b0 Z( l
for (int j = 0; j &lt; size; j++)  l/ Y& t$ f# u/ y- L% g: ?
5 M! ~2 G, K) E; {) @- |3 e0 k
cout &lt;&lt; setw (5) &lt;&lt; Board[j];: {. v/ \, h2 m4 c; u

5 S" z0 v# W, Z' A$ v3 M1 {3 Ecout &lt;&lt; endl;/ z/ s! R3 C1 n+ M& @. f" @" I
, t0 Y  x0 |! a4 i8 c7 c; b) j
}
# k) x8 A6 r9 Q6 X
$ J9 k3 e' Z2 V3 _3 l1 f}2 r$ y1 z6 S  V8 {: a

  D' N: C0 _. C可以用迭代的方法来计算这个表达式(见例2 - 2 0),可得t (k )= ( 4k )= (所需的三格板的数目)。由于必须花费至少( 1 )的时间来放置每一块三格表,因此不可能得到一个比分而治之算法更快的算法。</P>
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
yammay        

0

主题

0

听众

16

积分

升级  11.58%

该用户从未签到

新人进步奖

回复

使用道具 举报

wendy28        

0

主题

2

听众

24

积分

升级  20%

该用户从未签到

新人进步奖

回复

使用道具 举报

1

主题

2

听众

60

积分

升级  57.89%

该用户从未签到

新人进步奖

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-6-16 01:54 , Processed in 0.457008 second(s), 74 queries .

回顶部