Cómo implementar la función Fibonacci usando Python

Este artículo presenta principalmente cómo usar Python para implementar información relacionada con la función de Fibonacci. Los amigos que la necesiten pueden consultarla.

La secuencia de Fibonacci es muy simple. esto si aprendes algún lenguaje de programación.

He estado jugando con Python recientemente. Después de echar un vistazo rápido a Learning Python y Core Python, encontré accidentalmente una publicación en Internet sobre la evolución de los programadores de Python. Así que planeo imitar una publicación que utiliza más de diez métodos para completar una función factorial. Aquí escribiré una función de Fibonacci en nueve estilos diferentes.

Los requisitos son muy simples: ingrese n, genere el enésimo número de Fibonacci, n es un entero positivo

Los siguientes son nueve estilos diferentes:

1 ) Programadores de Python que escriben programas por primera vez:

def fib(n):

devuelve el enésimo número de Fibonacci Descripción:

Personas que escriben programas para primera vez A menudo sigue la sintaxis del lenguaje humano en lugar de la sintaxis del lenguaje de programación. Tomemos como ejemplo a un amigo mío que es muy bueno en programación. El primer programa que escribió para determinar los años bisiestos dice directamente esto: Si el año es un. año bisiesto, año de producción Es un año bisiesto; de lo contrario, el año no es un año bisiesto.

2) Programadores en C que acaban de aprender Python:

def fib(n):#{

if n<=2:

devuelve 1;

else:

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

#}Explicación:

Cuando entré en contacto con Python por primera vez, me sentí muy incómodo con el uso de sangrías en lugar de llaves para dividir bloques de programa. Además, no había un terminador después de cada declaración, por lo que terminé de escribir un Python cada vez. Lo que haces después de una función suele ser comentar las llaves y agregar los dos puntos que faltan.

3) Programadores Lazy Python:

def fib(n):

devuelve 1 y n<=2 o fib(n-1)+ fib( n-2) descripción:

Después de leer Aprendiendo Python, me di cuenta de que Python no tiene un operador ternario. , pero dado que el valor bool en Python es bastante especial (un poco como C, distinto de cero significa verdadero, no vacío significa verdadero) y las declaraciones lógicas de Python también admiten la evaluación de cortocircuito, esto puede ¿Se escribirá una imitación? sale la declaración.

4) Programadores más perezosos de Python:

fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2) descripción:

He usado la palabra clave lambda en C# y Scheme en Python es más simple que en C# y es muy similar al uso en Scheme, así que me adapté rápidamente. Esta forma de escritura se utiliza a menudo al declarar algunas funciones pequeñas en Python Shell.

5) Programadores de Python que acaban de aprender estructuras de datos:

def fib(n):

x,y=0,1

while(n):

x,y,n=y,x+y,n-1

return x descripción:

El Fibonacci anterior Todas las funciones son implementaciones de recursividad de árbol. Incluso si aprende un poco de algoritmo, debe conocer la ineficiencia de este tipo de recursividad. Aquí, cambiar de la recursividad del árbol a la iteración correspondiente puede mejorar mucho la eficiencia.

La función de asignación de tuplas de Python es algo que me gusta mucho. Esto puede simplificar mucho el código. Por ejemplo, el tmp=a;a=b;b=tmp; anterior se puede implementar directamente con la oración a,b=b,a, que es a la vez concisa y clara.

6) Programadores de Python que están tomando cursos de SICP:

def fib(n):

def fib_iter(n,x,y):

si n==0: devuelve x

si no: devuelve fib_iter(n-1,y,x+y)

devuelve fib_iter(n,0, 1) Explicación:

Aquí utilizo el método de escritura tail-recursion (Tail-recursion) que es muy común en el lenguaje Scheme. No hay iteración en Scheme, pero se pueden usar invariantes y recursividad de cola para simular la iteración y lograr el mismo efecto. Sin embargo, todavía no sé si Python ha realizado las optimizaciones correspondientes para la recursividad de cola, así que volveré a comprobarlo.

PD: Los estudiantes que han leído SICP pueden darse cuenta de un vistazo que este programa es en realidad un ejemplo del Capítulo 1 de SICP.

7) Un programador inteligente de Python:

fib=lambda n,x=0,y=1:x if not n else f(n-1,y, x+y ) Descripción:

La lógica básica es la misma que la del ejemplo anterior, que está escrita en recursividad de cola. La principal diferencia es que utiliza los parámetros predeterminados y el operador ternario proporcionados por Python, simplificando así el código a una línea. En cuanto a los parámetros predeterminados, todos los estudiantes que han estudiado C++ saben esto, y C# 4.0 también lo ha introducido.

8) Programadores de Python que acaban de completar álgebra lineal:

def fib(n):

def m1(a,b):

