python - programacion - serie fibonacci algoritmo

Cómo escribir la secuencia de Fibonacci?

Question

Originalmente había codificado el programa erróneamente. En lugar de devolver los números de Fibonacci entre un rango (es decir, startNumber 1, endNumber 20 should = solo esos números entre 1 y 20), he escrito para que el programa muestre todos los números de Fibonacci entre un rango (es decir, startNumber 1, endNumber 20 displays = Primeros 20 números de Fibonacci). Pensé que tenía un código seguro. Tampoco veo por qué sucede esto.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print map(fib, range(startNumber, endNumber))

Alguien señaló en mi Parte II (que se cerró por ser un duplicado - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) que necesita pasar el número de inicio y el número final a través de un generador usando un ciclo while. ¿Puede alguien señalarme en la dirección de cómo hacer esto? Cualquier ayuda es bienvenida.

Soy un programador de aprendizaje y me he encontrado con un revoltijo. Se me pide que escriba un programa que calculará y mostrará la secuencia de Fibonacci mediante un número de inicio y un número final ingresados ​​por el usuario (es decir, número_inicio = 20 número_denominado = 100 y solo mostrará los números entre ese rango). El truco es usarlo de manera inclusiva (que no sé cómo hacer en Python? - ¿Asumo que esto significa usar un rango inclusivo?).

Lo que tengo hasta ahora no es una codificación real, sino más bien:

• Escriba la fórmula de la secuencia Fib para infinito
• Muestra startNumber to endNumber solo desde la secuencia de Fib.

No tengo idea de por dónde empezar y estoy pidiendo ideas o ideas sobre cómo escribir esto. También traté de escribir el forumla de la secuencia de Fib, pero me pierdo en eso también.

Answer 1

Eficiente generador pitónico de la secuencia de Fibonacci

Encontré esta pregunta al tratar de obtener la generación Pythonic más corta de esta secuencia (luego me di cuenta de que había visto una similar en una Propuesta de Mejora de Python ), y no he notado que alguien más haya presentado mi solución específica (aunque la respuesta principal) se acerca, pero aún menos elegante), así que aquí está, con comentarios que describen la primera iteración, porque creo que puede ayudar a los lectores a entender:

def fib():
a, b = 0, 1
while True: # First iteration:
yield a # yield 0 to start with and then
a, b = b, a + b # a will now be 1, and b will also be 1, (0 + 1)

y uso:

for index, fibonacci_number in zip(range(10), fib()):
print(''{i:3}: {f:3}''.format(i=index, f=fibonacci_number))

huellas dactilares:

 0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55

(A fines de atribución, recientemente noté una implementación similar en la documentación de Python sobre módulos, incluso usando las variables a y b , que ahora recuerdo haber visto antes de escribir esta respuesta. Pero creo que esta respuesta demuestra un mejor uso del lenguaje).

Implementación definida recursivamente

La Enciclopedia en línea de las secuencias de enteros define la secuencia de Fibonacci recursivamente como

F (n) = F (n-1) + F (n-2) con F (0) = 0 y F (1) = 1

La definición sucinta de esto recursivamente en Python se puede hacer de la siguiente manera:

def rec_fib(n):
''''''inefficient recursive function as defined, returns Fibonacci number''''''
if n > 1:
return rec_fib(n-1) + rec_fib(n-2)
return n

Pero esta representación exacta de la definición matemática es increíblemente ineficiente para números mucho mayores que 30, porque cada número que se calcula también debe calcular para cada número debajo de él. Puedes demostrar lo lento que es usando lo siguiente:

for i in range(40):
print(i, rec_fib(i))

Recursividad memorizada para eficiencia

Puede ser memorizado para mejorar la velocidad (este ejemplo aprovecha el hecho de que un argumento de palabra clave predeterminado es el mismo objeto cada vez que se llama a la función, pero normalmente no usaría un argumento predeterminado mutable exactamente por este motivo):

