数据结构与算法-求取两个整数的最大公约数
求取两个整数的最大公约数
解法一：辗转相除法（欧几里德算法）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)))，只有在两个数都比较小的时候，可能看出计算的优势。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录