解法一：辗转相除法（欧几里德算法）Euclidean algorithm
定理：两个正整数 a、b (a>b)，它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数
思路：使用递归算法，结束条件：两个数可以相除，或者某一个数减少到 1
测试用例：
- 输入有 0，输入非整数
- 普通值（交换位置各尝试一次）
- 输入的值相邻（较大值 10000， 9999）
# 辗转相除法（欧几里德算法）Euclidean algorithm # 定理：两个正整数 a、b(a>b)，它们的最大公约数等于 a除以 b 的余数 c 和 b 之间的最大公约数 # 使用递归解决 def euclidean_algo(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 == 0: # 结束条件：两个数可以相除，或者某一个数减少到 1 return small return euclidean_algo(small, big%small) if __name__ == "__main__": assert euclidean_algo(10, 0) == None # 测试包含 0 的 assert euclidean_algo(10, 25) == 5 # 正常数值 assert euclidean_algo(25, 10) == 5 # 交换一下位置 assert euclidean_algo(3, 2) == 1 # 较大数值 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 必然是偶数，又可以进行移位运算
测试用例（增加）
- 都是偶数
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)))，只有在两个数都比较小的时候，可以看出计算的优势。
分享到:
