QQ登录

只需要一步,快速开始

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

残缺棋盘

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

823

主题

3

听众

4048

积分

我的地盘我做主

该用户从未签到

发帖功臣 元老勋章

跳转到指定楼层
1#
发表于 2004-10-4 05:16 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
<b>残缺棋盘</b>9 H: C) B6 W5 W: U  b9 B. H+ ~
<>残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注意当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - 3 a所示)。事实上,对于任意k,恰好存在22k 种不同的残缺棋盘。
8 R( [& ^$ h  }
% Q1 W& x2 M, @* C0 Z$ f1 c6 L残缺棋盘的问题要求用三格板(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中的某一方向的三格板来覆盖。0 V8 k" w1 |' k. ]& o
, w: G1 ?: J; a" P3 V2 E  o
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖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的棋盘中仅仅包含一个方格且此方格残缺,所以无需放置三格板。
; D  i# \# a, l% U* |1 k
( y  \) U$ G/ Y7 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。函数的输入参数如下:
* b& X8 A& d+ G' c% c9 s
; t- P% K+ Q2 R? tr 棋盘中左上角方格所在行。4 p, n8 F* @* }; r, F- g
0 h; P. W5 k/ w, @  l- D3 {# C) s
? tc 棋盘中左上角方格所在列。
9 \/ r" T5 e4 H& ]7 D, c
2 \& w, f) g6 ^* u/ I* @. a2 Z* m? dr 残缺方块所在行。9 F7 O5 Z& e6 L
* O( g. W+ H; f( O$ l
? dl 残缺方块所在列。! j( W8 ^  Q, X' W, |
$ f/ \/ T/ ^) M  y& C/ ?  F
? size 棋盘的行数或列数。9 n% @7 y% C! d0 E9 ?# f

8 x; y8 q, O2 h. |% G; JTi 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来表示这些三格板,并用三格板的标号来标记被该三格板覆盖的非残缺方格。  U0 r7 W' I/ s/ |( C& Z+ ]
; W/ t6 c! N& E: X
令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 表示这些额外时间。可以得到以下递归表达式:
2 ?' I8 P8 V7 j$ o1 r3 \+ M! ~: }  {; G8 W+ _  u
程序14-2 覆盖残缺棋盘
/ k) M" D" u& h" h( ], v2 Y+ U7 X# O) }
void TileBoard(int tr, int tc, int dr, int dc, int size)
' {5 S: `( T5 s2 P* E! ?) G4 Y7 h2 L: @$ h- V2 t7 S3 e/ T) i1 j& z
{// 覆盖残缺棋盘
. K: x. O2 i5 P% I8 `- X5 v2 t/ g" f! `* A5 n# d4 o$ E
if (size == 1) return;: H8 ^0 M( |& A) n+ e
. a: r# V* S  O7 ^. z4 [7 Y
int t = tile++, // 所使用的三格板的数目
( w2 V9 Q* i% Q" J4 T2 h1 t+ O2 z
s = size/2; // 象限大小
; P5 u2 g# _% [1 L6 u, Y3 V! o
/ \: \" ]4 P9 T. R" P4 n/ /覆盖左上象限' h4 \  g- n& u! p3 c5 l8 r: i
: ]" P6 \2 e' o  G/ q/ v
if (dr &lt; tr + s &amp;&amp; dc &lt; tc + s)
  ~1 D  W7 m/ I' F/ T3 x5 {% Y& }" P! g5 d9 w
// 残缺方格位于本象限6 D6 @. p/ F& l: Z: n+ V8 A

3 ^1 H  L; r! {0 _$ D& wTi l e B o a r d ( t r, tc, dr, dc, s);+ T3 I3 L3 B5 W- |' I+ k- R. r
+ y% r, O2 c0 ]3 Y( x
else {// 本象限中没有残缺方格
+ R  }/ C) ], ?4 L# p4 Y6 q6 j
5 |2 w# n3 s' Y9 t2 M// 把三格板t 放在右下角& }0 i$ j& T3 B

5 U. U  j# ?+ G' T2 V( BBoard[tr + s - 1][tc + s - 1] = t;% m( g' G3 {4 _" W3 t! X# l- `2 Z- c% v
1 k+ L1 R6 G3 W& X+ i: e
// 覆盖其余部分
5 R. N5 A8 R, S# W* |$ [) @
8 a& G3 x6 r  a$ wTi l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}
+ {7 R4 ^+ b9 D, u0 N' Y* d. f3 c( Y, q+ K
/ /覆盖右上象限
, S- I! H: o; f+ k* Q
$ z* O- W) H8 ]2 W$ cif (dr &lt; tr + s &amp;&amp; dc &gt;= tc + s)
1 j, p4 h; e" x4 L- ~6 t% L  G+ F. g& \  s
// 残缺方格位于本象限
6 F5 s8 g% B' \( f
4 ~! N2 o2 B. o: c9 P: vTi l e B o a r d ( t r, tc+s, dr, dc, s);: ^: o  b7 t6 b