m=,] para i en rango(n)]),,], es decir:,]*[x,y]T=[y,x+y]T

Sea la matriz binaria A=,] y el vector binario x=T. Es fácil saber que el resultado de Ax es el siguiente valor de Fibonacci, es decir:

Ax=[fib(1), fib(2)]T

Además:

Ax=[fib(2),fib(3)]T

Por analogía, podemos obtener:

A?x=[fib(n),fib(n-1)]T En otras palabras, podemos realizar n A transformaciones en el vector binario T para obtener [fib(n),fib( n+1) ]T, obteniendo así fib(n).

Aquí defino una función de multiplicación de matrices binarias m1 y una transformación m2 en un vector binario, y luego uso la operación de reducción para completar una operación de multiplicación continua para obtener A?x, y finalmente obtener fib (n ).

9) Programadores de Python preparándose para participar en la competencia ACM:

def fib(n):

lhm=[,]

rhm=[[0],[1]]

em=,]

#multiplicar dos matrices

def Matrix_mul(lhm,rhm):< / p>

#inicializa una matriz vacía llena de cero

resultado=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm)) ]

#bucle multiplicar

para i en rango(len(lhm)):

para j en rango(len(rhm[0])):

para k en rango(len(rhm)):

resultado[i][j]+=lhm[i][k]*rhm[k][j]< / p>

devolver resultado

def Matrix_square(mat):

devolver Matrix_mul(mat,mat)

#transformación rápida

def fib_iter(mat,n):

si no n:

devuelve em

elif(n%2):

devolver matriz_mul(mat,fib_iter(mat,n-1))

más:

devolver matriz_cuadrado(fib_iter(mat,n/2))

return Matrix_mul(fib_iter(lhm,n),rhm)[0][0]Explicación:

Después de leer la función fib anterior, es más fácil entender esta versión. Esta versión también utiliza el método de transformación binaria. encontrar mentira (n). Pero la diferencia es que la complejidad de esta versión es lgn, mientras que la versión anterior es lineal.

La diferencia de esta versión es que define una operación de exponenciación rápida de una matriz, fib_iter. El principio es muy simple y se puede comparar con el método de exponenciación rápida de números naturales, así que no entraré. en detalles aquí.

PD: Aunque se dice que es la versión ACM, para ser honesto, nunca he participado en esa cosa. Después de todo, mi algoritmo es demasiado bueno y la cosa es demasiado sofisticada. Pruébelo aquí ~

En Python, la recursividad más básica (fib1 a continuación) es demasiado ineficiente. Siempre que el número n sea grande, el tiempo de cálculo será muy largo al guardar el índice calculado. en un dict, los cálculos posteriores se pueden realizar directamente. Úselo y este método se convertirá en una nota, como se muestra en la función fib2 a continuación, y encontrará que la eficiencia mejora enormemente.

Cuando n=10, el tiempo de ejecución de fib1 y fab2 es muy corto y no se puede ver ninguna diferencia, sin embargo, cuando n=40, es demasiado obvio que se necesitan 35 segundos para ejecutar fib1. 35 segundos para ejecutar fab2. 0,00001 segundos.

Cuando n=40, la salida es la siguiente:

jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py

2014 -10-16 16:28:35.176396

fib1(40)=102334155

2014-10-16 16:29:10.479953

fib2 (40) =102334155

2014-10-16 16:29:10.480035 Estas dos funciones para calcular la secuencia de Fibonacci son las siguientes:/smilejay/python/blob/master/py2014/fibonacci.py

importar fecha y hora

def fib1(n):

si n == 0:

devolver 0

elif n == 1:

devuelve 1

más:

devuelve fib1(n - 1) + fib1(n - 2)

conocido = { 0: 0, 1: 1}

def fib2(n):

si n en conocido:

devuelve conocido[n]

res = fib2(n - 1) + fib2(n - 2)

conocido[n] = res

devolver res

if __name__ == '__main__':

n = 40

print(datetime.datetime.now())

print('fib1(%d) =%d' % (n, fib1(n)))

print(datetime.datetime.now())

print('fib2(%d)=%d' % (n, fib2(n)))

Print(datetime.datetime.now()) Posdata:

Desde que aprendí Python no hace mucho, no soy competente suficiente para dominar sus diversas características. En lugar de decir que estoy escribiendo programas en Python, es mejor decir que estoy escribiendo programas en C, C++, C# o Scheme. En cuanto al legendario método Pythonic, todavía no tengo mucha experiencia. Después de todo, no he escrito ningún programa real en Python.

Learning Python y Core Python son buenos libros de introducción a Python, y el primero es más adecuado para personas sin conocimientos de programación.

Python es el mejor lenguaje de programación introductorio para principiantes. Por lo tanto, puede reemplazar a Scheme como lenguaje introductorio de programación informática del MIT.