副标题#e#
残破棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，个中恰有一个方格残破。图2 – 3给出k≤2时各类大概的残破棋盘，个中残破的方格用阴影暗示。留意当k= 0时，仅存在一种大概的残破棋盘（如图1 4 – 3 a所示）。事实上，对付任意k，刚好存在22k 种差异的残破棋盘。
残破棋盘的问题要求用三格板（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中的某一偏向的三格板来包围。
用分而治之要领可以很好地办理残破棋查问题。这一要领可将包围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的棋盘中仅仅包括一个方格且此方格残破，所以无需安排三格板。
可以将上述分而治之算法编写成一个递归的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。函数的输入参数如下：
? tr 棋盘中左上角方格地址行。
? tc 棋盘中左上角方格地址列。
? dr 残破方块地址行。
? dl 残破方块地址列。
? size 棋盘的行数或列数。
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来暗示这些三格板，并用三格板的标号来标志被该三格板包围的非残破方格。
令t (k) 为函数Ti l e B o a r d包围一个2k×2k 残破棋盘所需要的时间。当k= 0时，s i z e便是1，包围它将耗费常数时间d。当k > 0时，将举办4次递归的函数挪用，这些挪用需耗费的时间为4t (k-1 )。除了这些时间外， if 条件测试和包围3个非残破方格也需要时间，假设用常数c 暗示这些特别时间。可以获得以下递归表达式：
#p#副标题#e#
措施14-2 包围残破棋盘
void TileBoard(int tr, int tc, int dr, int dc, int size)
{// 包围残破棋盘
if (size == 1) return;
int t = tile++, // 所利用的三格板的数目
s = size/2; // 象限巨细
/ /包围左上象限
if (dr < tr + s && dc < tc + s)
// 残破方格位于本象限
Ti l e B o a r d ( t r, tc, dr, dc, s);
else {// 本象限中没有残破方格
// 把三格板t 放在右下角
Board[tr + s - 1][tc + s - 1] = t;
// 包围其余部门
Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}
/ /包围右上象限
if (dr < tr + s && dc >= tc + s)
// 残破方格位于本象限
Ti l e B o a r d ( t r, tc+s, dr, dc, s);
else {// 本象限中没有残破方格
// 把三格板t 放在左下角
Board[tr + s - 1][tc + s] = t;
// 包围其余部门
Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}
/ /包围左下象限
if (dr >= tr + s && dc < tc + s)
// 残破方格位于本象限
TileBoard(tr+s, tc, dr, dc, s);
else {// 把三格板t 放在右上角
Board[tr + s][tc + s - 1] = t;
// 包围其余部门
TileBoard(tr+s, tc, tr+s, tc+s-1, s);}
// 包围右下象限
if (dr >= tr + s && dc >= tc + s)
// 残破方格位于本象限
TileBoard(tr+s, tc+s, dr, dc, s);
else {// 把三格板t 放在左上角
Board[tr + s][tc + s] = t;
// 包围其余部门
TileBoard(tr+s, tc+s, tr+s, tc+s, s);}
}
void OutputBoard(int size)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++)
cout << setw (5) << Board[i][j];
cout << endl;
}
}
#p#分页标题#e#
可以用迭代的要领来计较这个表达式（见例2 – 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必需耗费至少( 1 )的时间来安排每一块三格表，因此不行能获得一个比分而治之算法更快的算法。
