title: 算法D&C
author: 小胡
tags:
正文：
分而治之
D&C直观示例：
假设你是农场主，有一块土地。
你要将这块地均匀的分成方块，且分出的方块要尽可能大。显然，下面的分法都不符合要求。
如何将一块地均匀地分成方块，并确保分出方块是最大的呢？使用D&C策略！D&C算法是递归的。使用D&C解决问题的过程包括两个步骤。
1.1找出基线条件，这种条件必须可能简单
2.2不断将问题分解（或者说缩小规模），直到符合基线条件。
下面就来使用D&C找出前述问题的解决方案。可你能使用的最大方块有多大呢？
首先，找出基线条件。最容易处理的情况是，一条边的长度是另一条边的整数倍。
如果一边长25 m，另一边长50 m，那么可使用的最大方块为 25 m×25 m。换言之，可以将这块地分成两个这样的方块。
现在需要找出递归条件，这正是D&C的用武之地。根据D&C的定义，每次递归调用都必须缩小问题的规模。如何缩小前述问题的规模呢？我们首先找出这块地可容纳的最大方块。
你可以从这块地中划出两个640 m×640 m的方块，同时余下一小块地。现在是顿悟时刻：何不对余下的那一小块地使用相同的算法呢？
最初要划分的土地尺寸为1680 m×640 m，而现在要划分的土地更小，为640 m×400 m。**适用于这小块地的最大方块，也是适用于整块地的最大方块** 。换言之，你将均匀划分1680 m×640 m土地的问题，简化成了均匀划分640m*400m土地的问题
下面再次使用同样的算法，对于640m×400m的土地，可从中划出最大400m×400m.这将余下一块更小的土地，其尺寸为400m×240m，同理你又可以划出最大方块，余下更小的土地，其尺寸为240m ×160m.接下来，一直递归同样的方法。直到满足基线条件，即160m×80m，因为160m是80m的整数倍。
因此对于最初的那片土地，适用的最大方块为80m×80m.
这里重申一下D&C的工作原理：
1.1找出简单的基线条件；
2.2确定如何缩小问题的规模，使其符合基线条件。
