数据结构与算法-求取两个整数的最大公约数

# 辗转相除法（欧几里德算法）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 代表没错

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) # 输入非整数   

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) #