递归与分治

在前面的学习中了解了递归在排序与检索中的应用。本小节将介绍递归更广泛的应用。

棋盘覆盖问题

2^k*2^k的棋盘中间恰好有一个黑色格，其他都是白色。使用L型组合（4种）覆盖整个棋盘，注意黑色格不能被覆盖，白色格不能被重复覆盖。

 由于棋盘2^k*2^k具有高度对称性，所以可以很容易的想到使用分治——将棋盘切割为4块，每一块都是2^(k-1)*2^(k-1)，其中如果有一块有黑格子，可以使用递归解决；其他没有黑格子的三大块可以在中心构造出一个黑格子（如下图）继续递归。递归边界为k=1。

这道题在分治中为了使切割的四块使用同等的递归，变在本次递归的“中心”依据大白块的位置构造L型黑块，所以每次L型的覆盖利用的是这样的一个“构造”过程。最终递归的终点就是上图最右端，可见一直到递归的终点都是在一直构造L型块填充，所以可以证明出经过整个递归过程，棋盘内所有的白色小块都被L型无重复覆盖。

循环日程表问题

经典的一道递归问题，讲的是n=2^k个运动员进行网球循环赛，设计比赛日程表使得每个选手必须与其他n-1个选手各比赛一次，且每个选手每天只能比赛1次，循环赛一共n-1天。设计比赛日程表，有n行n-1列，第i行j列为第i个选手第i个选手第j天遇到的选手。

可以模拟k=1时的情况，此时n=2，所以可以列出这样的一个日程表：

 接着模拟k=2，此时发现可以将原k=1的4*4方块体拓展成4个——原4*4块放在左上角，右下角和左上角一样，右上方和左下方都是左上角每一个元素+2的结果（数学易证，此处不做解释）。同理第一列还是要舍掉：

 同样n=3也是一样的操作，其中右上角和左下角为左上角每个元素+4。以此类推，可以化作一个递归实现。

ACM学习笔记 DAY 24