Swift 3 中的斐波那契数生成器
Fibonacci numbers generator in Swift 3
下面的问答涵盖了在Swift中生成斐波那契数列的一些方法，但它已经过时了(Swift 1.2?):
问题： 我们如何使用现代 Swift (Swift >= 3) 巧妙地生成斐波那契数列？最好是避免显式递归的方法。
使用全局 sequence(state:next:) 函数
Swift 3.0
作为一个替代方案，我们可以使用一个简洁的全局 sequence 函数，一对在 Swift 3.0 中实现的函数（如进化提案 SE-0094 中所述） .
使用后者，我们可以在 [=15= 的 next 闭包中将斐波那契数列的先前和当前状态保持为可变 state 属性 ].
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
})
}
或者，使用元组 hack 压缩它（但是执行 next 一个额外的、不必要的时间）
func fibs(through: Int, includingZero useZero: Bool = false) -> UnfoldSequence<Int, (Int, Int)> {
return sequence(state: useZero ? (1, 0) : (0, 1), next: {
([=11=].1 <= through ? [=11=].1 : Optional<Int>.none, [=11=] = ([=11=].1, [=11=].0 + [=11=].1)).0 })
}
func fibs1(through: Int) -> UnfoldSequence<Int, (Int, Int)> {
return sequence(state: (0, 1), next: {
([=11=].1 <= through ? [=11=].1 : Optional<Int>.none, [=11=] = ([=11=].1, [=11=].0 + [=11=].1)).0 })
}
请注意，当不再满足 ... <= through 条件时，我们使用 nil return 显式终止序列。
用法示例：
// fib numbers up through 50, excluding 0
fibs(through: 50).forEach { print([=12=]) }
// 1 1 2 3 5 8 13 21 34
// ... or
fibs1(through: 50).forEach { print([=12=]) }
// 1 1 2 3 5 8 13 21 34
// ... including 0
fibs(through: 50, includingZero: true).forEach { print([=12=]) }
// 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) { % 2 == 0 ? [=12=] + : [=12=] }) // 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([=13=]) }
// 1 1 2 3 5 8 13 21 34 55
Swift3.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: { [=14=] <= 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: { [=14=] <= through })
}
示例应与上面的 Swift 3.0 相同。
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)
}
来自 :
for f in sequence(first: (0, 1), while: { <= 50 }, next: { (, [=11=] + )}) {
print(f.1)
}
// 1 1 2 3 5 8 13 21 34
请注意，为了在结果序列中包含零，它
足以将初始值 (0, 1) 替换为 (1, 0):
for f in sequence(first: (1, 0), while: { <= 50 }, next: { (, [=12=] + )}) {
print(f.1)
}
// 0 1 1 2 3 5 8 13 21 34
这使得 "artificial" 检查
if pair.1 == 0 { pair.1 = 1; return 0 }
多余。根本原因是斐波那契数列可以
被推广到负指数（https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers）：
... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...
在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()}
要打印前 10 个斐波那契数：
> print(Array(fibs.prefix(10)))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
如果您想过滤或映射这个无限序列，您需要先调用 .lazy，否则过滤或映射将严格执行并且不会终止。这是前 5 个偶数斐波那契数：
> print( Array(fibs.lazy.filter{[=12=] % 2 == 0}.prefix(5)) )
[2, 8, 34, 144, 610]
递归不好用！！递归是邪恶的！
我宁愿这样做:
func fibo(_ n:Int) -> Int {
var a = 0
var b = 1
for _ in 0..<n {
a += b
b = a - b
}
return a
}
哪个更快更干净！
详情
Xcode9.3.1，Swift4.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 开始的斐波那契数列的第一次或前两次迭代。
时间复杂度：O(n)
Space 复杂度：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
}
}
用法
fib(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)
如果您不需要准确性，可以使用 O(1) 函数满足您的需求：
func fibonacci(iteration: Int) -> Int {
return Int(round(pow(1.618033988749895, Double(iteration)) / 2.23606797749979))
}
这是它的工作原理：
print((0..<40).map(fibonacci))
// prints [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
在 70 次迭代之前完美运行。
警告：在第 71 次迭代中 returns 308061521170130 而不是 308061521170129
我刚刚看到 Dhaval Gevariya 代码，只需将打印斐波那契移到上方而不是下方，现在它也会打印 0
func fibonaci(n: Int)
{
var fiboNumberOne = 1
var fiboNumberTwo = 0
for i in 0..<n
{
print("Fibonaci \(fiboNumberTwo)")
let temp = fiboNumberOne + fiboNumberTwo
fiboNumberOne = fiboNumberTwo
fiboNumberTwo = temp
}
}
fibonaci(n: 5)
// MARK: - Function
func fibonacciSeries(_ num1 : Int,_ num2 : Int,_ term : Int,_ termCount : Int) -> Void{
if termCount != term{
print(num1)
fibonacciSeries(num2, num2+num1, term, termCount + 1)
}
}
// 标记：- 调用函数
斐波那契数列 (0, 1, 5, 0)
// 标记：- out 放
0 1 1 2 3
注意 只需更改斐波那契数列的项数。
下面的问答涵盖了在Swift中生成斐波那契数列的一些方法，但它已经过时了(Swift 1.2?):
问题： 我们如何使用现代 Swift (Swift >= 3) 巧妙地生成斐波那契数列？最好是避免显式递归的方法。
使用全局 sequence(state:next:) 函数
Swift 3.0
作为一个替代方案，我们可以使用一个简洁的全局 sequence 函数，一对在 Swift 3.0 中实现的函数（如进化提案 SE-0094 中所述） .
使用后者，我们可以在 [=15= 的 next 闭包中将斐波那契数列的先前和当前状态保持为可变 state 属性 ].
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
})
}
或者，使用元组 hack 压缩它（但是执行 next 一个额外的、不必要的时间）
func fibs(through: Int, includingZero useZero: Bool = false) -> UnfoldSequence<Int, (Int, Int)> {
return sequence(state: useZero ? (1, 0) : (0, 1), next: {
([=11=].1 <= through ? [=11=].1 : Optional<Int>.none, [=11=] = ([=11=].1, [=11=].0 + [=11=].1)).0 })
}
func fibs1(through: Int) -> UnfoldSequence<Int, (Int, Int)> {
return sequence(state: (0, 1), next: {
([=11=].1 <= through ? [=11=].1 : Optional<Int>.none, [=11=] = ([=11=].1, [=11=].0 + [=11=].1)).0 })
}
请注意，当不再满足 ... <= through 条件时，我们使用 nil return 显式终止序列。
用法示例：
// fib numbers up through 50, excluding 0
fibs(through: 50).forEach { print([=12=]) }
// 1 1 2 3 5 8 13 21 34
// ... or
fibs1(through: 50).forEach { print([=12=]) }
// 1 1 2 3 5 8 13 21 34
// ... including 0
fibs(through: 50, includingZero: true).forEach { print([=12=]) }
// 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) { % 2 == 0 ? [=12=] + : [=12=] }) // 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([=13=]) }
// 1 1 2 3 5 8 13 21 34 55
Swift3.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: { [=14=] <= 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: { [=14=] <= through })
}
示例应与上面的 Swift 3.0 相同。
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)
}
来自
for f in sequence(first: (0, 1), while: { <= 50 }, next: { (, [=11=] + )}) {
print(f.1)
}
// 1 1 2 3 5 8 13 21 34
请注意，为了在结果序列中包含零，它
足以将初始值 (0, 1) 替换为 (1, 0):
for f in sequence(first: (1, 0), while: { <= 50 }, next: { (, [=12=] + )}) {
print(f.1)
}
// 0 1 1 2 3 5 8 13 21 34
这使得 "artificial" 检查
if pair.1 == 0 { pair.1 = 1; return 0 }
多余。根本原因是斐波那契数列可以 被推广到负指数（https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers）：
... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...
在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()}
要打印前 10 个斐波那契数：
> print(Array(fibs.prefix(10)))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
如果您想过滤或映射这个无限序列，您需要先调用 .lazy，否则过滤或映射将严格执行并且不会终止。这是前 5 个偶数斐波那契数：
> print( Array(fibs.lazy.filter{[=12=] % 2 == 0}.prefix(5)) )
[2, 8, 34, 144, 610]
递归不好用！！递归是邪恶的！
我宁愿这样做:
func fibo(_ n:Int) -> Int {
var a = 0
var b = 1
for _ in 0..<n {
a += b
b = a - b
}
return a
}
哪个更快更干净！
详情
Xcode9.3.1，Swift4.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 开始的斐波那契数列的第一次或前两次迭代。
时间复杂度：O(n)
Space 复杂度：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
}
}
用法
fib(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)
如果您不需要准确性，可以使用 O(1) 函数满足您的需求：
func fibonacci(iteration: Int) -> Int {
return Int(round(pow(1.618033988749895, Double(iteration)) / 2.23606797749979))
}
这是它的工作原理：
print((0..<40).map(fibonacci))
// prints [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
在 70 次迭代之前完美运行。
警告：在第 71 次迭代中 returns 308061521170130 而不是 308061521170129
我刚刚看到 Dhaval Gevariya 代码，只需将打印斐波那契移到上方而不是下方，现在它也会打印 0
func fibonaci(n: Int)
{
var fiboNumberOne = 1
var fiboNumberTwo = 0
for i in 0..<n
{
print("Fibonaci \(fiboNumberTwo)")
let temp = fiboNumberOne + fiboNumberTwo
fiboNumberOne = fiboNumberTwo
fiboNumberTwo = temp
}
}
fibonaci(n: 5)
// MARK: - Function
func fibonacciSeries(_ num1 : Int,_ num2 : Int,_ term : Int,_ termCount : Int) -> Void{
if termCount != term{
print(num1)
fibonacciSeries(num2, num2+num1, term, termCount + 1)
}
}
// 标记：- 调用函数 斐波那契数列 (0, 1, 5, 0)
// 标记：- out 放 0 1 1 2 3
注意 只需更改斐波那契数列的项数。