def mem_fib(n, _cache={}):
''''''efficiently memoized recursive function, returns a Fibonacci number''''''
if n in _cache:
return _cache[n]
elif n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n

Descubrirá que la versión modificada es mucho más rápida y excederá rápidamente su profundidad de recursión máxima antes de que pueda pensar en levantarse para tomar un café. Puedes ver cuánto más rápido es visualmente al hacer esto:

for i in range(40):
print(i, mem_fib(i))

(Puede parecer que podemos hacer lo siguiente, pero en realidad no nos permite aprovechar el caché, porque se llama a sí mismo antes de que se llame a setdefault).

def mem_fib(n, _cache={}):
''''''don''t do this''''''
if n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n

Generador definido recursivamente:

Como he estado aprendiendo Haskell, me encontré con esta implementación en Haskell:

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

Lo más cerca que creo que puedo llegar a esto en Python en este momento es:

from itertools import tee
def fib():
yield 0
yield 1
# tee required, else with two fib()''s algorithm becomes quadratic
f, tf = tee(fib())
next(tf)
for a, b in zip(f, tf):
yield a + b

Esto lo demuestra:

[f for _, f in zip(range(999), fib())]

Sin embargo, solo puede llegar al límite de recursividad. Por lo general, 1000, mientras que la versión de Haskell puede llegar a cientos de millones, aunque usa los 8 GB de la memoria de mi computadora portátil para hacerlo:

> length $ take 100000000 fib
100000000

Answer 2

¿Por qué no simplemente hacer lo siguiente?

x = [1,1]
for i in xrange(10):
x.append(x[-1] + x[-2])
print '', ''.join(str(y) for y in x)

Answer 3

¿Que tal este? Supongo que no es tan elegante como las otras sugerencias porque exige la especificación inicial del resultado anterior para producir el resultado esperado, pero creo que es una opción muy legible, es decir, todo lo que hace es proporcionar el resultado y el resultado previo a la recursión.

#count the number of recursions
num_rec = 0
def fibonacci(num, prev, num_rec, cycles):
num_rec = num_rec + 1
if num == 0 and prev == 0:
result = 0;
num = 1;
else:
result = num + prev
print(result)
if num_rec == cycles:
print("done")
else:
fibonacci(result, num, num_rec, cycles)
#Run the fibonacci function 10 times
fibonacci(0, 0, num_rec, 10)

Aquí está el resultado:

0
1
1
2
3
5
8
13
21
34
done

Answer 4

15 minutos en un tutorial que utilicé al aprender Python, le pedí al lector que escribiera un programa que calcule una secuencia de Fibonacci a partir de 3 números de entrada (primer número de Fibonacci, segundo número y número para detener la secuencia). El tutorial solo cubría variables, if / thens, y loops hasta ese punto. Sin funciones todavía Se me ocurrió el siguiente código:

sum = 0
endingnumber = 1
print "/n.:Fibonacci sequence:./n"
firstnumber = input("Enter the first number: ")
secondnumber = input("Enter the second number: ")
endingnumber = input("Enter the number to stop at: ")
if secondnumber < firstnumber:
print "/nSecond number must be bigger than the first number!!!/n"
else:
while sum <= endingnumber:
print firstnumber
if secondnumber > endingnumber:
break
else:
print secondnumber
sum = firstnumber + secondnumber
firstnumber = sum
secondnumber = secondnumber + sum

Como puede ver, es realmente ineficiente, pero SI FUNCIONA.

Answer 5

Básicamente traducido de Ruby:

def fib(n):
a = 0
b = 1
for i in range(1,n+1):
c = a + b
print c
a = b
b = c

...

Answer 6

Código de Python canónico para imprimir la secuencia de Fibonacci:

a,b=1,1
while(True):
print a,
a,b=b,a+b # Could also use b=a+b;a=b-a

Para el problema "Imprima el primer número de Fibonacci de más de 1000 dígitos de longitud":

