使用遞迴查詢兩個給定數字的最大公約數 (GCD) 的 Swift 程式

---

本教程將討論如何編寫 Swift 程式，使用遞迴查詢兩個給定數字的最大公約數。

兩個數字的最大公約數 (GCD) 也稱為最大公因數 (HCF)，是指這兩個給定正數的公因數中最大的正數。兩個數的最大公約數不能為負數或零，兩個數的最小最大公約數始終為 1。例如，假設我們有兩個數字：16 和 24

所以 16 的因數 = 2x2x2x2

24 的因數 = 2x2x2x3

所以，GCD(16, 24) = 2x2x2 = 8

以下是相同的演示 -

輸入

假設我們的給定輸入是 -

Num1 = 16
Num2 = 24

輸出

期望的輸出是 -

GCD = 8

歐幾里得演算法

為了計算兩個數的最大公約數，我們首先計算它們的因數，然後取它們共有的最大數來計算最大公約數。這種方法對於小數非常有效，但是如果數字很大，這種方法就會變得很困難。因此，為了找到小數或大數的最大公約數，我們使用歐幾里得演算法。在這個演算法中，我們除以兩個數字，直到餘數變為 0。

GCD(x, y) = GCD(y, x%y)

這裡，x%y 用於查詢餘數。

為了計算兩個數字的最大公約數，我們可以使用遞迴方法。遞迴方法是一種函式呼叫自身以完成指定任務的方法。

演算法

以下是演算法 -

步驟 1 - 建立一個遞迴函式。

步驟 2 - 宣告一個名為“output”的變數來儲存餘數。

let output: Int = n1 % n2

步驟 3 - 檢查 output != 0。如果條件為真，則遞迴呼叫 findRecursiveGCD() 函式。否則返回 n2，因為餘數為零，這意味著我們找到了兩個數的最大公約數。

步驟 4 - 呼叫函式並將結果儲存到變數中。

步驟 5 - 列印輸出。

示例 1

以下程式演示瞭如何使用遞迴計算兩個給定數字的最大公約數。

import Swift
import Foundation
// Recursive function to find gcd of two numbers
func findRecursiveGCD(n1: Int, n2: Int) -> Int {
   let output: Int = n1 % n2
   // Base condition
   if output != 0{
      // Calling function itself
      return findRecursiveGCD(n1: n2, n2: output)
   } else{
      return n2
   }
}
// Calling Function
var result = findRecursiveGCD(n1:27, n2:21)
print("GCD of 27 and 21 is ", result)

輸出

GCD of 27 and 21 is  3

在上面的程式碼中，我們建立了一個名為 findRecursiveGCD 的遞迴函式來計算兩個數的最大公約數。它使用歐幾里得演算法。在這個函式中，我們透過遞迴呼叫函式來找到兩個數的餘數。所以 findRecursiveGCD() 的工作原理是 -

findRecursiveGCD(27, 21) -

Output = 27 % 21 = 6

if 6 != 0{
   return findRecursiveGCD(n1: 21, n2: 6)
} else{
   return n2
}

Output = 21 % 6 = 3

if 3 != 0{
   return findRecursiveGCD(n1: 6, n2: 3)
} else{
   return n2
}

Output = 6 % 3 = 0

if 0 != 0{
   return findRecursiveGCD(n1: 6, n2: 3)
} else{
   return n2 = 3
}

所以 27 和 21 的最大公約數是 3。