使用函数 Swift 的斐波那契项的总和

Question

我正在尝试学习函数 Swift 并开始从 Project Euler 做一些练习。

Even Fibonacci numbers Problem 2 Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

根据 WWDC 高级 Swift 视频实现了记忆斐波那契函数：

func memoize<T:Hashable, U>( body: ((T)->U,T) -> U) -> (T)->U {
  var memo = [T:U]()
  var result: ((T)->U)!
  result = { x in
    if let q = memo[x] { return q }
    let r = body(result,x)
    memo[x] = r
    return r
  }
  return result
}

let fibonacci = memoize { (fibonacci:Int->Double,n:Int) in n < 2 ? Double(n) : fibonacci(n-1) + fibonacci(n-2) }

并实现了一个符合 Sequence 协议的 class

class FibonacciSequence: SequenceType {
  func generate() -> GeneratorOf<Double> {
      var n = 0
      return GeneratorOf<Double> { fibonacci(n++) }
  }

  subscript(n: Int) -> Double {
      return fibonacci(n)
  }
}

问题的第一个（非功能性）解决方案：

var fib = FibonacciSequence().generate()
var n:Double = 0
var sum:Double = 0
while n < Double(4_000_000) {
  if n % 2 == 0 {
    sum += n
  }
n = fib.next()!
}

println(sum)

第二个更实用的解决方案，使用 ExSwift 作为 takeWhile 功能

let f = FibonacciSequence()
println((1...40).map { f[[=14=]] }
                .filter { [=14=] % 2 == 0 }
                .takeWhile { [=14=] < 4_000_000 }
                .reduce(0, combine: +))

我想改进这个解决方案，因为开始时的 1...40 范围无缘无故地计算了太多项。理想情况下，我希望能够有某种无限范围，但同时只计算满足 takeWhile

中条件的所需项

有什么建议吗？

Answer 1

这里我生成了一旦达到最大值就停止的序列。然后你只需要减少而不过滤，当n是奇数时和0就可以了。

func fibonacciTo(max: Int) -> SequenceOf<Int> {
    return SequenceOf { _ -> GeneratorOf<Int> in
        var (a, b) = (1, 0)
        return GeneratorOf {
            (b, a) = (a, b + a)
            if b > max { return nil }
            return b
        }
    }
}


let sum = reduce(fibonacciTo(4_000_000), 0) {a, n in (n % 2 == 0) ? a + n : a }

作为替代方案，如果您希望保留 fibonacci 更通用的功能，您可以使用 takeWhile 和 reduce1 扩展 SequenceOf 以获得类似函数组成：

 extension SequenceOf {
    func takeWhile(p: (T) -> Bool) -> SequenceOf<T> {
        return SequenceOf { _ -> GeneratorOf<T> in
            var generator = self.generate()
            return GeneratorOf {
                if let next = generator.next() {
                    return p(next) ? next : nil
                }
                return nil
            }
        }
    }

    // Reduce1 since name collision is not resolved
    func reduce1<U>(initial: U, combine: (U, T) -> U) -> U {
        return reduce(self, initial, combine)
    }
}


func fibonacci() -> SequenceOf<Int> {
    return SequenceOf { _ -> GeneratorOf<Int> in
        var (a, b) = (1, 0)
        return GeneratorOf {
            (b, a) = (a, b + a)
            return b
        }
    }
}

let sum2 = fibonacci()
    .takeWhile({ [=11=] < 4_000_000 })
    .reduce1(0) { a, n in (n % 2 == 0) ? a + n : a}

希望对您有所帮助

Answer 2

有一个 filter() 函数将序列作为参数：

func filter<S : SequenceType>(source: S, includeElement: (S.Generator.Element) -> Bool) -> [S.Generator.Element]

但由于 return 值是一个数组，如果您需要，这不适合使用 "infinite" 序列。但是

lazy(FibonacciSequence()).filter ( { [=11=] % 2 == 0 })

你得到一个 "infinite" 偶数斐波那契数列。你不能在该序列上调用 ExSwift 的 .takeWhile() 方法，因为 .takeWhile() 仅针对 struct SequenceOf 而不是针对一般序列。但是

