小學五年級所學的“求解最大公約數(shù)”問題，其實不難，然而“最大公約數(shù)”到底有何意義呢？本期谷老師通過引入“圖靈程序設計叢書”《算法圖解》[美]，關(guān)于“分而治之”算法的分析，深刻說明其意義。

每天叫醒你的不是鬧鐘，而是夢想和態(tài)度

難易指數(shù)：★★★★★

適宜對象：小學培優(yōu)

本期編號：D00012

假設你是農(nóng)場主,有一小塊土地(1680m×640m的長方形，如下圖)。你要將這塊地均勻地分成方塊, 且分出的方塊要盡可能大。

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

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

解法1-求最大公約數(shù)法

思路分析：

1）根據(jù)題目意思，我們所要分出的方塊，必須能同時整除1680m和640m，所以邊長是1680和640的公約數(shù)

2）如果要使方塊最大，則邊長應最大，那么方塊邊長應取1680和640的最大公約數(shù)。

解答：

1680和640的公約數(shù)由“2，2，2，2，5”組成。其最大公約數(shù)為：2 × 2 × 2 × 2 × 5 = 80m，因此，方塊最大邊長為80m。

解法2-分而治之

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

1. 最容易處理的情況是，一條邊的長度是另一條邊的整數(shù)倍(此處稱為“基線條件”)。如下圖所示：

如果一邊長25m，另一邊長50m，那么可使用的最大方塊為25m×25m。換言之，可以將這塊地分成兩個這樣的方塊。

2. 你可以從這塊地中劃出兩個640m×640m的方塊，同時余下一小塊地?，F(xiàn)在是頓悟時刻：何不對余下的那一小塊地使用相同的算法呢？

3. 最初要劃分的土地尺寸為1680m×640m，現(xiàn)在要劃分的土地更小，為640m×400m。適用于這小塊地的最大方塊，也是適用于整塊地的最大方塊(見下文解釋)。換言之，你將均勻劃分1680m×640m土地的問題，簡化成了均勻劃分640m×400m土地的問題！

4. 下面再次使用同樣的算法。對于640m×400 m的土地，可從中劃出的最大方塊為400m×400m。

這將余下一塊更小的土地，其尺寸為400m×240m。

5. 你可從這塊土地中劃出最大的方塊，余下一塊更小的土地，其尺寸為240m×160m。

接下來，從這塊土地中劃出最大的方塊，余下一塊更小 的土地。

6. 余下的這塊土地滿足”基線條件“，因為160是80的整數(shù)倍。將這塊土地分成兩個方塊后，將不會余下任何土地！

因此，對于最初的那片土地，適用的最大方塊為80m×80m。

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

(1) 找出簡單的基線條件；

(2) 確定如何縮小問題的規(guī)模，使其符合基線條件。

歐幾里得算法

前面說“適用于這小塊地的最大方塊，也是適用于整塊地的最大方塊”，如果你覺得這一點不好理解，也不用擔心。這確實不好理解，但遺憾的是，要證明這一點，需要的篇幅有點長。如果你想搞明白其中的原因，可參閱歐幾里得算法?？珊箤W院很清楚地闡述了這種算法?？珊箤W院主頁網(wǎng)址為：

https://www.khanacademy.org/

感興趣的朋友可以查閱”the-euclidean-algorithm“。

注：本題的“分而治之”算法，摘自于“圖靈程序設計叢書”《算法圖解》[美] Aditya Bhargava，為了表示對原作者的尊重，谷老師僅作了少量改動。

兩種解法的聯(lián)系：

1）“最大公約數(shù)法”，其公約數(shù)由“2，2，2，2，5”組成，共5個數(shù)。

2）“分而治之”，其拆分過程為，(1680, 640)-->(400, 640)-->(400, 240)-->(160, 240)-->(160, 80)-->(80, 80)，共經(jīng)歷了5次拆分。

都是5，這絕不是巧合！聰明的你，發(fā)現(xiàn)了什么沒？

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

為了解決一個大的問題，可以：

1) 把它分成兩個或多個更小的問題；

2) 分別解決每個小問題；

3) 把各小問題的解答組合起來，即可得到原問題的解答。

小問題通常與原問題相似，可以遞歸地使用“分而治之”策略來解決。

同類拓展：

1.本例的“土地分塊”問題，如果不知道土地大小(長和寬)，卻告訴你最終分成了80m×80的小方塊，而且經(jīng)過了5次分割過程，能求出土地的大小嗎？如果不能，請問還需要什么條件？

2.隨便想一個1-100的數(shù)字，你的目標是猜到這個數(shù)字。你每次猜測后，我都只會告訴你三種結(jié)果：比猜的數(shù)大、比猜的數(shù)小、兩者相同。請用兩種不同的方法來猜數(shù)。如果要求最小的猜測次數(shù)呢？

李白：行路難，行路難，多歧路，今安在？長風破浪會有時，直掛云帆濟滄海。