¿Cómo escribir la secuencia de Fibonacci?

140

Originalmente había codificado el programa incorrectamente. En lugar de devolver los números de Fibonacci entre un rango (es decir, startNumber 1, endNumber 20 debería = solo aquellos números entre 1 y 20), he escrito para que el programa muestre todos los números de Fibonacci entre un rango (ie. StartNumber 1, endNumber 20 muestra = 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 estaba cerrada por ser un duplicado - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) que yo necesita pasar startNumber y endNumber a través de un generador usando un ciclo while. ¿Alguien puede señalarme la dirección de cómo hacer esto? Cualquier ayuda es bienvenida.


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

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

  • Escribe la fórmula de secuencia de Fib hasta infinito
  • Muestra startNumber to endNumber solo de la secuencia Fib.

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

DAKOTA DEL SUR.
fuente

Respuestas:

257

Hay mucha información sobre la secuencia de Fibonacci en Wikipedia y Wolfram . Mucho más de lo que pueda necesitar. De todos modos, es bueno aprender a usar estos recursos para encontrar (lo más rápido posible) lo que necesita.

Escribe la fórmula de secuencia de Fib hasta infinito

En matemáticas, se da de forma recursiva:

fibonacci de wikipedia

En programación, infinito no existe. Puede usar una forma recursiva traduciendo la forma matemática 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 crece. De hecho, esto es O (2 n ) en el tiempo.

Continúa en los sitios que te vinculé y verás esto (en wolfram ):

Ecuación de Fibonacci

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 siguiendo 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 de la secuencia Fib.

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

Suponga que ahora escribió af (n) que devuelve el ené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 la forma de iterador y buscaría:

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. El Proyecto Euler (google for it) te entrenará para hacerlo: P ¡Buena suerte y diviértete!

Andrea Ambu
fuente
1
Necesita usar un bucle while, no un mapa. Intenta resolverlo por tu cuenta, luego vuelve con el código si no puedes hacerlo. No soy vago (el código es más corto que este comentario). Lo estoy haciendo por ti, pruébalo con la pista "while";) Si tienes problemas con eso, vuelve otra vez;)
Andrea Ambu
Estoy de vuelta, jajaja. Me deshice de la función de mapa (rango) y estoy usando solo una función de rango (startNumber, endNumber). Ahora el problema que tengo es dónde usar la instrucción while. Intento al principio de la función pero, por supuesto, hay un billin en una línea de error. ¿Dónde debería ponerlo? Thx
SD.
Intente hacer, a mano, un ejemplo de entrada-salida de su programa (con un rango corto). Intenta averiguar dónde está mal tu programa. Intenta convertir el "método manual" en código. Esto es para hacer ejercicio, para aprender. Podría poner dos líneas de código, pero no creo que aprendas nada de ellas.
Andrea Ambu
1
Deberíamos usar int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))), ¿alguna idea? @AndreaAmbu
señor63. j
3
@ lord63.j, solo debe usar esa fórmula si sabe que comienza a desviarse del valor real cuando nestá por encima de 70 y explota con un OverflowError cuando nestá ligeramente por encima de 600. Otros enfoques pueden manejar un valor nde 1000 o más sin soplar arriba o perdiendo precisión.
cdlane
66

Generador pitónico eficiente de la secuencia de Fibonacci

Encontré esta pregunta al intentar obtener la generación Pythonic más corta de esta secuencia (más tarde me di cuenta de que había visto una similar en una Propuesta de Mejora de Python ), y no he notado que nadie más haya encontrado 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 eso puede ayudar a los lectores a comprender:

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

(Para fines de atribución, recientemente noté una implementación similar en la documentación de Python en los módulos, incluso usando las variables ay 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 secuencias enteras define la secuencia de Fibonacci recursivamente como

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

Definir sucintamente esto de forma recursiva 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. Puede demostrar lo lento que es utilizando lo siguiente:

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

Recursión memorable para la eficiencia

Se puede memorizar 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 por exactamente 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 memorable es mucho más rápida y superará rápidamente su profundidad máxima de recursión antes de que pueda siquiera pensar en levantarse para tomar un café. Puede ver cuánto más rápido es visualmente haciendo 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 llamar 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 subir hasta el límite de recurrencia. Por lo general, 1000, mientras que la versión de Haskell puede llegar a los cientos de millones, aunque utiliza los 8 GB de memoria de mi computadora portátil para hacerlo:

> length $ take 100000000 fib 
100000000

Consumir el iterador para obtener el enésimo número de Fibonacci

Un comentarista pregunta:

Pregunta para la función Fib () que se basa en el iterador: ¿qué sucede si desea obtener el enésimo, por ejemplo, el décimo número de fib?

La documentación de itertools tiene una receta para esto:

from itertools import islice

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

y ahora:

>>> nth(fib(), 10)
55
Aaron Hall
fuente
Acerca de la última opción '' 'no hacer esto' '', no entiendo por qué se llamaría a sí mismo antes de establecer el valor predeterminado. ¿No se supone que setdefault devuelve el valor si n es una clave válida? Doc dice: "Si la clave está en el diccionario, devuelva su valor. De lo contrario, inserte la clave con un valor predeterminado y devuelva default. El valor predeterminado es Ninguno". Qué me estoy perdiendo ?
binithb
@binithb la expresión dentro de la setdefaultllamada se evalúa antes de que setdefault sea.
Aaron Hall
23

¿Por qué no simplemente hacer lo siguiente?

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))
Thomas Spycher
fuente
21

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) como:

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