TakeWhileSequence(
    lazy(FibonacciSequence()).filter ( { [=12=] % 2 == 0 }),
    { [=12=] < 4_000_000 }
)

有效并给出所有小于的偶数斐波那契数列 4,000,000。那么

let sum = reduce(TakeWhileSequence(
    lazy(FibonacciSequence()).filter ( { [=13=] % 2 == 0 }),
    { [=13=] < 4_000_000 }), 0, +)

给出预期结果并仅计算 "necessary" 斐波那契数列。

请注意，实际上没有必要记住斐波那契数列在这里是因为它们是按顺序访问的。另外（如@Matteo 已经注意到），所有斐波那契数都是整数。所以你可以将序列更简单地定义为

struct FibonacciSequence : SequenceType {

    func generate() -> GeneratorOf<Int> {
        var current = 1
        var next = 1
        return GeneratorOf<Int>() {
            let result = current
            current = next
            next += result
            return result
        };
    }
}

并且上述计算仍然有效。

Answer 3

您可以使用 Swift 的惰性序列非常接近您想要的结果。如果您使用斐波那契数列生成器（这是我正在使用的那个：）

var (a, b) = (1, 0)

var fibs =  GeneratorOf<Int> {

  (b, a) = (a, b + a)

  return b

}

你可以用 lazy() 包装它：

var (a, b) = (1, 0)

var fibs = lazy(

  GeneratorOf<Int> {

    (b, a) = (a, b + a)

    return b

  }
)

这将它作为惰性函数公开给 filter()。这个 filter() returns:

LazySequence<FilterSequenceView<GeneratorOf<Int>>>

现在，要获得 takeWhile() 函数，您需要扩展 LazySequence：

extension LazySequence {

  func takeWhile(condition: S.Generator.Element -> Bool)
    -> LazySequence<GeneratorOf<S.Generator.Element>> {

    var gen = self.generate()

    return lazy( GeneratorOf{ gen.next().flatMap{ condition([=13=]) ? [=13=] : nil }})

  }
}

因此如果基础序列结束或条件不满足，它 returns nil（停止生成器）。

综上所述，您在给定数字下的斐波那契数列看起来很像您想要的：

fibs
  .filter {[=14=] % 2 == 0}
  .takeWhile {[=14=] < 100}

//2, 8, 34

但是，因为 reduce 不是 LazySequence 上的方法，所以您必须转换为数组：

fibs
  .filter {[=15=] % 2 == 0}
  .takeWhile {[=15=] < 100}.array
  .reduce(0, combine: +)

//44

您可以对 LazySequence 做一个快速而肮脏的扩展来获得 reduce():

extension LazySequence {

  func reduce<U>(initial: U, combine: (U, S.Generator.Element) -> U) -> U {

    var accu = initial

    for element in self { accu = combine(accu, element) }

    return accu

  }
}

你可以这样写最后的东西：

fibs
  .filter {[=17=] % 2 == 0}
  .takeWhile {[=17=] < 100}
  .reduce(0, combine: +)

//44

所有这些序列都坚持它们的懒惰 - fibs 是无限的，所以它们不会真正起作用。事实上，在 reduce 之前什么都不会计算：在那之前都是 thunks。

Answer 4

在Swift 3.1中，这里有一个永远生成斐波那契数列的迭代器，以及从中派生出的无限序列：

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

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

let fibs = AnySequence{FibIterator()}

四百万以下的偶数项之和可以这样算：

fibs.prefix{[=11=] < 4000000}.filter{[=11=] % 2 == 0}.reduce(0){[=11=] + }

请注意 filter 和 map 默认情况下是严格的，并且将运行在无限序列上永远。在上面的示例中，这无关紧要，因为 prefix returns 只有有限数量的值。您可以调用 .lazy 来获得惰性序列，其中 filter 和 map 将表现得不严格。例如，这是前 5 个偶数斐波那契数：

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

使用函数 Swift 的斐波那契项的总和

Sum of Fibonacci term using Functional Swift

functional-programming

swift