最大公约数——辗转相除法

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数，这是一个递归过程。

辗转相除法更像辗转相减法，因为辗转一次可能要减好几次，就变成了除法（取余操作）。

执行过程

假设要求自然数a、b的最大公约数，商依次为q₀, q₁, ..., q_n, 余数依次为r₁, r₂, ..., r_n，则执行过程如下：

a = q₀ * b + r₀;

b = q₁ * r₀ + r₁;

r₀ = q₂ * r₁ + r₂;

r₁ = q3 * r₂ + r₃;

...

r_n-3 = q_n-1 * r_n-2 + r_n-1;

r_n-2 = q_n * r_n-1 + r_n;

如果r_n = 0; 则r_n-1即为a、b的最大公约数。

证明

辗转相除法的正确性可以通过两步来证明。首先，算法的最终结果r_n?1同时整除a和b。因为它是一个公约数，所以必然小于或者等于最大公约数g。然后，任何a和b的公约数都能整除r_n?1。所以g一定小于或等于r_n?1。两个不等式只在r_n?1 = g是同时成立。具体证明如下：

1、证明r_n-1是a和b的一个公约数，即r_n-1能够a和b。

　　因为r_n-2 = q_n * r_n-1 + r_n、r_n = 0，所以

　　　　r_n-2 = q_n * r_n-1;

　　因为r_n?1能够整除r_n?2，所以也能够整除r_n-3:

　　　　r_n-3 = q_n-1 * r_n-2 + r_n-1 = q_n-1 * (q_n * r_n-1) + r_n-1 = (q_n-1 * q_n  + 1) * r_n-1;

　　同理可证r_n?1可以整除所有之前步骤的余数，包括a和b，即r_n?1是a和b的一个公约数，r_n?1 ≤ g。

2、证明任何整除a和b的自然数g（也就是a和b的公约数）都能整除r_n-1:

　　根据定义，a和b可以写成g的倍数：a = mg、b = ng，其中m和n是自然数。

　　因为r₀ = a ? q₀ * b = mg ? q₀ * ng = (m ? q₀ * n)g，所以g整除r0。

　　同理可证g整除每个余数r₁, r₂, …, r_n-1。

　　综上所述，g = GCD(a, b) = GCD(b, r₀) = GCD(r₀, r₁) = … = GCD(r_n?2, r_n?1) = r_n?1。

C语言实现

int function(int a, int b) {
    if(a == 0)
        return b;
    if(b == 0)
        return a;
    return function(b, a % b);
}

实际上，最大公约数对浮点数也是适用的：

#define feq(a, b) (fabs(a - b) < 1E-4)
double fgcd(double a, double b){
     if (feq(a, 0))
         return b;
     if (feq(b, 0))
         return a;
     return fgcd(b, fmod(a, b));
}

最大公约数——辗转相除法,布布扣,bubuko.com

最大公约数——辗转相除法

原文：http://www.cnblogs.com/redhead/p/3660228.html