辗转相除法的减损法与减损定理的最大公约数思路与解法

方案一：欧几里得算法（Euclidean algorithm）

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

思路：使用递归算法，结束条件：两个数可以整除用c语言求三个数的最大公约数，或者一个数可以减为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)))

解决方案2：更减法

定理：两个正整数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))

方案3：将减法与减法和移位运算结合（移位运算性能好）（递归函数下面简称gcd）

测试用例（增加）

所有偶数

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)
 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)))用c语言求三个数的最大公约数，只有当两个数比较小时，才能看出计算的优势。