a,b=1,1
i=1
while(len(str(a))<=1000):
i=i+1
a,b=b,a+b
print i,len(str(a)),a

Answer 7

Esta fue una tarea práctica que vi en la Programación Sal on Python de Khan Academy: https://www.khanacademy.org/science/computer-science-subject/computer-science/v/exercise---write-a-fibonacci-function

Probablemente no sea la primera persona en asignar eso como algo que debe hacer. Pero es increíble descubrirlo por ti mismo. Aprendí mucho a descifrarlo realmente y fue una maravilla.

Te recomiendo que lo resuelvas por ti mismo antes de intentar copiar el código de otra persona para la tarea.

En el video de arriba, Sal, el instructor, muestra la teoría detrás del número de Fibonacci, y con eso en mente, deberías ser capaz de resolverlo.

Me llevó unos 10 minutos y este es el código que hice (estoy aprendiendo Python desde hace 3 días y este es mi primer lenguaje de programación para aprender). No habría podido escribir el código si no fuera por el video del tutorial anterior: https://www.khanacademy.org/science/computer-science-subject/computer-science/v/comparing-iterative-and-recursive-factorial-functions que da un ejemplo de Sal haciendo una ecuación factorial recursiva y le da la mentalidad para resolver este problema.

Aquí está mi código:

def fibonacci(num):
if num <= 1: #base case
return num
else:
return fibonacci(num-1) + fibonacci(num-2)

Puede ver que si el número es 1 o 0, simplemente devuelve el número.

Encuentro esto más limpio que decir si number es 1 return 1 y si number es 0 return 0.

Answer 8

Este es el más simple en python para la serie de Fibonacci, pero ajustado [0] en la matriz de salida por append () para dar como resultado una segunda variable de la lista de resultados que es result.append(second)

def fibo(num):
first = 0
second = 1
result = [0]
print(''Fibonacci series is'')
for i in range(0,num):
third = first + second
#print(second)
result.append(second)
first = second
second = third
print(result)
return
fibo(7)

SALIDA

Fibonacci series is
[0, 1, 1, 2, 3, 5, 8, 13]

Answer 9

Esto es bastante eficiente, usando O (log n) operaciones aritméticas básicas.

def fib(n):
return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n)

Éste usa O (1) operaciones aritméticas básicas, pero el tamaño de los resultados intermedios es grande y, por lo tanto, no es eficiente en absoluto.

def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

Éste calcula X ^ n en el anillo polinómico Z [X] / (X ^ 2 - X - 1) usando la exponenciación por cuadratura. El resultado de ese cálculo es el polinomio Fib (n) X + Fib (n-1), a partir del cual se puede leer el enésimo número de Fibonacci.

De nuevo, esto usa operaciones aritméticas O (log n) y es muy eficiente.

def mul(a, b):
return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1]
def fib(n):
x, r = (1, 0), (0, 1)
while n:
if n & 1: r = mul(r, x)
x = mul(x, x)
n >>= 1
return r[0]

Answer 10

Hay mucha información sobre la Secuencia de Fibonacci en wikipedia y en wolfram . Mucho más de lo que puedas necesitar De todos modos, es una buena idea aprender a usar estos recursos para encontrar (lo más rápido posible) lo que necesita.

Escriba la fórmula de la secuencia Fib para infinito

En matemáticas, se da en forma recursiva:

En la programación, infinito no existe. Puede usar una forma recursiva traduciendo el formulario matemático directamente en su idioma, por ejemplo, en Python se convierte en:

def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)

Pruébelo en su idioma favorito y vea que este formulario requiere mucho tiempo a medida que n se hace más grande. De hecho, este es O (2 ⁿ ) en el tiempo.

Continúa en los sitios que he vinculado contigo y verás esto (en wolfram ):

Este es bastante fácil de implementar y muy, muy rápido de calcular, en Python:

from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

