swift - serie - sucesion de fibonacci ejercicios
Generador de números de Fibonacci en Swift 3 (4)
La siguiente pregunta y respuesta cubre algunos métodos para generar números de Fibonacci en Swift, pero está bastante desactualizada (¿Swift 1.2?):
Pregunta: ¿Cómo podríamos generar números de Fibonacci pulcramente usando Swift moderno (Swift> = 3)? Preferiblemente métodos que eviten la recursión explícita.
Usando la función de sequence(state:next:) global sequence(state:next:)
Swift 3.0
Como una alternativa, podríamos hacer uso de una de las funciones de sequence global clara, un par de funciones que se implementaron en Swift 3.0 (como se describe en la propuesta de evolución SE-0094 ).
Usando el último de estos, podemos mantener el estado anterior y actual de la secuencia de números de Fibonacci como la propiedad de state mutable en el next cierre de la 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
})
}
O, condensando esto usando tuplas (sin embargo, ejecutando el next uno extra, innecesario, tiempo)
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 })
}
Tenga en cuenta que terminamos explícitamente las secuencias con un retorno nil cuando la condición ... <= through ya no se cumple.
Ejemplo de uso:
// 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
También podríamos eliminar los criterios de terminación de arriba para construir una secuencia infinita de números de Fibonacci, para ser usados en combinación, por ejemplo, con 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
Cuando llegue Swift 3.1, se habrá implementado el método de prefix(while:) para secuencias, como se describe en la propuesta de evolución SE-0045 . Usando esta característica adicional, podemos modificar los métodos de fibs arriba para evitar la terminación de secuencia condicional by- nil explícita:
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 })
}
Los ejemplos deberían funcionar igual que para Swift 3.0 anterior.
En Swift 3.1, aquí hay un iterador que genera números de Fibonacci para siempre, y una secuencia infinita derivada de él:
class FibIterator : IteratorProtocol {
var (a, b) = (0, 1)
func next() -> Int? {
(a, b) = (b, a + b)
return a
}
}
let fibs = AnySequence{FibIterator()}
Para imprimir los primeros 10 números de Fibonacci:
> print(Array(fibs.prefix(10)))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Si desea filtrar o asignar esta secuencia infinita, primero .lazy llamar a .lazy , ya que de lo contrario el filtro o el mapa se comportarán estrictamente y no terminarán. Aquí están los primeros 5 números pares de Fibonacci:
> print( Array(fibs.lazy.filter{$0 % 2 == 0}.prefix(5)) )
[2, 8, 34, 144, 610]
Una alternativa para Swift 3.0 sería usar la función auxiliar
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)
}
de Express para bucles en rápido con rango dinámico :
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
Tenga en cuenta que para incluir cero en la secuencia resultante, basta con reemplazar el valor inicial (0, 1) por (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
Eso hace que el cheque "artificial"
if pair.1 == 0 { pair.1 = 1; return 0 }
redundante. La razón subyacente es que los números de Fibonacci se pueden generalizar a índices negativos ( https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers ):
... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...
¡Esto es malo para usar la recursión! la recursión es malvada!
Hubiera preferido hacerlo de esta manera:
func fibo(_ n:Int) -> Int {
var a = 0
var b = 1
for _ in 0..<n {
a += b
b = a - b
}
return a
}
¡Lo cual es mucho más rápido y más limpio!