以下问答涵盖了在Swift中生成斐波纳契数的几种方法,但它已经过时了(Swift 1.2?):
问题:我们如何使用现代Swift(Swift> = 3)整齐地生成Fibonacci数?优选地,避免显式递归的方法。
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, ...
sequence(state:next:)
函数作为一种替代方案,我们可以使用一个整洁的全局sequence
函数,一对在Swift 3.0中实现的函数(如演化提议SE-0094中所述)。
使用后者,我们可以将斐波纳契数列的先前和当前状态保持为state
的next
闭包中的可变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到达时,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相同。
在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]
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!)")
细节
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))
来自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
}
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)
使用递归这是不好的!!递归是邪恶的!
我宁愿这样做:
func fibo(_ n:Int) -> Int {
var a = 0
var b = 1
for _ in 0..<n {
a += b
b = a - b
}
return a
}
哪个更快更干净!