Otra forma de hacerlo es seguir la definición (de wikipedia ):

El primer número de la secuencia es 0, el segundo número es 1, y cada número subsiguiente es igual a la suma de los dos números anteriores de la secuencia misma, produciendo la secuencia 0, 1, 1, 2, 3, 5, 8 , etc.

Si su idioma admite iteradores, puede hacer algo como:

def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b

Muestra startNumber to endNumber solo desde la secuencia de Fib.

Una vez que sepa cómo generar números de Fibonacci, solo tiene que desplazarse por los números y verificar si verifican las condiciones dadas.

Supongamos ahora que escribió af (n) que devuelve el n-ésimo término de la secuencia de Fibonacci (como el que tiene sqrt (5))

En la mayoría de los idiomas puedes hacer algo como:

def SubFib(startNumber, endNumber):
n = 0
cur = f(n)
while cur <= endNumber:
if startNumber <= cur:
print cur
n += 1
cur = f(n)

En Python usaría el formulario de iterador y buscaré:

def SubFib(startNumber, endNumber):
for cur in F():
if cur > endNumber: return
if cur >= startNumber:
yield cur
for i in SubFib(10, 200):
print i

Mi sugerencia es aprender a leer lo que necesitas. Project Euler (google for it) te entrenará para hacerlo: P ¡Buena suerte y diviértete!

Answer 11

La idea detrás de la secuencia de Fibonacci se muestra en el siguiente código de Python:

def fib(n):
if n == 1:
return 1
elif n == 0:
return 0
else:
return fib(n-1) + fib(n-2)

Esto significa que fib es una función que puede hacer una de tres cosas. Define fib (1) == 1, fib (0) == 0 y fib (n) para ser:

fib (n-1) + fib (n-2)

Donde n es un número entero arbitrario. Esto significa que fib (2), por ejemplo, se expande a la siguiente aritmética:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

Podemos calcular fib (3) de la misma manera con la aritmética que se muestra a continuación:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

Lo importante a tener en cuenta aquí es que fib (3) no se puede calcular sin calcular fib (2), que se calcula conociendo las definiciones de fib (1) y fib (0). Tener una llamada de función como la función de Fibonacci se llama recurrencia, y es un tema importante en la programación.

Esto suena como una tarea para hacer, así que no voy a hacer la parte de inicio / final para ti. Python es un lenguaje maravillosamente expresivo para esto, así que esto debería tener sentido si usted entiende las matemáticas, y con suerte le enseñará acerca de la recursión. ¡Buena suerte!

Editar: Una crítica potencial de mi código es que no usa el rendimiento súper práctico de la función Python, lo que hace que la función fib (n) sea mucho más corta. Mi ejemplo es un poco más genérico, ya que no muchos lenguajes fuera de Python tienen rendimiento.

Answer 12

La recursividad agrega tiempo. Para eliminar los bucles, primero import math . Luego use math.sqrt y golden ratio en una función:

#!/usr/bin/env python3
import math
def fib(n):
gr = (1 + math.sqrt(5)) / 2
fib_first = (gr**n - (1 - gr)**n) / math.sqrt(5)
return int(round(fib_first))
fib_final = fib(100)
print(fib_final)

ref: Números de Fibonacci en Python

Answer 13

Lo sabemos

Y que El n-ésimo poder de esa matriz nos da:

Entonces podemos implementar una función que simplemente compute la potencia de esa matriz a la potencia n-ésima.

como todos sabemos, el poder a ^ n es igual a

Así que al final la función de Fibonacci sería O (n) ... nada realmente diferente de una implementación más fácil si no fuera por el hecho de que también sabemos que x^n * x^n = x^2n y la evaluación de x^n por lo tanto se puede hacer con complejidad O (log n)

Aquí está mi implementación de fibonacci usando un lenguaje de programación veloz:

