分治法

分治法（divide and conquer）的基本思想

分治法是把一片领土分解为若干部分，然后一块块的征服。（大的毕竟比小的容易征服）
划分问题(divide)：把问题的实例划分成子问题
递归求解(conquer)：递归解决子问题
合并问题(combine)：合并子问题的解得到原问题的解

归并排序

先将待排序数组划分成两个待排序数组
依次递归的处理每一部分
合并两个有序数组(在线性时间内可以完成)。

运行时间

T(n) = T(n / 2) + θ(n)

棋盘覆盖问题

无标题.png

棋盘覆盖算法(参数表)
{
如果是单个字符,则返回;
将棋盘划分成尺寸为一半的子棋盘;(2^k * 2 ^k 划分为 4个2^k-1 * 2^k-1);
判断特殊方格在哪个子棋盘中，再用相应的L型骨牌覆盖相应的结合部,
即不含特殊方格的部分在结合部的三个方格
记下他们的位置，作为各部分的特殊方格
依次对左上角，右上角，左下角和右下脚这四个子棋盘进行棋盘覆盖
}
参数表：
递归元：棋盘尺寸size=2^k。递归时棋盘尺寸减半,即size = size / 2。若size为1则终止
棋盘位置参数tr和tc(棋盘左上角的位置参数--横坐标和纵坐标)
该棋盘特殊方格位置的位置参数dr和dc
L型骨牌覆盖的顺序利用全局变量title表示