伪·从零开始学算法-2.2 求最大公约数

为了这篇文章我专门做了个视频。

虽然只是演示用的……

简介

两个或多个正整数数的公约数是,对于这些数,存在一个正整数,可以整除它们。公约数可能有若干个,而其中最大的就是最大公约数。

也就是:

A: card(A) ≥ 2, (∀ a ∈ A, a ∈N*) ;

B = ;

k = max;

k即为A中各数的最大公约数。

从人类的做法推导

我们计算最大公约数的时候,通常用短除法来计算。具体的方法是:同时让这些数除以一个比较小的公约数,得到的结果再这样操作,直到找不到大于等于2的公约数;将除数相乘即得到最大公约数。比如:

短除法计算最大公约数

通过经验,人是可以快速找到一些较小的公约数,写在除数上的。但是,计算机却无法这么做。但是计算机可以从1开始,判断某个整数是否能整除所有给定的数。如果能,即为公约数,记下来;否则,除数加1,再试。

但是,算法是有限的,到什么时候停止呢?根据常理,一组数的最大公约数一定不大于这组数的最小的数。因此,如果算到这组数的最小值的话,就不用再算下去了。

由此可以推导出流程图如下:

计算最大公约数流程图(1)

鉴于1能够整除所有正整数,我们可以让循环从2开始。这样,流程图如下:

计算最大公约数流程图(2)

如果我们把“∀ a ∈ A, a mod i = 0?”的判断展开,则如下:

计算最大公约数流程图(3)

已经非常复杂了。

实际应用中,我们更多的是计算两个数之间的最大公约数。这样,流程图可以简化如下:

计算两个数的最大公约数流程图

不过这个方法在计算的时候,如果是小的数字还可以,遇到大数的时候,计算时间就非常长。

这时候还可以使用更加简便的算法。

辗转相除法

辗转相除法又称欧几里得算法,首次出现于《几何原本》中,被人们认为是史上第一个算法。它可以用于求两数的最大公约数。

首先,用两数中较大数除以较小数,求得数;再用较小数和余数按上述操作进行相除;直到余数为0。此时的除数即为最大公约数。

流程图表示如下:

辗转相除法(1)

考虑到许多编程语言使用的是DO-WHILE型的直到型循环结构,还有一些语言没有直到型循环结构,流程图改写为如下:

辗转相除法(2)

其中当型的流程图在循环结构前有一个定义变量r的操作。这里的r的赋值只要不等于0就可以了。

此外,还有递归型的流程图:

辗转相除法(递归)

更相减损术

更相减损术是《九章算术》中给出的求两个数的最大公约数的方法:

可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

算法描述为:

第一步:任意给两个正整数;判断它们是否都是偶数,如果是,用2约简,并记下次数;否则,进行下一步;

第二步:以较大的数减去较小的数,把差与较小的数相比,并用大数减小数。继续此操作,使所得数相等为止。记下这个数。

第三步:如果第一步有约简,第二步所得的数乘上2乘约简次数就是最大公约数。否则,第二步所得的数就是最大公约数。

(人教版的教科书上对这个的解释有问题……粗体字表示增加的内容)

流程图如下:

更相减损术(1)

标准化后如下:

更相减损术(2)

看起来非常麻烦。

不过,还有一个简单的算法:

更相减损术(3)

实际上这和辗转相除法很相似了。在维基百科上,它们是在一个词条内的,而且上面的算法被称为欧几里得算法的减法形式。

三者的比较

在现代,算法之间的比较主要体现在效率上。在下面,我将使用IPython的工具来测试它们的运行速度(使用语言为Python,在安装Windows 10 专业版和Python 3.6的华硕N551ZU上进行,结果仅供参考)。

各种算法的执行时间测试

从这里就能看出来,虽然现在电脑硬件水平的发展相当成熟,但是各个算法之间的运行速度还是有比较明显的差别的。

之前的那个直接求最大公约数的方法,运算速度相对于其他的算法都比较慢,尤其是在两个数都非常大的情况下。相比之下,其他算法的运算速度和它的运算速度相差悬殊。

另外,更相减损术在两数相差悬殊的时候,运算速度也会减慢。

从这里我们可以看出优化算法的意义——可以显著减少运行时间,提高效率,节能。这个测试还是在比较好的机器上进行的,如果是在简单的单片机上,差别就更加明显了。

参考资料

如果大家想了解关于这两个算法的更多内容,也可以看看。

辗转相除法 - 维基百科,自由的百科全书

普通高中课程标准实验教科书(必修) 数学(A版) 必修3. 人民教育出版社

辗转相除法、更相减损法、Stein算法 - CSDN博客

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180313A1QIGJ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券