struct Mat {
var m00: Int
var m01: Int
var m10: Int
var m11: Int
}
func pow(m: Mat, n: Int) -> Mat {
guard n > 1 else { return m }
let temp = pow(m: m, n: n/2)
var result = matMultiply(a: temp, b: temp)
if n%2 != 0 {
result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
}
return result
}
func matMultiply(a: Mat, b: Mat) -> Mat {
let m00 = a.m00 * b.m00 + a.m01 * b.m10
let m01 = a.m00 * b.m01 + a.m01 * b.m11
let m10 = a.m10 * b.m00 + a.m11 * b.m10
let m11 = a.m10 * b.m01 + a.m11 * b.m11
return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}
func fibonacciFast(n: Int) -> Int {
guard n > 0 else { return 0 }
let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)
return pow(m: m, n: n-1).m00
}

Esto tiene complejidad O (log n). Calculamos la potencia de Q con el exponente n-1 y luego tomamos el elemento m00 que es Fn + 1 que en el exponente de potencia n-1 es exactamente el n-ésimo número de Fibonacci que queríamos.

Una vez que tenga la función rápida de fibonacci, puede iterar desde el número de inicio y el número final para obtener la parte de la secuencia de Fibonacci que le interesa.

let sequence = (start...end).map(fibonacciFast)

por supuesto, primero realice algún control al inicio y al final para asegurarse de que puedan formar un rango válido.

Sé que la pregunta tiene 8 años, pero me divertí respondiendo de todos modos. :)

Answer 14

OK ... después de estar cansado de referir todas las respuestas largas, ahora encuentre la manera siguiente y dulce, bastante directa para implementar Fibonacci en python. Puede mejorarlo de la manera que desee obteniendo un argumento o obteniendo información del usuario ... o cambie los límites de 10000. Como necesite ......

def fibonacci():
start = 0
i = 1
lt = []
lt.append(start)
while start < 10000:
start += i
lt.append(start)
i = sum(lt[-2:])
lt.append(i)
print "The Fibonaccii series: ", lt

Este enfoque también funciona bien. Encuentre el análisis de ejecución a continuación

In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop

Answer 15

Otra forma de hacerlo:

a,n=[0,1],10
map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2))

Asignar una lista a ''a'', asignar un entero a ''n'' Mapa y reducir son dos de las tres funciones más potentes en Python. Aquí el mapa se usa solo para iterar ''n-2'' veces. a [-2:] obtendrá los dos últimos elementos de una matriz. a.append (x + y) agregará los dos últimos elementos y se agregará a la matriz

Answer 16

Prueba esto:

def nth_fib(n):
if n == 0:
return 1
elif n == 1:
return 0
else:
return nth_fib(n - 1) + nth_fib(n - 2)

Answer 17

Simplemente pasando por http://projecteuler.net/problem=2 esta fue mi opinión

# Even Fibonacci numbers
# Problem 2
def get_fibonacci(size):
numbers = [1,2]
while size > len(numbers):
next_fibonacci = numbers[-1]+numbers[-2]
numbers.append(next_fibonacci)
print numbers
get_fibonacci(20)

Answer 18

Tal vez esto ayude

def fibo(n):
result = []
a, b = 0, 1
while b < n:
result.append(b)
a, b = b, b + a
return result

Answer 19

Todos estos parecen un poco más complicados de lo que necesitan ser. Mi código es muy simple y rápido:

def fibonacci(x):
List = []
f = 1
List.append(f)
List.append(f) #because the fibonacci sequence has two 1''s at first
while f<=x:
f = List[-1] + List[-2] #says that f = the sum of the last two f''s in the series
List.append(f)
else:
List.remove(List[-1]) #because the code lists the fibonacci number one past x. Not necessary, but defines the code better
for i in range(0, len(List)):
print List[i] #prints it in series form instead of list form. Also not necessary

Answer 20

Usando for loop e print solo el resultado

def fib(n:''upto n number'')->int:
if n==0:
return 0
elif n==1:
return 1
a=0
b=1
for i in range(0,n-1):
b=a+b
a=b-a
return b

