def GCD(a, b):
# 基本情況：當 b 為 0 時，返回 a
if b == 0:
return a
else:
# 遞迴調用：GCD(b, a % b)
return GCD(b, a % b)
測試範例
num1 = 48
num2 = 18
result = GCD(num1, num2)
print(f"{num1} 和 {num2} 的最大公因數是: {result}")
解釋
-
基本情況：
- 當 b=0b = 0b=0 時，直接返回 aaa 作為最大公因數。
-
遞迴調用：
- 使用 return GCD(b, a % b) 進行遞迴調用，這一步相當於將問題規模縮小，逐步逼近基本情況。
測試範例
- a=48a = 48a=48
- b=18b = 18b=18
- 步驟：
- GCD(48,18)GCD(48, 18)GCD(48,18) 進行遞迴調用 GCD(18,48%18)=GCD(18,12)GCD(18, 48 \% 18) = GCD(18, 12)GCD(18,48%18)=GCD(18,12)
- GCD(18,12)GCD(18, 12)GCD(18,12) 進行遞迴調用 GCD(12,18%12)=GCD(12,6)GCD(12, 18 \% 12) = GCD(12, 6)GCD(12,18%12)=GCD(12,6)
- GCD(12,6)GCD(12, 6)GCD(12,6) 進行遞迴調用 GCD(6,12%6)=GCD(6,0)GCD(6, 12 \% 6) = GCD(6, 0)GCD(6,12%6)=GCD(6,0)
- 因為 b=0b = 0b=0，返回 666
因此，48 和 18 的最大公因數是 6。
阿摩線上測驗
登入