算法-辗转相除法（欧几里得算法）

发表于 更新于 分类于

算法：辗转相除法（欧几里得算法）

  • GCD递归定理

  • 辗转相除法算法概述

  • 辗转相除法伪代码

  • 辗转相除法代码实现

对于两个数的最大公约数的求解，在我们的笔算过程中，通常是使用一个短除法，本质上其实也就是进行一个质因数分解的过程，但对于一个较大的数来说，将其进行质因数分解是一件非常耗时的过程，这显然不是一个好的做法，因此基于数论基础，我们有了辗转相除法，也叫做欧几里得算法。

该算法的一个更容易理解的几何解释是，假设有一块 \(a*b\) 的地面需要铺设正方形砖块，问应该如何取砖块的长度。在此选取过程中，我们每次取该矩形剩余部分的短边作为砖块边长，铺设至无法再铺设为止，如此循环，当某砖块长度恰好能够铺满地面不留余地，则该长度为所取长度，也就是 \(a\) 和 \(b\) 的最大公约数1。

GCD递归定理

在叙述该算法之前，先了解辗转相除法的实现前提也就是GCD递归定理：

对任意非负整数\(a\)和任意正整数\(b\), \[ gcd(a,b) = gcd(b,a \quad mod \quad b) \]

辗转相除法算法概述

基于上面的GCD递归定理，我们便可以知道可以采用递归的方式，对两个整数的最大公约数进行相对较为高效的计算。

算法描述：

  1. 求两个数的余数；
  2. 若余数为0，则较小数即为最大公约数；否则执行3；
  3. 用较小的数替换较大的数，用余数替换较小的数；
  4. 返回1。

算法示例

\[ gcd(30,21) = gcd(21,9) = gcd(9,3) = gcd(3,0) = 3 \]

辗转相除法伪代码表示

下面我们采用递归方式实现辗转相除法2。

GCD(a, b)

1
2
3
4
if b == 0
  return a
else
  return GCD(b, a mod b)

辗转相除法实现

C

1
2
3
4
5
6
7
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

pascal

1
2
3
4
5
6
function gcd(a, b : integer) :integer;
begin
    if b = 0 then
        gcd := a
    else
        gcd := gcd(b, a mod b);

参考资料

  • 《Free Pascal 语言与基础算法》

  1. The Secret Rules of Modern Living: Algorithms (2015)↩︎

  2. 《算法导论》（第三版）↩︎