Resultado

>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>>

Imprima la list contiene todos los números

def fib(n:''upto n number'')->int:
l=[0,1]
if n==0:
return l[0]
elif n==1:
return l
a=0
b=1
for i in range(0,n-1):
b=a+b
a=b-a
l.append(b)
return l

Resultado

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Answer 21

Ve a buscar cómo convertir un problema recursivo en uno iterativo. Debería ser capaz de calcular desde allí.

Es posible que sean los principios que intentan que aprendas, especialmente si se trata de un curso de Algoritmos.

Answer 22

basado en la secuencia clásica de fibonacci y solo por el bien de los de una sola línea

si solo necesitas el número del índice, puedes usar el reducir (incluso si reducirlo no es el más adecuado para esto, puede ser un buen ejercicio)

def fibonacci(index):
return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1]

y para obtener la matriz completa simplemente elimine el o (r.pop (0) y 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])

Answer 23

esto es una mejora para la respuesta de Henry henry:

def fib(n):
a = 0
b = 1
for i in range(1,n+1):
c = a + b
print b
a = b
b = c

el código debería imprimir b en lugar de imprimir c

salida: 1,1,2,3,5 ....

Answer 24

usar recursión:

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
x=input(''which fibonnaci do you want?'')
print fib(x)

Answer 25

¡hay un método muy fácil para darse cuenta de eso!

Puede ejecutar este código en línea libremente utilizando http://www.learnpython.org/

# Set the variable brian on line 3!
def fib(n):
"""This is documentation string for function. It''ll be available by fib.__doc__()
Return a list containing the Fibonacci series up to n."""
result = []
a = 0
b = 1
while a < n:
result.append(a) # 0 1 1 2 3 5 8 (13) break
tmp_var = b # 1 1 2 3 5 8 13
b = a + b # 1 2 3 5 8 13 21
a = tmp_var # 1 1 2 3 5 8 13
# print(a)
return result
print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]

Answer 26

Complejidad del tiempo

La función de almacenamiento en caché reduce la forma normal de calcular series de Fibonacci de O (2 ^ n) a O (n) al eliminar las repeticiones en el árbol recursivo de la serie de Fibonacci:

Código:

import sys
table = [0]*1000
def FastFib(n):
if n<=1:
return n
else:
if(table[n-1]==0):
table[n-1] = FastFib(n-1)
if(table[n-2]==0):
table[n-2] = FastFib(n-2)
table[n] = table[n-1] + table[n-2]
return table[n]
def main():
print(''Enter a number : '')
num = int(sys.stdin.readline())
print(FastFib(num))
if __name__==''__main__'':
main()

Answer 27

def fib():
a,b = 1,1
num=eval(input("Please input what Fib number you want to be calculated: "))
num_int=int(num-2)
for i in range (num_int):
a,b=b,a+b
print(b)

Answer 28

def fib(lowerbound, upperbound):
x = 0
y = 1
while x <= upperbound:
if (x >= lowerbound):
yield x
x, y = y, x + y
startNumber = 10
endNumber = 100
for fib_sequence in fib(startNumber, endNumber):
print "And the next number is... %d!" % fib_sequence

Answer 29

def fib(x, y, n):
if n < 1:
return x, y, n
else:
return fib(y, x + y, n - 1)
print fib(0, 1, 4)
(3, 5, 0)
#
def fib(x, y, n):
if n > 1:
for item in fib(y, x + y, n - 1):
yield item
yield x, y, n
f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55

Answer 30

import time
start_time = time.time()
#recursive solution
def fib(x, y, upperLimit):
return [x] + fib(y, (x+y), upperLimit) if x < upperLimit else [x]
#To test :
print(fib(0,1,40000000000000))
print("run time: " + str(time.time() - start_time))

Resultados

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368 , 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049 , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853]

tiempo de ejecución: 0.04298138618469238