解法一：輾轉相除法（歐幾里德算法）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)))，只有在兩個數都比較小的時候，可以看出計算的優勢。
分享到:
