分而治之——D&C

有时候可能会遇到使用任何已知的算法都无法解决的问题。可以尝试使用掌握的各种问题解决方法来找出解决方案。分而治之（D&C）——一种著名的递归式问题解决方法，就是一种通用的问题解决方法。本文将深入算法的核心。只能解决一种问题的算法毕竟用处有限，而 D&C 提供了解决问题的思路，是另一个可供使用的工具。

假设一位农场主，有一小块土地（1680m*640m）。需要将这块土地均匀地分成方块，且分出的方块要尽可能大。

如何将一块地均匀的分成方块，并确保分出的方块是最大的呢？使用 D&C 策略！D&C 算法是递归的。

使用 D&C 解决问题的过程包括两个步骤。

（1）找出基线条件，这种条件尽可能简单。

（2）不断将问题分解（或者说缩小规模），直到符合基线条件。

首先，找出基线条件。最容易处理的情况是，一条边的长度是另一条边的整数值。如果一边长 25m，另一边长 50m，那么可使用的最大方块为 25m*25m。也就是说，可以将这块地分成两个这样的方块。

根据 D&C 的定义，每次递归调用都缩小问题的规模。我们首先找出这块地可容纳的最大方块。可以从这块地中划出两个 640m*640m 的方块，同时余下一小块地。对余下的那一小块也同样使用相同的算法。

最初要划分的土地尺寸为 1680m*640m，而现在要划分的土地更小，为 640m*400m。适用于这小块地的最大方块，也是适用于整块地的最大方块。换言之，将均匀划分 1680m*640m 土地的问题。简化成了均匀划分 640m*400m 的问题。

下面再次使用同样的算法。对于 640m*400m 的土地，可从中划出的最大方块为 400m*400m。这将余下一块更小的土地，其尺寸为 400m*240m。再划出最大的方块，余下一块更小的地为 240m*160m。再划出最大的方块，余下尺寸为 80m*160m。因为 160 是 80 的整数倍，余下的这块土地满足基线条件。将 80m*160m 的土地分成两个方块，将不会余下任何土地。

因此，对于最初 1680m*640m 的那片土地，适用的最大方块为 80m*80m。

D&C 并非可用于解决问题的算法，而是一种解决问题的思路。