Swift 3中的Fibonacci数生成器

Question

下面的问答涵盖了几种在Swift中生成Fibonacci数的方法，但它相当过时(Swift 1.2?)：

使用泛函Swift求Fibonacci项的和

问题：

我们如何使用现代Swift (Swift >= 3)巧妙地生成斐波纳契数？最好是避免显式递归的方法。

Answer 1

Swift 3.0的另一种选择是使用helper函数

public func sequence(first: T, while condition: @escaping (T)-> Bool, next: @escaping (T) -> T) -> UnfoldSequence {
    let nextState = { (state: inout T) -> T? in
        // Return `nil` if condition is no longer satisfied:
        guard condition(state) else { return nil }
        // Update current value _after_ returning from this call:
        defer { state = next(state) }
        // Return current value:
        return state
    }
    return sequence(state: first, next: nextState)
}

来自

带有动态范围的swift中的Express for循环

for f in sequence(first: (0, 1), while: { $1 <= 50 }, next: { ($1, $0 + $1)}) {
    print(f.1)
}
// 1 1 2 3 5 8 13 21 34

请注意，为了在结果序列中包含零，替换初始值就足够了

由

for f in sequence(first: (1, 0), while: { $1 <= 50 }, next: { ($1, $0 + $1)}) {
    print(f.1)
}
// 0 1 1 2 3 5 8 13 21 34

这使得“人工”检查成为可能。

if pair.1 == 0 { pair.1 = 1; return 0 }

多余的。潜在的原因是斐波那契数可以推广为负指数(

https://en.wikipedia.org/wiki/Generalizations

_

的

_

斐波那契

_

数字

)：

... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...

Answer 2

使用全局

函数

Swift 3.0

作为另一种选择，我们可以使用一个整洁的全局

函数，在Swift 3.0中实现的一对函数(如演进提案中所述

SE-0094

)。

使用其中的后者，我们可以将斐波那契数序列的先前和当前状态保持为可变的

属性中的

关闭

..。

func fibs(through: Int, includingZero useZero: Bool = false)
    -> UnfoldSequence {
    return sequence(state: useZero ? (1, 0) : (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        guard pair.1 <= through else { return nil }
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        })
}
    // explicit type annotation of inout parameter closure
    // needed due to (current) limitation in Swift's type
    // inference

// alternatively, always start from one: drop useZero 
// conditional at 'state' initialization
func fibs1(through: Int)
    -> UnfoldSequence {
    return sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        guard pair.1 <= through else { return nil }
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        })
}

或者，使用元组hack对其进行压缩(无论如何执行

一个额外的，不必要的时间)

func fibs(through: Int, includingZero useZero: Bool = false) -> UnfoldSequence {
    return sequence(state: useZero ? (1, 0) : (0, 1), next: { 
        ($0.1 <= through ? $0.1 : Optional.none, $0 = ($0.1, $0.0 + $0.1)).0 })
}

func fibs1(through: Int) -> UnfoldSequence {
    return sequence(state: (0, 1), next: { 
        ($0.1 <= through ? $0.1 : Optional.none, $0 = ($0.1, $0.0 + $0.1)).0 })
}

注意，我们显式地使用

返回时返回

不再满足条件。

示例用法：

// fib numbers up through 50, excluding 0
fibs(through: 50).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34

// ... or
fibs1(through: 50).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34

// ... including 0
fibs(through: 50, includingZero: true).forEach { print($0) }
    // 0 1 1 2 3 5 8 13 21 34

// project Euler #2: sum of even fib numbers up to 4000000
print(fibs(through: 4_000_000)
    .reduce(0) { $1 % 2 == 0 ? $0 + $1 : $0 }) // 4 613 732

我们还可以去掉上面的终止条件，以构造一个无限的斐波那契数序列，并与之结合使用

func infFibs() -> UnfoldSequence {
    return sequence(state: (0, 1), next: {
        (pair: inout (Int, Int)) -> Int in (pair.1, pair = (pair.1, pair.0 + pair.1)).0 })
}

// prefix the first 6 fib numbers (excluding 0) from
// the infinite sequence of fib numbers
infFibs().prefix(10).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34 55

Swift 3.1

当Swift 3.1到来时，

用于序列的方法，如进化提案中所述

SE-0045

，将会实现。使用这个附加功能，我们可以修改

方法来避免显式的-

条件序列终止：

func fibs(through: Int, startingFromZero useZero: Bool = false)
    -> AnySequence {
    return sequence(state: useZero ? (1, 0) : (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        }).prefix(while: { $0 <= through })
}

// alternatively, always start from one: drop useZero 
// conditional at 'state' initialization
func fibs1(through: Int) -> AnySequence {
    return sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        }).prefix(while: { $0 <= through })
}

示例应该与上面的Swift 3.0相同。

Answer 3

在Swift 3.1中，这里有一个迭代器，它永远生成Fibonacci数，并从它派生出一个无限序列：

class FibIterator : IteratorProtocol {
    var (a, b) = (0, 1)

    func next() -> Int? {
        (a, b) = (b, a + b)
        return a
    }
}

let fibs = AnySequence{FibIterator()}

要打印前10个斐波那契数字，请执行以下操作：

> print(Array(fibs.prefix(10)))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

如果你想过滤或者映射这个无限序列，你需要调用

首先，因为否则过滤器或映射将严格执行，并且不会终止。下面是前5个偶数斐波纳契数：

> print( Array(fibs.lazy.filter{$0 % 2 == 0}.prefix(5)) )
[2, 8, 34, 144, 610]