从数组中计算最大公约数的有效方法 - Swift

Question

我创建了以下函数，它以两个 Integers 作为参数并计算它们的 GCD：

func getGCD(_ num1: Int, _ num2: Int) -> Int {

    let remainder = num1 % num2
    if remainder != 0 {
        return gcd(num2, remainder)
    } else {
        return num2
    }
}

注意： 我想使用 Recursivity。

问题一：有没有办法让这个功能更高效？

问题 2：如何将此函数用于 [Int] 类型的 Array？

Answer 1

首先，您的函数不适用于负数 Integers，因此使它成为 "more efficient" 的一种方法是使用 abs()，以获得号码：

func gcd(_ a: Int, _ b: Int) -> Int {
    let remainder = abs(a) % abs(b)
    if remainder != 0 {
        return gcd(abs(b), remainder)
    } else {
        return abs(b)
    }
}

第二个问题 - 使用数组：

var numbers = [5,10]
var index = 0
var result = 0
if numbers.isEmpty{result=0}
else if numbers.count == 1{result = numbers[0]}
else{
    while index <= numbers.count-1{
        if index==0{
            result = gcd(numbers[index], numbers[index + 1])
            index+=2
        }
        else {
            result = gcd(result,numbers[index])
            index+=1
        }
    }

}
print(result) // prints 5

Answer 2

一旦你有一个函数 gcd（或 getGCD）处理两个整数，下面的函数将适用于整数数组 arr：

let result = arr.reduce(0) {gcd([=10=],)}

从数组中计算最大公约数的有效方法 - Swift

Efficient way of computing the Greatest Common Divisor from an Array - Swift

arrays

greatest-common-divisor

swift