Donde n es un 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 función que se llama a sí misma como lo hace la función de Fibonacci se llama recursión, y es un tema importante en la programación.

Esto suena como una tarea, así que no voy a hacer la parte inicial / final por ti. Sin embargo, Python es un lenguaje maravillosamente expresivo para esto, por lo que debería tener sentido si comprende las matemáticas y, con suerte, le enseñará sobre la recursividad. ¡Buena suerte!

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

James Thompson
fuente
Este no es un problema de tarea, pero ¡guau, gracias por la respuesta! Entiendo lo que necesito hacer, pero iniciarlo e implementarlo es lo que estoy atascado ahora (especialmente con la implementación de valores de entrada del usuario). ¿Puedes darnos una idea de esto? Sigo recibiendo un error <function fib at 0x0141FAF0>.
SD.
Entiendo que está intentando implementar un programa que puede estar más allá de su capacidad actual. Hacerme escribir más código no te ayudará. Deberías intentar hackear mi código hasta que funcione, y leer más tutoriales de Python. El espacio en blanco puede ser un problema, pero no sé ese error.
James Thompson el
Entiendo. ¿Hay alguna otra idea que creas que pueda estar perdiendo? Sin embargo, entiendo si no puedes ayudar. Le doy las gracias por su tiempo.
SD.
Su error <function fib at 0x0141FAF0> puede ser el resultado de decir "fib" (que se refiere a la función en sí) en lugar de "fib ()" que llamará a la función. La mejor de las suertes.
Kiv
8
Tenga en cuenta que este método recursivo ingenuo para calcular los números de Fibonacci puede entrar en el desbordamiento de la pila (no en el sitio) muy rápido. Para fines prácticos, genere iterativamente o use algún tipo de memorización o algo así.
David Thornley
12

Complejidad del tiempo:

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

ingrese la descripción de la imagen aquí

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()
Akash Rana
fuente
9

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

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

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

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

Éste calcula X ^ n en el anillo polinomial 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), del cual se puede leer el enésimo número de Fibonacci.

Nuevamente, 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]
Paul Hankin
fuente
1
La primera y la tercera técnica son buenas. La segunda técnica está desactivada por 1; efectivamente necesita n -= 1funcionar correctamente, y tampoco funciona n = 0. En cualquier caso, realmente me ayudaría si se agregara mucho contexto para explicar cómo funcionan, especialmente la primera técnica. Veo que tienes una publicación en paulhankin.github.io/Fibonacci
Acumenus
6

Código canónico de Python 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":

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
DaVinci
fuente
4

Lo sabemos

ingrese la descripción de la imagen aquí

Y que la enésima potencia de esa matriz nos da:

ingrese la descripción de la imagen aquí

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

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

ingrese la descripción de la imagen aquí

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

Aquí está mi implementación de Fibonacci usando lenguaje de programación rápido:

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 ené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 inicial 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 algunas verificaciones 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. :)

Giuseppe Lanza
fuente
3

Secuencia de Fibonacci es: 1, 1, 2, 3, 5, 8, ....

Es decir f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Mi implementación favorita (la más simple y, sin embargo, alcanza una velocidad de la luz en comparación con otras implementaciones) es esta:

def fibonacci(n):
    a, b = 0, 1
    for _ in range(1, n):
        a, b = b, a + b
    return b

Prueba

>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]

Sincronización

>>> %%time
>>> fibonacci(100**3)
CPU times: user 9.65 s, sys: 9.44 ms, total: 9.66 s
Wall time: 9.66 s

Editar: un ejemplo de visualización para esta implementación.

Aziz Alto
fuente
3

usar recursividad:

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)
usuario2095044
fuente
2

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 la lista a 'a', asignar un número entero a 'n' Map y reduce son 2 de las tres funciones más poderosas en python. Aquí el mapa se usa solo para iterar 'n-2' veces. un [-2:] obtendrá los dos últimos elementos de una matriz. a.append (x + y) agregará los dos últimos elementos y se agregará a la matriz

sanooj
fuente
1

