Swift 3中的Fibonacci数字生成器

问题描述 投票:2回答:8

以下问答涵盖了在Swift中生成斐波纳契数的几种方法,但它已经过时了(Swift 1.2?):

问题:我们如何使用现代Swift(Swift> = 3)整齐地生成Fibonacci数?优选地,避免显式递归的方法。

swift swift3 sequence fibonacci
8个回答
4
投票

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

public func sequence<T>(first: T, while condition: @escaping (T)-> Bool, next: @escaping (T) -> T) -> UnfoldSequence<T, T> {
    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)
}

来自Express for loops in swift with dynamic range

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

请注意,为了在结果序列中包含零,只需用(0, 1)替换初始值(1, 0)即可:

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 }

多余的。根本原因是Fibonacci数可以推广到负指数(https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers):

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

4
投票

使用全局sequence(state:next:)函数

Swift 3.0

作为一种替代方案,我们可以使用一个整洁的全局sequence函数,一对在Swift 3.0中实现的函数(如演化提议SE-0094中所述)。

使用后者,我们可以将斐波纳契数列的先前和当前状态保持为statenext闭包中的可变sequence(state:next:)属性。

func fibs(through: Int, includingZero useZero: Bool = false)
    -> UnfoldSequence<Int, (Int, Int)> {
    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<Int, (Int, Int)> {
    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
        })
}

或者,使用元组黑客(但是执行next一个额外的,不必要的,时间)来缩小它

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

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

请注意,当不再满足nil条件时,我们使用... <= through返回显式终止序列。

用法示例:

// 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

我们还可以从上面移除终止标准以构建无限序列的斐波那契数,以组合使用,例如,与prefix

func infFibs() -> UnfoldSequence<Int, (Int, Int)> {
    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到达时,prefix(while:)序列的方法,如进化提案SE-0045中所述,将会实施。使用这个附加功能,我们可以修改上面的fibs方法,以避免显式的by-nil条件序列终止:

func fibs(through: Int, startingFromZero useZero: Bool = false)
    -> AnySequence<Int> {
    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<Int> {
    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相同。


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]

如果你想过滤或映射这个无限序列,你首先需要调用.lazy,否则过滤器或map将严格表现并且不会终止。以下是前5个甚至斐波那契数字:

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

0
投票

细节

Xcode 9.3.1,Swift 4.1

extension Array where Element: BinaryInteger {

    private mutating func fibonacci(index: Int) {
        if index >= count {
            return
        }
        self[index] = self[index-1] + self[index-2]
        return fibonacci(index: index+1)
    }

    init(fibonacci count: Int) {
        self = [Element]()
        if count < 0 {
            self = [Element]()
        }
        self = [Element](repeating: 1, count: count)
        fibonacci(index: 2)
    }

    static func calculate(fibonacciAt index: Int) -> Element? {

        if index < 0 {
            return nil
        }

        if index < 2 {
            return 1
        }

        func calc(a: Element, b: Element, index: Int) -> Element {
            if index == 1 {
                return b
            }
            return calc(a: b, b: a+b, index: index-1)
        }

        return calc(a: 1, b: 1, index: index)
    }
}

用法

let fibonacciSequence = [Int](fibonacci: 15)
let index = 12
print(fibonacciSequence)
print(fibonacciSequence[index])
let value = [Int].calculate(fibonacciAt: index)
print("\(value!)")

结果

enter image description here


0
投票

细节

XCode版本10.0 beta 6,Swift 4.2

需要控制流来获得从0开始的fibonacci seq的第一次或前两次迭代。

时间复杂度:O(n) 空间复杂度:O(n)

func fib(_ n: Int) -> [Int] {

 var fibs: [Int] = [0, 1]
 switch n
 {
 case 1:  return [fibs[0]]
 case 2:  return [fibs[0],fibs[1]]
 default:

 (2...n-1).forEach
 { i in
     fibs.append(fibs[i - 1] + fibs[i - 2])
 }

 return fibs
 }
}

用法

纤维(8)

//打印(FIB(8))


0
投票

来自David kopec的书“Swift中的经典计算机科学问题”:

通过递归

 var fibMemo: [UInt: UInt] = [0: 0, 1: 1] // our old base cases

 func fib3(n:  UInt) ­> UInt
 {

    if let result = fibMemo[n] 
    { 
       // our new base case

       return result
    } 
    else 
    {

       fibMemo[n] = fib3(n: n ­ 1) + fib3(n: n ­ 2) // memoization
    }

   return fibMemo[n]!
 }

通过迭代方法

func fib4(n: UInt) ­> UInt
{

     if (n == 0) 
     {
        // special case

        return n
     }

     var last: UInt = 0, next: UInt = 1 // initially set to fib(0) & fib(1          

     for _ in 1..<n {

          (last, next) = (next, last + next) }

     return next
}

0
投票
func fibonaci(n: Int)
{
    var fiboNumberOne = 1
    var fiboNumberTwo = 0

    for i in 0..<n
    {
        let temp = fiboNumberOne + fiboNumberTwo
        fiboNumberOne = fiboNumberTwo
        fiboNumberTwo = temp
        print("Fibonaci \(fiboNumberTwo)")

    }
}

 fibonaci(n: 5)

-2
投票

使用递归这是不好的!!递归是邪恶的!

我宁愿这样做:

func fibo(_ n:Int) -> Int {

    var a = 0
    var b = 1

    for _ in 0..<n {
        a += b
        b = a - b
    }

    return a
}

哪个更快更干净!

© www.soinside.com 2019 - 2024. All rights reserved.