© Sashkin/Shutterstock.com
La secuencia de Fibonacci es, sin duda, una de las secuencias matemáticas más famosas de todos los tiempos. Los matemáticos y los científicos han estado usando esta secuencia durante siglos en matemáticas y ciencias, nombrándola en honor al famoso matemático italiano de la Edad Media, Fibonacci.
La sucesión de Fibonacci es una serie de números en la que cada número subsiguiente es la suma de los dos anteriores, empezando por 0 y 1. La secuencia suele denotarse con Fn y tiene este aspecto: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, etc.
Pero ¿Cual es el problema? ¿Por qué debería importarnos la sucesión de Fibonacci? Bueno, resulta que esta secuencia no es solo una serie arbitraria de números.
La secuencia de Fibonacci se encuentra en toda la naturaleza y en muchas áreas de la ciencia, y tiene importantes aplicaciones en informática y programación. La importancia de la serie en la informática se deriva de los diversos algoritmos que pueden generar sus números.
Los lenguajes de programación como Python tienen funciones integradas para generar la secuencia de Fibonacci. Si está interesado en comprender los algoritmos detrás de estas funciones, quédese, ya que este artículo explicará algunos de los 7 algoritmos y métodos principales utilizados para generar los números de Fibonacci.
Diferentes métodos para crear programas para los números de Fibonacci
Existen múltiples métodos/enfoques para generar números de Fibonacci, cada uno con diferentes complejidades de tiempo y espacio. La forma más sencilla de encontrar el n-ésimo número de Fibonacci es usar la recursividad.
Sin embargo, este enfoque no es muy eficiente y puede conducir a muchos cálculos redundantes. Por lo tanto, exploraremos la recursividad junto con otros métodos para ver cuál(es) puede(n) considerarse el más eficiente.
Recursión
La recursividad es un método para resolver un problema en el que el solución depende de las soluciones a instancias más pequeñas del mismo problema. En el contexto de la sucesión de Fibonacci, la solución recursiva funciona dividiendo el problema de encontrar el n-ésimo número de Fibonacci en dos problemas más pequeños: encontrar el (n-1)-ésimo número de Fibonacci y encontrar el (n-2)-ésimo número de Fibonacci.
Este proceso continúa recursivamente hasta que se alcanza el caso base, donde n es 0 o 1. El caso base representa la condición que la función debe cumplir para dejar de llamarse a sí misma. Una vez que se cumple, la función simplemente devuelve n. Para todos los demás valores de n, la función recursivamente se llama a sí misma, pasando n-1 y n-2 como argumentos/parámetros.
El siguiente ejemplo muestra un programa de Python simple que implementa la recursividad para generar números de Fibonacci:
def fibonacci(n):
if n=1: # caso base
return n
otro:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # Salida: 13
La función primero comprueba el caso base sobre lo cual devuelve n. Si n es mayor que 1, la función recursivamente se llama a sí misma con n-1 y n-2 como argumentos y suma sus valores devueltos. Esto se debe a que el número n-ésimo en una secuencia de Fibonacci es igual a la suma de los números (n-1)-ésimo y (n-2)-ésimo en la secuencia.
Las llamadas recursivas continúan hasta que se alcanza el caso base y la función devuelve el n-ésimo número en la secuencia. Podemos obtener la complejidad temporal de la solución recursiva: su exponencial es O(2n), ya que la función se llama a sí misma dos veces para cada valor de n.
Esto puede volverse ineficiente rápidamente a medida que n crece, lo que hace que este método no sea práctico para valores más grandes de n. La complejidad del espacio es O(n), que es lineal, ya que la profundidad máxima del árbol recursivo es n.
Iteración
La iteración es un enfoque más eficiente para resolver la secuencia de Fibonacci problema. El enfoque iterativo implica resolver un problema ejecutando repetidamente un conjunto de instrucciones hasta que se cumpla una condición específica.
En el contexto de la secuencia de Fibonacci, la solución iterativa funciona comenzando con los dos primeros números de Fibonacci y calculando el siguiente número de Fibonacci utilizando los dos anteriores. Este proceso continúa hasta que se calcula el enésimo número de Fibonacci.
La secuencia de Fibonacci apareció por primera vez en el manuscrito latino”Liber Abaci”(1202), donde se usaba para calcular el crecimiento de las poblaciones de conejos.
©TippaPatt/Shutterstock.com
Podemos implementar un programa simple usando iteración para crear números de Fibonacci de la siguiente manera:
def fibonacci(n):
if n==0:
devuelve 0
elif n==1:
devuelve 1
else:
fib1, fib2=0, 1
para i en rango (2, n+1):
fib=fib1 + fib2
fib1, fib2=fib2, fib
return fib2
Aquí, estamos usando un ciclo para calcular el n-ésimo número de Fibonacci en tiempo lineal. Logramos esto comenzando con los primeros dos números en la secuencia (0 y 1) y calculando iterativamente el siguiente número como la suma de los dos anteriores.
Hacemos un seguimiento de los dos números anteriores en variables y los actualizamos en cada iteración. Después de n iteraciones, devolvemos el n-ésimo número.
La complejidad temporal de la solución iterativa es O(n), que es lineal. Esto se debe a que el ciclo for se ejecuta n-1 veces para calcular el n-ésimo número de Fibonacci. Dado que la función usa solo un número constante de variables para calcular el n-ésimo número de Fibonacci, su complejidad espacial es O(1), que es constante.
Memoización
Memoización es un método de resolver un problema almacenando los resultados de costosas llamadas a funciones y devolviendo el resultado almacenado en caché cuando se repiten las mismas entradas.
En el contexto de la secuencia de Fibonacci, la solución de memorización funciona almacenando las soluciones a los subproblemas y devolviendo el resultado almacenado en caché, si está disponible.
De esta manera, el programa calcula la solución a cada subproblema solo una vez y lo reutiliza cuando es necesario.
Aquí hay un ejemplo de implementación de memorización:
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
elif n=1:
return n
else:
memo[n]=fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
Este ejemplo utiliza un top-Down enfoque para calcular el n-ésimo número de Fibonacci almacenando en caché los valores calculados previamente para evitar cálculos redundantes. La función primero verifica si ya calculó y almacenó en caché el valor del n-ésimo número de Fibonacci en un diccionario de Python. Si es así, devuelve el valor almacenado en caché.
Si no lo ha hecho, calcula el valor recursivamente como la suma de los números de Fibonacci (n-1)-ésimo y (n-2)-ésimo, almacena en caché el valor calculado en el diccionario y lo devuelve.
La complejidad temporal de la solución de memorización es O(n), que es lineal. Esto se debe a que el programa calcula cada número de Fibonacci solo una vez y lo almacena en el diccionario de notas para uso futuro. La complejidad del espacio también es O(n), que es lineal, ya que el diccionario memo almacena soluciones a subproblemas hasta n.
Programación dinámica
La programación dinámica es un método para resolver un problema dividiéndolo en subproblemas más pequeños y almacenando las soluciones a estos subproblemas para evitar cálculos redundantes.
En el contexto de la secuencia de Fibonacci, la solución de programación dinámica funciona calculando los números de Fibonacci de forma ascendente y almacenando las soluciones en una matriz. De esta manera, la solución a cada subproblema solo se calcula una vez y se reutiliza cuando es necesario.
Considere el siguiente ejemplo:
def fibonacci(n):
fib=[0, 1]
para i en el rango (2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
La función usa una lista de Python para almacenar los valores calculados de la secuencia, comenzando con los dos primeros valores. Luego, itera de 2 a n, calculando el valor i-ésimo como la suma de los valores (i-1)-ésimo y (i-2)-ésimo y almacenándolo en la lista. Finalmente, devuelve el valor n-ésimo de la lista.
La complejidad temporal de la solución de programación dinámica es O(n), que es lineal. La complejidad temporal del algoritmo es O(n) porque el bucle for calcula el número de Fibonacci número n ejecutando n-1 veces, y cada cálculo requiere un tiempo constante.
Además, la complejidad espacial del algoritmo es O(n) porque utiliza una lista de tamaño n para almacenar las soluciones a los subproblemas.
Exponenciación de matrices
La exponenciación de matrices es un método para resolver un problema elevando una matriz a una potencia. En el contexto de la secuencia de Fibonacci, la solución de exponenciación de matrices funciona mediante el uso de una matriz con números de Fibonacci para elevarla a la potencia de n-1 para obtener el número de Fibonacci enésimo.
Podemos usar la exponenciación de matrices para cree un programa de Python para los números de Fibonacci, como se muestra:
import numpy as np
def fibonacci(n):
F=np.array([[ 1, 1], [1, 0]])
return np.linalg.matrix_power(F, n-1)[0, 0]
En este ejemplo, estamos usando una técnica de exponenciación matricial para calcular el n-ésimo número de Fibonacci en tiempo logarítmico. Para lograr esto, elevamos una matriz de 2×2 a la potencia de n-1 y la multiplicamos por el vector de estado inicial [0, 1]. La matriz resultante contiene los números de Fibonacci n-ésimo y (n+1)-ésimo, y devolvemos el número n-ésimo.
La complejidad temporal de la solución de exponenciación matricial es O(log n), que es, por supuesto, logarítmico. El algoritmo divide y vencerás que se usa en la multiplicación de matrices reduce el número de multiplicaciones requeridas. Por lo tanto, la complejidad del espacio es O(1), que es constante, ya que solo se utiliza una cantidad constante de memoria.
Fórmula de Binet
La fórmula de Binet es una fórmula directa para calcular la enésimo número de Fibonacci sin tener que calcular todos los números de Fibonacci anteriores.
La fórmula suele escribirse como: Fn=round((Φ^n – (1-Φ)^n)/√5), donde Φ (phi) es la proporción áurea.
La fórmula de Binet sugiere que la proporción de dos números de Fibonacci consecutivos tiende a la proporción áurea a medida que n aumenta.
©TippaPatt/Shutterstock.com
En el contexto de la sucesión de Fibonacci, la fórmula de Binet funciona utilizando la proporción áurea, que es (1 + √5)/2, y su conjugado, que es 1 – √5)/2.
Un ejemplo en Python sería:
def fibonacci(n):
proporción_áurea=(1 + 5**0,5)/2
ronda de retorno((proporción_áurea**n – (1 – proporción_áurea)**n)/5**0,5 )
La función primero define la proporción áurea. A continuación, calculamos el término n-ésimo utilizando la fórmula de Binet y devolvemos el valor entero redondeado del resultado.
Esta implementación de la fórmula de Binet es computacionalmente eficiente porque requiere solo unas pocas operaciones aritméticas simples para calcular cualquier término de la secuencia de Fibonacci, sin necesidad de calcular todos los términos anteriores.
Esto se demuestra por la complejidad temporal de la fórmula de Binet que es O(1), que es constante. Esto se debe a que la fórmula solo requiere unas pocas operaciones aritméticas para calcular el n-ésimo número de Fibonacci. La complejidad del espacio es O(1), que es constante, porque el programa usa solo unas pocas variables para calcular el n-ésimo número de Fibonacci.
Algoritmo codicioso
El algoritmo codicioso es una técnica Se utiliza para resolver problemas de optimización. Funciona tomando la mejor decisión en cada paso y esperando que las decisiones tomadas conduzcan a una solución óptima. Este algoritmo sigue la estrategia”codiciosa”de elegir siempre el número más grande posible en cada paso.
Uno puede generar números de Fibonacci usando este enfoque comenzando con los dos casos base y luego iterando a través de la serie para encontrar el siguiente número
Primero, guarda los dos números anteriores en dos variables y luego súmalos para obtener el siguiente número de Fibonacci. Este proceso continúa hasta que se genera el número n-ésimo en la secuencia.
Podemos implementar un programa para números de Fibonacci usando el algoritmo Greedy de una manera simple, de la siguiente manera:
def fibonacci(n):
si n=1:
retorna n
prev, curr=0, 1
para i en range(2, n+1):
prev, curr=curr, prev + curr
return curr
Primero comprobamos si n satisface el caso base , en cuyo caso devolvimos el valor apropiado. De lo contrario, creamos una lista para almacenar los dos números de Fibonacci anteriores (0 y 1), y luego usamos un ciclo para generar los siguientes números en la secuencia al agregar los dos últimos números en la lista. El ciclo continúa hasta que se genera el n-ésimo número en la secuencia, momento en el que lo devolvemos.
La complejidad temporal del Algoritmo Greedy es O(n), que es lineal, ya que necesitamos iterar n veces para generar el n-ésimo número en la secuencia. La complejidad del espacio también es O(n), ya que necesitamos almacenar los dos números anteriores en la secuencia para cada iteración del bucle.
Sin embargo, podríamos optimizar la complejidad del espacio almacenando solo los dos números anteriores en lugar de todos los números generados hasta ahora.
Redondeando hacia arriba
La secuencia de Fibonacci es un concepto matemático importante y atemporal con numerosas aplicaciones en informática y programación. Con el algoritmo correcto, puede generar rápida y fácilmente cualquier número de Fibonacci.
En términos generales, la iteración y la programación dinámica son los algoritmos más eficientes en términos de complejidad de tiempo y espacio, mientras que la exponenciación matricial es la más eficiente en términos de complejidad de tiempo para valores más grandes de n. La recursividad es la más intuitiva pero también la menos eficiente en términos de complejidad de tiempo y complejidad de espacio.
Al final, el mejor algoritmo a usar depende del problema en cuestión. Por lo tanto, es importante comprenderlos para saber cuándo utilizar cada método para optimizar el rendimiento de sus programas de Fibonacci.
Programa para números de Fibonacci con ejemplos Preguntas frecuentes (FAQ)
Espiral de Arquímedes, Proporción áurea, Secuencia de Fibonacci: ¿Cuál es la conexión?
La espiral de Arquímedes y la secuencia de Fibonacci se pueden relacionar a través de la proporción áurea.
La La proporción áurea es una constante matemática que es igual a la proporción de dos números en la secuencia de Fibonacci. Esta proporción también se puede encontrar en la forma de la Espiral de Arquímedes.
Por lo tanto, los tres conceptos están interrelacionados y tienen importantes aplicaciones en matemáticas, ciencias y arte.
¿Cuál es la diferencia entre recursión e iteración al generar números de Fibonacci?
La recursividad es una técnica en la que una función se llama a sí misma para resolver un problema, mientras que la iteración es una estructura de bucle que repite un conjunto de instrucciones hasta que se cumpla una determinada condición.
La recursividad es el enfoque más directo para generar números de Fibonacci, pero es ineficiente debido a su complejidad de tiempo exponencial. La iteración es más eficiente y puede calcular el n-ésimo número en tiempo lineal.
¿Cómo se aplica la secuencia de Fibonacci a la informática y la programación?
La La secuencia de Fibonacci tiene muchas aplicaciones, como algoritmos para generar números aleatorios, gráficos, árboles, algoritmos de clasificación y compresión de datos. Además, la secuencia de Fibonacci se usa en criptografía y en el análisis del rendimiento de los algoritmos.
¿Cuál es el significado de la secuencia de Fibonacci?
A menudo se se utiliza para modelar patrones de crecimiento en la naturaleza, como la ramificación de los árboles, la disposición de las hojas en un tallo y las espirales en una concha marina o una piña. También se utiliza en análisis técnico para predecir tendencias de mercado y en criptografía para generar números aleatorios.
¿Cuáles son algunos ejemplos de números de Fibonacci en la naturaleza y el arte?
La proporción áurea se encuentra en muchos fenómenos naturales, como las espirales en ciertas plantas y animales (p. ej., piñas, girasoles, conchas, etc.).
También se encuentra en ciertas estructuras, como el Partenón en Atenas, Grecia, música como la Quinta Sinfonía de Beethoven, arte como la Mona Lisa de Leonardo da Vinci y astronomía como las órbitas de los planetas alrededor de las estrellas.