用 Python 在遞迴中計算兩個數的 GCD 的程式

假設我們有兩個數字 a 和 b。我們必須以遞迴的方式找到這兩個數的 GCD。為了得到 GCD，我們將使用歐幾里得演算法。

因此，如果輸入是 a = 25 b = 45，則輸出將是 5

為了解決這個問題，我們將遵循以下步驟

• 定義一個函式 gcd()。這將使用 a、b
• 如果 a 等於 b，則
  • 返回 a
• 否則當 a < b 時，則
  • 返回 gcd(b, a)
• 否則，
  • 返回 gcd(b, a - b)

示例

讓我們看看以下實現，以便更好地理解

def gcd(a, b):
   if a == b:
      return a
   elif a < b:
      return gcd(b, a)
   else:
      return gcd(b, a - b)

a = 25
b = 45
print(gcd(a, b))

輸入

25, 45

輸出

5

Arnab Chakraborty

更新於： 2021 年 10 月 12 日

7K+ 瀏覽量

開始您的職業生涯

完成課程獲取認證

開始學習