算法：辗转相除法（欧几里得算法）
- GCD递归定理
- 辗转相除法算法概述
- 辗转相除法伪代码
- 辗转相除法代码实现
对于两个数的最大公约数的求解，在我们的笔算过程中，通常是使用一个短除法，本质上其实也就是进行一个质因数分解的过程，但对于一个较大的数来说，将其进行质因数分解是一件非常耗时的过程，这显然不是一个好的做法，因此基于数论基础，我们有了辗转相除法，也叫做欧几里得算法。
GCD递归定理
在叙述该算法之前，先了解辗转相除法的实现前提也就是GCD递归定理：
对任意非负整数
和任意正整数
,
辗转相除法算法概述
基于上面的GCD递归定理，我们便可以知道可以采用递归的方式，对两个整数的最大公约数进行相对较为高效的计算。
算法描述：
- 求两个数的余数；
- 若余数为0，则较小数即为最大公约数；否则执行3；
- 用较小的数替换较大的数，用余数替换较小的数；
- 返回1.
算法示例
辗转相除法伪代码表示
下面我们采用递归方式实现辗转相除法。
(以下引用自《算法导论》)
GCD(a, b)
if b == 0
return a
else
return GCD(b, a mod b)
辗转相除法实现
C
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
pascal
function gcd(a, b : integer) :integer;
begin
if b = 0 then
gcd := a
else
gcd := gcd(b, a mod b);
参考资料
- 《算法导论》（第三版）
- 《Free Pascal 语言与基础算法》
本文首发于个人博客算法 - 辗转相除法 | 不存在的貓， 转载请注明出处
