c语言算法 - 分而治之算法 - 残缺棋盘

核心提示：程序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

程序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;
}
}

可以用迭代的方法来计算这个表达式（见例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必须花费至少( 1 )的时间来放置每一块三格表，因此不可能得到一个比分而治之算法更快的算法。