Números de fibonacci en lenguaje de Python

“Si se agrega 0 a 1, la respuesta sería 1. Si se suman la respuesta 1 y el addend (no el augend), la nueva respuesta sería 2. Si se suman esta nueva respuesta y su complemento, la respuesta sería 3. Si se suman esta nueva respuesta y su complemento, la respuesta sería 5."

Los números de Fibonacci son una secuencia particular en la que el primer valor está previamente decolorado como 0 y el segundo valor está predeclarado como 1. El resto de los números se producen a partir de estos dos agregando los dos números anteriores. Todos los números de Fibonacci son enteros positivos, comenzando desde 0. Los primeros doce números de Fibonacci y cómo se obtienen son los siguientes:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

Sin las expresiones de suma, estos números de fibonacci se pueden colocar en una tabla de la siguiente manera:

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

La primera fila tiene los números de fibonacci. La segunda fila tiene índices basados ​​en cero, suponiendo que los números de Fibonacci están en una matriz.

Los números de Fibonacci se pueden producir en el tiempo O (n) y en el tiempo o (1). En estas expresiones de complejidad de tiempo, N significa N operaciones principales, y 1 significa 1 operación principal. Con o (n), se producen números de n fibonacci, comenzando a partir de 0. Con O (1), se produce un número de fibonacci a partir de un índice correspondiente. Es por eso que solo se necesita una operación principal en lugar de n operaciones principales.

El objetivo de este artículo es explicar cómo producir números de Fibonacci, de cualquier manera, usando Python.

Fórmula para un número de fibonacci

La definición formal de un número de fibonacci es:

donde f_norte es el número de fibonacci en la N basada en cero

Producir números de fibonacci en el tiempo o (n)

Si n es 1, entonces solo 0 se imprimiría como un número de fibonacci. Si n es 2, entonces 0 y 1 se imprimirían como números de fibonacci, en ese orden. Si n es 3, entonces 0, 1 y 1 se imprimirían como números de fibonacci en ese orden. Si n es 4, entonces 0, 1, 1 y 2 se imprimirían como números de fibonacci en ese orden. Si n es 5, entonces 0, 1, 1, 2 y 3 se imprimirían como números de fibonacci, en ese orden. Si n es 6, entonces 0, 1, 1, 2, 3 y 5 se imprimirían como números de fibonacci, en ese orden, y así sucesivamente.

La función de Python para producir los primeros números N Fibonacci es:

Def fibonacci (n):
arr = [0] * (n)
arr [1] = 1
para i en el rango (2, n):
arr [i] = arr [i - 1] + arr [i - 2]
regresar arr

Comienza creando una matriz de n elementos, todo inicializado en ceros. Esta matriz tendrá los números de Fibonacci. El primer número de fibonacci, 0, ya está ahí. El segundo número Fibonacci, 1, es asignado por la siguiente declaración (en la función). Luego está el for-bucle, que comienza desde el índice 2 hasta justo antes de n. Tiene la declaración:

arr [i] = arr [i - 1] + arr [i - 2]

Esto agrega los dos números anteriores inmediatos.

El código para llamar a la función e imprimir los primeros doce números de Fibonacci puede ser:

N = 12
A = fibonacci (n)
para i en el rango (n):
imprimir (a [i], end = ")
imprimir()

La salida es:

0 1 1 2 3 5 8 13 21 34 55 89

Producir un número de fibonacci en tiempo constante

Hay una fórmula matemática que relaciona un índice basado en cero con su número de Fibonacci correspondiente. La fórmula es:

Tenga en cuenta que en el lado derecho de la ecuación, no es la raíz cuadrada de 5 la que se eleva al poder n; Es la expresión entre paréntesis la que se eleva al poder n. Hay dos de esas expresiones.

Si n es 0, FIBN sería 0. Si n es 1, fib_norte sería 1. Si n es 2, fib_norte sería 1. Si n es 3, fib_norte sería 2. Si n es 4, fib_norte serían 3, y así sucesivamente. El lector puede verificar esta fórmula matemáticamente mediante la sustitución de diferentes valores para n y evaluar. n es un índice basado en cero en esta fórmula.

El código de Python para esta fórmula es:

importación matemática

Def fibno (n):
Fibn = ((((1+matemáticas.sqrt (5))/2) ** n - ((1 -math.sqrt (5)) / 2) ** n) / matemáticas.SQRT (5)
FIBN de regreso

Se importó el módulo de matemáticas. Tiene la función de raíz cuadrada. El operador, ** se usa para la alimentación. La función fibno () implementa la fórmula directamente. Una llamada e impresión adecuadas para la función fibno () es:

N = 11
ret = fibno (n)
Imprimir (Ret)

La salida es:

89.0000000000000003

Es posible eliminar los dígitos decimales innecesarios de la respuesta. Sin embargo, esa es una discusión por otro tiempo.

Si se requieren diferentes números de fibonacci para diferentes índices de N, la función fibno () debe llamarse una vez para cada uno de los índice N para devolver los diferentes números de Fibonacci correspondientes. El siguiente programa hace esto para los índices basados ​​en cero, 7 a 9 (inclusive):

importación matemática

Def fibno (n):
Fibn = ((((1+matemáticas.sqrt (5))/2) ** n - ((1 -math.sqrt (5)) / 2) ** n) / matemáticas.SQRT (5)
FIBN de regreso
para i en el rango (7, 10):
imprimir (fibno (i), end = ")
imprimir()

La salida es:

13.00000000000000002 21.00000000000000004 34.0000000000000001

Tenga en cuenta la forma en que el bucle se ha codificado en Python. El primer índice es 7. El siguiente índice es 8, y el último índice es 9. 10 en el argumento de rango es 9 + 1. El valor en la posición de 10 debe ser el último índice basado en cero más 1. El primer argumento, 7, es el índice de inicio basado en cero.

Conclusión

Los números de Fibonacci son una secuencia particular de números enteros (enteros positivos). Comienza con 0, seguido de 1 incondicionalmente. El resto de los números se desarrollan a partir de ahí agregando los dos números anteriores inmediatos.

Para obtener los primeros números N fibonacci, acepte 0 y 1 como los dos primeros, luego para el resto, use un for-bucle con una declaración como:

arr [i] = arr [i - 1] + arr [i - 2]

que agrega los dos números anteriores inmediatos.

Para obtener solo un número de Fibonacci de un índice basado en cero N, use la fórmula: