JAVA 牛牛

欧几里得算法(辗转相除法)

  • Apr 29, 2020
  • 0 views

1. 欧几里得算法(辗转相除法)

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。

欧几里得法(辗转相除法) 通过举例说明1

举例： 105和85的最大公约数

  1. 第一轮计回算 105÷85=1…20
  2. 第二轮计算 85÷20=4…5
  3. 第三轮计算 20÷5=4
  4. 第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 5

欧几里得法(辗转相除法) 通过举例说明2

举例： 21和17的最大公约数

  1. 第一轮计回算 21÷17=1…4
  2. 第二轮计算 17÷4=4…1
  3. 第三轮计算 4÷1=4
  4. 第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 1
  • 基于这条定理：

首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数……以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。

贴代码：

def first_way(a, b):
    """
    第一种方法：欧几里得算法----辗转相除法
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    # 如果最终余数为0 公约数就计算出来了
    while(b!=0):
        temp = a % b
        a = b
        b = temp
    return a

2. 穷举法(一个一个除)

这个比较好理解。因为a,b两个数的最大公因数肯定小于等于相对更小的那个数，所以从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。代码如下：

def second_way(a, b):
    """
    第二种方法：一个一个除
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    # 保证a>b
    if(a<b):
        a,b = b,a
    for i in range(1,b+1):
        if (a%i==0) and (b%i==0):
            value = i;
    return value

3. stein算法

看下面这两个结论

  • gcd(a, a) = a， 也就是一个数和他自己的公约数是其自身。
  • gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。
def third_way(a,b):
    """
    第三种方法思想：stein算法
        gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
        gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
        当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数
    和一个奇数的最大公约数时，可以先将偶数除以2。
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    #保证b比a小
    if a < b:
        a, b = b, a

    if (0 == b):
        return a
    # a,b都是偶数 除2右移一位即可
    if a % 2 == 0 and b % 2 == 0:
        return 2 * third_way(a >> 1, b >> 1)
    # a是偶数
    if a % 2 == 0:
        return third_way(a >> 1, b)
    # b是偶数
    if b % 2 == 0:
        return third_way(a, b >> 1)
    # 都是奇数
    return third_way((a + b) >> 1, (a - b) >> 1)

求出a,b的最大公约数后，利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数的 最小公倍数：

# 求两个数的最小公倍数
def lcm(a,b):
    return a * b / third_way(a, b)

4. 三个数的最大公约数和最小公倍数

计算三个数的最大公约数时，我是利用之前写好的计算2个数的最大公约数的方法，先算出a,b的公约数，再用a,b的公约数与c再代入方法，此时返回的值就是三个数的最大公约数了。

同样，在计算三个数的最小公倍数时，多次嵌套，先求出两个数的最小公倍数，再求其与第三个数的最小公倍数。

def three_num(a,b,c):
    """
    求三个数的最大公约数
    :param a: 第一个数
    :param b: 第二个数
    :param c: 第三个数
    :return: 这三个数的最大公约数
    """
    # 多次嵌套，返回3个数的最大公约数
    return first_way(first_way(a,b),c)
Search