Swift程式：求兩個數的最大公約數

本教程將討論如何編寫一個Swift程式來求兩個數的最大公約數。

最大公約數 (GCD) 也稱為最大公因數或最高公因子 (HCF)。兩個正數的最大公約數定義為這兩個正數的公因數中最大的正數。GCD的值不能為0或負數。兩個數的GCD的最小值始終為1。例如，我們有兩個數24和30。

24的因數 = 2 x 2 x 2 x 3

30的因數 = 2 x 3 x 5

因此，GCD(24, 30) = 2 x 3 = 6，因為2 x 3是公因數。

以下是相同的演示 -

輸入

假設我們的輸入是

Number 1 = 24
Number 2 = 30

輸出

期望的輸出是

GCD = 6

歐幾里得演算法

通常，要找到兩個數的最大公約數，我們需要首先找到它們的因數，然後取它們的最大公因數來計算GCD。這種方法只對較小的數字有效，但如果數字很大，這種方法就很難找到GCD。因此，為了克服這個困難，我們使用歐幾里得演算法。

在這個歐幾里得演算法中，我們除以兩個數，直到它們的餘數為0。

GCD(m, n) = GCD(n, m%n)

這裡，m%n用於查詢m和n的餘數。

在Swift中，我們可以使用以下任何一種方法來計算兩個數的最大公約數

方法1 - 迭代法

我們可以使用while迴圈來計算GCD。

演算法

以下是演算法 -

  • 步驟1 - 建立一個帶有兩個引數的函式。

  • 步驟2 - 宣告一個值為0的變數，即x = 0。

  • 步驟3 - 宣告兩個名為y和z的int型別變數。這裡，y使用max()函式儲存num1和num2中的最大數，而z使用min()函式儲存num1和num2中的最小數。

var y: Int = max(num1, num2)
var z: Int = min(num1, num2)

這裡的max()和min()確保最大數應該被最小數整除。

  • 步驟4 - 執行while迴圈，直到z != 0。

  • 步驟5 - 使用%運算子查詢餘數。

  • 步驟6 - 返回GCD

  • 步驟7 - 使用兩個引數呼叫findGCD(num1:78, num2:46)函式，並將輸出儲存在result變數中。

  • 步驟8 - 列印輸出。

示例

以下程式演示瞭如何使用迭代方法求兩個數的最大公約數。

import Swift
import Foundation

// Function to find gcd of two numbers
func findGCD(num1: Int, num2: Int) -> Int {
   var x = 0

   // Finding maximum number
   var y: Int = max(num1, num2)

   // Finding minimum number
   var z: Int = min(num1, num2)

   while z != 0 {
      x = y
      y = z
      z = x % y
   }
   return y
}

// Calling Function
var result = findGCD(num1:78, num2:46)
print("GCD of 78 and 46 is ", result)

輸出

GCD of 78 and 46 is 2

在上面的程式碼中，我們建立了一個名為findGCD()的函式來查詢兩個數的最大公約數。此函式遵循歐幾里得演算法。因此，首先找到給定兩個數字中最大和最小的數字，以便最大數字可以被最小數字整除。然後找到它們的餘數，直到餘數的值為0。現在呼叫findGCD()函式，並將78和46作為引數傳遞給它。因此，findGCD()函式的工作原理如下：

findGCD(78, 46): 
x = 0
y = max(78, 46) = 78
z = min(78, 46) = 46

while 46 != 0 {
   x = 78
   y = 46
   z = x % y => 78 %46 = 32
}
while 32 != 0 {
   x = 78
   y = 32
   z = x % y => 78 %32 = 14
}
while 14 != 0 {
   x = 32
   y = 14
   z = x % y => 32 % 14 = 4
}
while 4 != 0 {
   x = 14
   y = 4
   z = x % y => 14 % 4 = 2
}
while 2 != 0 {
   x = 4
   y = 2
   z = x % y => 4 % 2 = 0
}
return y => 2

因此，顯示輸出78和46的最大公約數是2。

方法2 - 遞迴法

我們可以使用遞迴方法計算GCD。

演算法

以下是演算法 -

  • 步驟1 - 建立一個帶有兩個引數的函式。

  • 步驟2 - 宣告一個名為res的int型別變數來儲存餘數。

let res: Int = num1 % num2

  • 步驟3 - 檢查res != 0。如果條件為真，則遞迴呼叫findGCD()函式。否則返回num2，因為餘數為零，這意味著我們找到了兩個數的GCD。

  • 步驟4 - 呼叫函式並將結果儲存在“result”變數中。

  • 步驟5 - 列印輸出。

示例

以下程式演示瞭如何使用遞迴方法求兩個數的最大公約數。

import Swift
import Foundation

// Function to find gcd of two numbers
func findGCD(num1: Int, num2: Int) -> Int {

   let res: Int = num1 % num2
   if res != 0{
      return findGCD(num1: num2, num2: res)
   } else{
      return num2
   }
}

// Calling Function
var result = findGCD(num1:12, num2:8)
print("GCD of 12 and 8 is ", result)

輸出

GCD of 12 and 8 is 4

在上面的程式碼中，我們建立了一個名為findGCD()的函式來查詢兩個數的最大公約數。此函式也遵循歐幾里得演算法。在此函式中，我們透過自呼叫函式來查詢兩個數的餘數。現在呼叫findGCD()函式，並將12和8作為引數傳遞給它。因此，findGCD()函式的工作原理如下：

findGCD(12, 8):
res = num1 % num2 = 12 % 8 = 4
if 4 != 0{
   return findGCD(num1: 8, num2: 4)
} else{
   return num2
}
res = 8 % 4 = 0
if 0 != 0{
	return findGCD(num1: 8, num2: 4)
} else{
   return num2 => 4
}

因此，顯示輸出12和8的最大公約數是4。

更新於：2022年8月18日

1K+ 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告