layout: posttitle: 数据结构与算法—求取两个整数的最大公约数
date: 2019-10-15
tag: 数据结构与算法

求取两个整数的最大公约数

  • 解法一：辗转相除法（欧几里德算法）Euclidean algorithm

定理：两个正整数 a、b(a>b)，它们的最大公约数等于 a除以 b 的余数 c 和 b 之间的最大公约数

思路：使用递归算法，结束条件：两个数可以相除，或者某一个数减少到 1

测试用例：

  1. 输入有 0，输入非整数
  2. 普通值（交换位置各尝试一次）
  3. 输入的值相邻（较大值 10000， 9999）
  1. # 辗转相除法（欧几里德算法）Euclidean algorithm
  2. # 定理：两个正整数 a、b(a>b)，它们的最大公约数等于 a除以 b 的余数 c 和 b 之间的最大公约数
  3. # 使用递归解决
  4. def euclidean_algo(num1: int, num2: int) -> int:
  5.     assert isinstance(num1, int)
  6.     assert isinstance(num2, int)
  7.     big, small = (num1, num2) if num1 > num2 else (num2, num1)
  8.     # 边界条件
  9.     if small == 0:
  10.         return None
  12.     if big%small == 0: #  结束条件：两个数可以相除，或者某一个数减少到 1
  13.         return small
  15.     return euclidean_algo(small, big%small)
  18. if __name__ == "__main__":
  19.     assert euclidean_algo(10, 0) == None # 测试包含 0 的
  20.     assert euclidean_algo(10, 25) == 5 # 正常数值
  21.     assert euclidean_algo(25, 10) == 5 # 交换一下位置
  22.     assert euclidean_algo(3, 2) == 1 # 较大数值
  23.     euclidean_algo(1.0, 2.0) # 输入非整数，运行出现 AssertionError 代表没错

辗转相除法存在 a%b 取模的操作，当两个整数较大时，性能会比较差

时间复杂度为：近似 O(log(max(a, b)))

  • 解法二：更相减损法

定理：两个正整数 a、b(a>b)，它们的最大公约数等于 a-b 的差值 c 和较小数 b 的最大公约数

def get_greatest_commin_divisor(num1: int, num2: int) -> int:
    assert isinstance(num1, int)
    assert isinstance(num2, int)
    big, small = (num1, num2) if num1 > num2 else (num2, num1)
    if small == 0:
        return None

    if big == small: # 两个数相同是终止条件
        return small
    return get_greatest_commin_divisor(small, big-small)


if __name__ == "__main__":
    assert get_greatest_commin_divisor(10, 0) == None # 测试包含 0 的
    assert get_greatest_commin_divisor(10, 25) == 5 # 正常数值
    assert get_greatest_commin_divisor(25, 10) == 5 # 交换一下位置
    assert get_greatest_commin_divisor(3, 2) == 1 # 较大数值
#     get_greatest_commin_divisor(1.0, 2.0) # 输入非整数

更相减损法：不稳定，当两个整数相差较大时，如 10000 和 1 需要递归 9999 次

最坏时间复杂度：O(max(a, b))

  • 解法三：辗转相除法结合更相减损法，并结合移位操作(移位操作性能好)（以下递归函数简称 gcd ）

    • 若 a、b 均为偶数，gcd(a, b) = 2×gcd(a/2, b/2) = 2×gcd(a>>1, b>>1)
    • 若 a 为偶数，b 为奇数 gcd(a, b) = gcd(a/2, b) = gcd(a>>1, b)
    • a 为奇数，b 为偶数 gcd(a, b) = gcd(a, b/2) = gcd(a, b>>1)
    • a、b 均为奇数，二者利用更相向损法运算一次，gcd(a, b) = gcd(a, a-b) 此时 a-b 必然是偶数，又可以进行移位运算

测试用例（增加）

  1. 都是偶数
def get_greatest_commin_divisor(num1: int, num2: int) -> int:
    # 边界条件
    assert isinstance(num1, int)
    assert isinstance(num2, int)
    big, small = (num1, num2) if num1 > num2 else (num2, num1)
    if small == 0: 
        return None

    if big == small: # 两个数相同是终止条件
        return small

    if big&1 ==0 and small&1 == 0: # 如果两个都是偶数
        return get_greatest_commin_divisor(big>>1, small>>1)<<1 # 注意，这里有个左移位（即乘 2 倍）

    elif big&1 !=0 and small&1 == 0: # 若 big 为奇数， small 为偶数
        return get_greatest_commin_divisor(big, small>>1)

    elif big&1 ==0 and small&1 != 0: # 若 big 为偶数， small 为奇数
        return get_greatest_commin_divisor(big>>1, small)

    elif big&1 !=0 and small&1 != 0: # 若 big, small 都为奇数
        return get_greatest_commin_divisor(big-small, small)


if __name__ == "__main__":
    assert get_greatest_commin_divisor(10, 0) == None # 测试包含 0 的
    assert get_greatest_commin_divisor(10, 25) == 5 # 正常数值
    assert get_greatest_commin_divisor(25, 10) == 5 # 交换一下位置
    assert get_greatest_commin_divisor(36, 10) == 2
    assert get_greatest_commin_divisor(3, 2) == 1 # 较大数值
#     get_greatest_commin_divisor(1.0, 2.0) #

避免取模运算，而且算法性能稳定，时间复杂度为 O(log(max(a, b)))，只有在两个数都比较小的时候，可以看出计算的优势。