2007年的质量进步

声明:本文使用的代码和例子来源于《计算机算法设计与分析》(王晓东主编，电子工业出版社)。我对代码做了一些修改，这样我就可以在tc图形模式下看到主题的结果。

题目:在由(2 k) * (2 k)个方块组成的棋盘上，有一个特殊的方块不同于其他方块，称为特殊方块，这个棋盘称为特殊棋盘。现在要求用L形方块填满棋盘的其余部分(注:L形方块由3个单元格组成。也就是围棋中忌讳的蠢三角，方向任意)，任意两个L形方块不能重叠覆盖。L形正方形的形状如下:

■■*■■***■*■

■******■*■■*■■

题目的解法采用分而治之的方法，即子题和整体题具有相同的形式。我们分割棋盘，切割一次后的棋盘如图1所示。我们可以看到，棋盘被切割成大小相同的四个子棋盘，特殊的方块必须位于四个子棋盘中的一个。假设特殊框位于右上角如图1，我们在图中的位置放一个L型框(用灰色填充)。这样，每个子棋盘都有一个“特殊方块”，我们继续这样划分每个子棋盘，直到子棋盘的大小为1。

所用L形方块的个数为(4 K-1)/3，算法的时间为O (4 K)，是一个渐进的最优解。