欧几里得算法伪代码转换为Swift？

Question

我一直在研究减少 Swift 中分数的函数，并遇到了欧几里德算法来寻找最大公因数 (http://en.wikipedia.org/wiki/Euclidean_algorithm)

我将伪代码转换为 swift，但我很困惑如果它返回 a 我认为应该是分数的分子。对此的任何帮助将不胜感激。谢谢！

伪代码：

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
     return a

Swift:

var a = 2
var b = 4

func gcd(a: Int, b: Int) -> Int {
    var t = 0
    while b != 0 {
        t = b
        let b = a % b
        let a = t
    }
    return a
}

println("\(a)/\(b)")

控制台输出： 2/4

Answer 1

当你这样做时

let b = a % b

您正在创建另一个只读变量 b，它与外部作用域中的变量 b 无关。您需要删除循环内的两个 lets，并通过使用 var 声明它们来使参数可修改，如下所示：

func gcd(var a: Int, var b: Int) -> Int {
    var t = 0
    while b != 0 {
        t = b
        b = a % b
        a = t
    }
    return a
}

您可以这样调用您的函数：

let a = 111
let b = 259
println("a=\(a), b=\(b), gcd=\(gcd(a,b))")

这会打印 a=111, b=259, gcd=37

Answer 2

采用@dasblinkenlight 的回答并通过使用元组进行并行赋值来摆脱t：

Swift 2.1:

func gcd(var a: Int, var _ b: Int) -> Int {
    while b != 0 {
        (a, b) = (b, a % b)
    }
    return a
}

gcd(1001, 39)  // 13

var 参数在 Swift 2.2 中已弃用，将在 Swift 3[=27= 中删除].所以现在有必要在函数中将 a 和 b 声明为 var：

func gcd(a: Int, _ b: Int) -> Int { var (a, b) = (a, b) while b != 0 { (a, b) = (b, a % b) } return a }

Answer 3

可以使用递归方法，在找到 GCD 之前一直调用自身。

func gcd(a: Int, b: Int) -> Int {
    if b == 0 {
        return a
    }

    let remainder: Int = a % b

    return gcd(b, b: remainder)
}

并像这样使用

let gcdOfSomeNums = gcd(28851538, b: 1183019)
//gcdOfSomeNums is 17657

Answer 4

Swift Christopher Larsen 给出的答案的第 3 个版本

func gcd(a: Int, b: Int) -> Int {
  if b == 0 { return a }
  return gcd(a: b, b: a % b)
}

欧几里得算法伪代码转换为Swift？

Euclidean algorithm pseudocode conversion to Swift?

ios

swift

pseudocode