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+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告