北京小学奥数：最大公约数和“分而治之”算法联袂演出

小学五年级所学的“求解最大公约数”问题，其实不难，然而“最大公约数”到底有何意义呢？本期谷老师通过引入“图灵程序设计丛书”《算法图解》[美]，关于“分而治之”算法的分析，深刻说明其意义。

每天叫醒你的不是闹钟，而是梦想和态度

难易指数：★★★★★

适宜对象：小学培优

本期编号：D00012

假设你是农场主,有一小块土地(1680m×640m的长方形，如下图)。你要将这块地均匀地分成方块, 且分出的方块要尽可能大。

([美]《算法图解》第4章快速排序-分而治之)

显然，下面的分法都不符合要求。

解法1-求最大公约数法

思路分析：

1）根据题目意思，我们所要分出的方块，必须能同时整除1680m和640m，所以边长是1680和640的公约数

2）如果要使方块最大，则边长应最大，那么方块边长应取1680和640的最大公约数。

解答：

1680和640的公约数由“2，2，2，2，5”组成。其最大公约数为：2 × 2 × 2 × 2 × 5 = 80m，因此，方块最大边长为80m。

解法2-分而治之

分而治之(D&C)算法原理，参考下文。

1. 最容易处理的情况是，一条边的长度是另一条边的整数倍(此处称为“基线条件”)。如下图所示：

如果一边长25m，另一边长50m，那么可使用的最大方块为25m×25m。换言之，可以将这块地分成两个这样的方块。

2. 你可以从这块地中划出两个640m×640m的方块，同时余下一小块地。现在是顿悟时刻：何不对余下的那一小块地使用相同的算法呢？

3. 最初要划分的土地尺寸为1680m×640m，现在要划分的土地更小，为640m×400m。适用于这小块地的最大方块，也是适用于整块地的最大方块(见下文解释)。换言之，你将均匀划分1680m×640m土地的问题，简化成了均匀划分640m×400m土地的问题！

4. 下面再次使用同样的算法。对于640m×400 m的土地，可从中划出的最大方块为400m×400m。

这将余下一块更小的土地，其尺寸为400m×240m。

5. 你可从这块土地中划出最大的方块，余下一块更小的土地，其尺寸为240m×160m。

接下来，从这块土地中划出最大的方块，余下一块更小 的土地。

6. 余下的这块土地满足”基线条件“，因为160是80的整数倍。将这块土地分成两个方块后，将不会余下任何土地！

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

这里重申一下D&C的工作原理：

(1) 找出简单的基线条件；

(2) 确定如何缩小问题的规模，使其符合基线条件。

欧几里得算法

前面说“适用于这小块地的最大方块，也是适用于整块地的最大方块”，如果你觉得这一点不好理解，也不用担心。这确实不好理解，但遗憾的是，要证明这一点，需要的篇幅有点长。如果你想搞明白其中的原因，可参阅欧几里得算法。可汗学院很清楚地阐述了这种算法。可汗学院主页网址为：

https://www.khanacademy.org/

感兴趣的朋友可以查阅”the-euclidean-algorithm“。

注：本题的“分而治之”算法，摘自于“图灵程序设计丛书”《算法图解》[美] Aditya Bhargava，为了表示对原作者的尊重，谷老师仅作了少量改动。

两种解法的联系：

1）“最大公约数法”，其公约数由“2，2，2，2，5”组成，共5个数。

2）“分而治之”，其拆分过程为，(1680, 640)-->(400, 640)-->(400, 240)-->(160, 240)-->(160, 80)-->(80, 80)，共经历了5次拆分。

都是5，这绝不是巧合！聪明的你，发现了什么没？

分而治之(divide and conquer，D&C)原理

为了解决一个大的问题，可以：

1) 把它分成两个或多个更小的问题；

2) 分别解决每个小问题；

3) 把各小问题的解答组合起来，即可得到原问题的解答。

小问题通常与原问题相似，可以递归地使用“分而治之”策略来解决。

同类拓展：

1.本例的“土地分块”问题，如果不知道土地大小(长和宽)，却告诉你最终分成了80m×80的小方块，而且经过了5次分割过程，能求出土地的大小吗？如果不能，请问还需要什么条件？

2.随便想一个1-100的数字，你的目标是猜到这个数字。你每次猜测后，我都只会告诉你三种结果：比猜的数大、比猜的数小、两者相同。请用两种不同的方法来猜数。如果要求最小的猜测次数呢？

李白：行路难，行路难，多歧路，今安在？长风破浪会有时，直挂云帆济沧海。