& X; Z# w" l- O: T' u7 d  k5 z9 aelse {// 本象限中没有残缺方格
, E3 l* B. C, E8 ]  a
6 q" V% }% a$ ^0 ^5 O// 把三格板t 放在左下角% O( ?/ Z9 e: z3 c- ~( d

$ ^3 v3 L" K. F, s- P& s9 wBoard[tr + s - 1][tc + s] = t;
# j5 S, b  [+ c9 h6 _. C; O$ B; V- Z. Z  x
// 覆盖其余部分
5 J% O  B  }& y3 s. P6 e# F. |  b( B
Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}; C5 x* Q& x7 O2 R8 C$ p+ T. ^

9 B/ K. }6 v( w- H- C4 c/ /覆盖左下象限. t" A4 x4 a5 i

, D) ?% J: p. |. E: {" B. L% dif (dr &gt;= tr + s &amp;&amp; dc &lt; tc + s)1 C: [; `/ q/ I7 f% s  k, u( b
, p) _# s  w* q; F" x* }" c' F* t
// 残缺方格位于本象限% F: D! b/ ~& r: q8 T
5 \- y2 H6 b/ u+ Q6 m! a  L5 Z
TileBoard(tr+s, tc, dr, dc, s);
- Y0 \' z# c4 D1 `  _0 ]) x1 B, @
else {// 把三格板t 放在右上角. |7 {9 T* T7 i2 H. y

/ n: i4 g5 _0 BBoard[tr + s][tc + s - 1] = t;* d' K: m- r2 x/ y( R
8 o) r; z4 h# {0 ], |$ Y# e2 ]
// 覆盖其余部分  v. X+ J( n% _; f5 [

6 H  v* y1 s% VTileBoard(tr+s, tc, tr+s, tc+s-1, s);}
2 U6 t" g) j' A1 s7 Q6 l) z3 g* T9 P, P
; e& b, X# ]& M. z) B# i// 覆盖右下象限
6 E+ M7 i& H# Y+ P0 v8 F8 v3 d/ a+ D; T
if (dr &gt;= tr + s &amp;&amp; dc &gt;= tc + s)5 V- c: {& N& F. G0 R
9 {3 g# B" M0 L
// 残缺方格位于本象限
. e- c- u3 `  J( v/ T# z- G- b, ^) n- D
TileBoard(tr+s, tc+s, dr, dc, s);3 h! `8 J3 e- i; O; @
0 h$ e% `7 h$ g* D: j, ~* @
else {// 把三格板t 放在左上角
- K' R2 y* P( Z( U7 d+ Z  n) y) m" K/ A% n) h4 O9 Z  F; Z( h2 M. _7 e4 e
Board[tr + s][tc + s] = t;5 N+ w5 T2 ]# T3 f) P. E. M
9 R7 N: D% n. B. c* `( b7 J
// 覆盖其余部分
. ~" S0 S! k2 v4 d$ }- j! ]9 S6 s3 G: ?. H3 R7 D; Y
TileBoard(tr+s, tc+s, tr+s, tc+s, s);}: P0 r; [# m) w: D9 t9 ^  u
; V4 ]# V# I4 V3 h+ M1 X
}
" W  e& B$ ?" e& j& }% g
1 b$ K2 O* u% ^  Rvoid OutputBoard(int size)
# @; v" Y% u3 M% |
! l6 S8 I/ _$ l1 U$ N{
7 w0 k0 y% I1 w$ L* P2 t0 V+ }9 w5 ~/ h9 h5 k' l% r# h
for (int i = 0; i &lt; size; i++) {
1 b1 p- }/ M) G6 {, B
; p" {& q& ^) [2 q6 J( wfor (int j = 0; j &lt; size; j++)
- W4 Q7 l  M1 O) c7 n! ]0 [( ?3 K: j% F
3 \) `8 \8 v; Q/ f/ F; Ncout &lt;&lt; setw (5) &lt;&lt; Board[j];7 i/ T  n1 o7 c2 d2 x
+ O0 }5 c/ ]" N# m: `
cout &lt;&lt; endl;
7 g& m) h" t4 ?2 Q5 Z; R& o( Q( x$ u. Z9 ^/ v1 s
}
% H5 T8 d9 m; q! f# }
3 X7 ?& p) U$ F1 s" @6 W}
, \! W3 M/ o' G- U+ M- D8 H9 S3 h; l* @0 T
可以用迭代的方法来计算这个表达式(见例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-15 10:22 , Processed in 0.527891 second(s), 76 queries .

回顶部