Todo esto parece un poco más complicado de lo que debe 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
Timmy
fuente
2
Programación dinámica FTW! fibonacci (100000000000000000000000000000000000000000000000000000000000000000000000000000) responde casi al instante
Hans
66
De alguna manera lo dudo.
Lanaru
¿Qué pasa con el inicio de la lista como [0, 1] (es decir, List.append (0); List.append (1)) para evitar el comando de eliminación después de lo contrario? ... y el número de Fibonacci debería indexarse ​​mejor ya que Fibonacci (10) devuelve los números de Fibonacci por debajo de 10, no el décimo.
SeF
1

De acuerdo ... después de estar cansado de referir todas las respuestas largas, ahora encuentre la forma más sencilla y dulce a continuación para implementar Fibonacci en Python. Puede mejorarlo de la manera que desee obteniendo un argumento u obteniendo la entrada del usuario ... o cambiando los límites de 10000. Según lo 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. Encuentra los análisis de ejecución a continuación

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

Esta es una mejora a la respuesta de Matthew 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 debe imprimir b en lugar de imprimir c

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

adongo
fuente
1

Usando for loop e imprime 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 el que listcontiene 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]
R__raki__
fuente
1
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 13, en El

tiempo de ejecución: 0.04298138618469238

Nathan Rogers
fuente
1

¡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]
xgqfrms
fuente
¡Una manera fácil de realizar la serie Fibonacci simplemente usando el iterador, sin ninguna estructura de datos de recursión compleja!
xgqfrms
1

Se puede hacer de la siguiente manera.

n = 0

números = [0]

para i en rango (0,11):
    imprimir n,
    números.append (n)
    prev = números [-2]
    si n == 0:
        n = 1
    más:
        n = n + anterior
J.Jai
fuente
1

Solo por diversión, en Python 3.8+ puede usar una expresión de asignación (también conocido como el operador de morsa) en una comprensión de la lista, por ejemplo:

>>> a, b = 0, 1
>>> [a, b] + [b := a + (a := b) for _ in range(8)]  # first 10 Fibonacci numbers
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Una expresión de asignación le permite asignar un valor a una variable y devolverlo en la misma expresión. Por lo tanto, la expresión

b := a + (a := b)

es equivalente a ejecutar

a, b = b, a + b

y devolviendo el valor de b.

Eugene Yarmash
fuente
0

A los 15 minutos de un tutorial que usé cuando aprendí Python, le pidió 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 en el que detener la secuencia). El tutorial solo había cubierto variables, if / thens, y bucles hasta ese punto. Aún no hay funciones. 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 sí funciona.

Jonas
fuente
0
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)
AlexB
fuente
3
eval(input())no es necesario aquí; Creo que int(input())en el caso es mejor.
GingerPlusPlus
0

Simplemente revisando http://projecteuler.net/problem=2 esta fue mi opinión al respecto

# 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)
Filype
fuente
0
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
jdsantiagojr
fuente
0

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
van Gogh
fuente
0

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

si solo necesita el número del índice, puede usar la reducción (incluso si la reducción no es la más adecuada 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 o (r.pop (0) y 0)

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

¿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 anterior para La recursividad.

#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á la salida:

0
1
1
2
3
5
8
13
21
34
done
the_marcelo_r
fuente
0

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

...

Matthew Smith
fuente
0
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
JayL
fuente
0

Una explicación más detallada de cómo funciona Memoization para la secuencia de Fibonacci.

# Fibonacci sequence Memoization

fib_cache = {0:0, 1:1}

def fibonacci(n):
    if n < 0:
        return -1
    if fib_cache.has_key(n):
        print "Fibonacci sequence for %d = %d cached" % (n, fib_cache[n])
        return fib_cache[n]
    else:
        fib_cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return fib_cache[n]

if __name__ == "__main__":
    print fibonacci(6)
    print fib_cache
    # fibonacci(7) reuses fibonacci(6) and fibonacci(5)
    print fibonacci(7)
    print fib_cache
sysuser
fuente
0

Estaba tratando de evitar una función recursiva para resolver este problema, así que tomé un enfoque iterativo. Originalmente estaba haciendo una función recursiva memorable, pero seguí alcanzando la profundidad recursiva máxima. También tenía objetivos estrictos de memoria, por lo que me verás manteniendo la matriz lo más pequeña posible durante el proceso de bucle, manteniendo solo 2-3 valores en la matriz en cualquier momento.

def fib(n):
    fibs = [1, 1] # my starting array
    for f in range(2, n):
        fibs.append(fibs[-1] + fibs[-2]) # appending the new fib number
        del fibs[0] # removing the oldest number
    return fibs[-1] # returning the newest fib

print(fib(6000000))

Obtener el número 6 millones de Fibonacci toma alrededor de 282 segundos en mi máquina, mientras que el 600K Fibonacci toma solo 2.8 segundos. No pude obtener números de Fibonacci tan grandes con una función recursiva, incluso una memorable.

Jared Mackey
fuente