SD1-23-2-TéllezGonzálezJorgeLuis-Examen5

Vista previa del material en texto

FACULTAD DE INGENIERÍA 1
Examen V: Fibonacci
Jorge Luis Téllez González, 315132726
Sistemas Distribuidos - Grupo: 01
Resumen—La secuencia de Fibonacci es una serie numérica
que ha fascinado a matemáticos y programadores por igual
debido a sus múltiples propiedades matemáticas y armónicas que
impactan en múltiples campos del conocimiento. En este trabajo
exploraremos dos formas de implementar la función de Fibonacci
en Java: la primera de manera recursiva y la segunda de manera
iterativa.
Index Terms—Fibonacci, recursivo, iterativo, Java, rendimiento
I. INTRODUCCIÓN
LA sucesión de Fibonacci es una secuencia numérica quese define comenzando con los números 0 y 1, y cada
número subsiguiente es la suma de los dos números anteriores.
En una sucesión recurrente de la forma:
r1 = 1, r2 = 1, rn = rn−1 + rn−2 (1)
La secuencia continúa infinitamente, y comienza con los
siguientes valores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
El matemático italiano Leonardo de Pisa, también conocido
como Fibonacci, descubrió la sucesión de Fibonacci en el siglo
XIII mientras viajaba con su padre, quien era comerciante. Su
descubrimiento se produjo al observar cómo se reproducı́an las
parejas de conejos. Con el tiempo, se ha descubierto que esta
secuencia está presente en varios fenómenos de la naturaleza,
como la estructura espiral del caparazón de algunos moluscos
y la disposición de las hojas de algunas plantas. También se
aplica en campos como la informática y la teorı́a de juegos.
La propiedad más significativa de la sucesión de Fibonacci es
que si se considera la sucesión de cocientes de un término entre
el término anterior, se acerca cada vez más al número áureo,
también conocido como Phi (Φ), que es igual a 1+sqrt(5)/2.
Esto se refleja en la fórmula siguiente:
ĺım
n→∞
rn−1
rn
= Φ
En cuanto a otros usos, tiene aplicaciones en otras áreas clave
como en la estadı́stica y la probabilidad, donde se utiliza para
modelar el crecimiento de poblaciones y la distribución de
valores extremos en una muestra de datos.
Programar esta sucesión tiene 2 posibles caminos: una versión
recursiva y otra iterativa. La recursividad es un concepto de
programación que consiste en que una función se llame a sı́
misma de forma directa o indirecta. Es decir, una función
recursiva es aquella que se define en términos de sı́ misma.
La recursividad se utiliza para resolver problemas que se
pueden dividir en subproblemas más pequeños que tienen la
misma estructura que el problema original. De esta forma, la
función recursiva resuelve cada uno de los subproblemas, y al
combinar las soluciones de todos los subproblemas se obtiene
la solución al problema original.
function fibonacciRecursivo(n)
si n = 0 entonces
devolver 0
sino si n = 1 entonces
devolver 1
sino
devolver fibonacciRecursivo(n-1) +
fibonacciRecursivo(n-2)
fin si
fin function
Por otra parte, la técnica iterativa se refiere a solucionar el
problema a partir del uso de ciclos; estructuras repetitivas que
permiten ejecutar instrucciones dada una condición de inicio,
un cuerpo, y una condición de salida.
function fibonacciIterativo(n)
si n = 0 entonces
devolver 0
sino si n = 1 entonces
devolver 1
sino
a := 0
b := 1
para i desde 2 hasta n hacer
c := a + b
a := b
b := c
fin para
devolver b
fin si
fin function
En el contexto de la recursividad y la iteración con ciclos, es
importante considerar la complejidad computacional de ambas
soluciones. Generalmente, las soluciones con ciclos pueden
alcanzar complejidades computacionales superiores a O(n2),
mientras que la recursividad permite obtener algoritmos ca-
paces de alcanzar complejidades cercanas al orden ideal de
O(n log n). Tanto la recursividad como la iteración con ciclos
tienen sus fortalezas y debilidades, y la elección depende
del problema especı́fico y de las necesidades de eficiencia y
claridad del código.
FACULTAD DE INGENIERÍA 2
Para los propósitos del presente trabajo, analizaremos las
diferencias de ejecución entre ambas versiones del algoritmo
de Fibonacci por medio de su implementación en Java. Para
los propósitos de este prueba, se ejecutarán 100 veces ambas
versiones para comprobar el promedio de tiempo obtenido
para su ejecución de cada uno de ellos, empleando Sys-
tem.nanoTime() para realizar mediciones precisas del tiempo
transcurrido entre cada ejecución.
II. DESARROLLO
II-A. Programa desarrollado
Para ejemplificar las diferencias entre los tiempos de ejecu-
ción entre ambas técnicas se generó un programa en Java
compuesto por 3 clases: la clase principal, FBRecursivo y
FBIterativo. Para realizar la implementación y las pruebas,
se generó un menú de opciones que permite seleccionar qué
metodologı́a usar para ejecutar el algoritmo; como se observa
a continuación.
Figura 1: Ejecución del programa: selección del tipo de
ejecución.
La clase FBRecursivo, sin atributos, se encarga de calcular
recursivamente los n términos de la sucesión de Fibonacci.
Figura 2: Algoritmo de Fibonacci en formato recursivo.
Por otra parte, en la clase FBIterativo, que no cuenta con
parámetros, se encarga de calcular el n-ésimo término de la
serie por medio de un ciclo for que inicia a partir de i=2 (por la
forma en que inicia la serie) y comienza a calcular el término
siguiente a partir de la suma de los valores anteriores en la
serie.
Figura 3: Algoritmo de Fibonacci en formato iterativo.
En la clase principal, por otra parte, se empieza solicitando
al usuario la forma de calcular el algoritmo. Por medio de la
lectura de esa opción con un objeto Scanner, se emplea una es-
tructura switch para elegir qué caso ejecutar y validar si es una
opción correcta o no. En cada una de las opciones sé instancia
un nuevo objeto al que se le aplicará el respectivo método
de calcular(n), donde n es el número de términos que se
desean calcular para la sucesión de Fibonacci. Adicionalmente,
se emplea System.nanoTime() para obtener timestamps en
nanosegundos que después se trasforman en ms con el fin de
obtener un promedio de 100 ejecuciones para cada versión del
algoritmo.
Figura 4: Clase principal del programa en el switch.
II-B. Resultados
Para el desarrollo de las pruebas Considerando un promedio
de 100 ejecuciones y sus tiempos obtenidos, se llega a los
siguientes tiempos:
FACULTAD DE INGENIERÍA 3
Para n=10, la versión recursiva arroja 0.1175ms, por otra
parte, la versión iterativa obtiene 0.1077ms.
Para n=20, la versión recursiva arroja 0.1497ms, por otra
parte, la versión iterativa obtiene 0.0873ms.
Para n=30, la versión recursiva arroja 3.0183ms, por otra
parte, la versión iterativa obtiene 0.0977ms.
Para n=40, la versión recursiva arroja 329.2699ms, por
otra parte, la versión iterativa obtiene 0.10744ms.
Cabe señalar que, para evitar afectar en la medida de lo
posible el desempeño de los programas, se eliminaron las
impresiones en pantalla y solo se muestran los promedios
durante el programa principal.
III. CONCLUSIONES
Cómo se puede observar, la forma iterativa de este algoritmo
se encuentra en un nivel de eficiencia completamente superior
con respecto a su contraparte recursiva. Si bien se comentó
al inicio de este trabajo que los algoritmos recursivos suelen
presentar una ventaja frente a su contrapartes iterativas, en
este caso particular el algoritmo recursivo presenta una notable
desventaja frente a su contraparte iterativa por el hecho de que
el cálculo de los valores de la serie se realiza múltiples veces;
malgastando tiempo y recursos de memoria en consecuencia.
Este algoritmo podrı́a solucionarse por medio de un enfoque
consistente en guardar los valores ya calculados y no repetir
el cálculo de elementos de la sucesión que ya habı́an sido
calculados previamente.
Por tanto, no siempre es el caso de que los algoritmos recursi-
vos sean más rápidos que los iterativos, y su implementación
depende en gran medida de la naturaleza del problema a
resolver y la capacidadde dividirlo en sub-problemas parti-
cionables.
BIBLIOGRAFÍA
[1] UAL. “Sucesión de Fibonacci.” (), dirección: https : / /
www2 . ual . es / jardinmatema / sucesion - de - fibonacci/
(visitado 04-04-2023).
[2] Wikipedia. “Sucesión de Fibonacci.” (2023), dirección:
https: / /es .wikipedia .org/wiki /Sucesi%5C%C3%5C%
B3n de Fibonacci (visitado 04-04-2023).
[3] KeepCoding. “¿Cómo calcular el Algoritmo de Fibonacci
en Scala?” (2023), dirección: https://keepcoding.io/blog/
que-es-el-algoritmo-de-fibonacci/ (visitado 04-04-2023).
[4] M. Castañon. “Algoritmo Serie de Fibonacci Pseint.”
(2020), dirección: https : / / pseudocodigoejemplos .
com / algoritmo - serie - de - fibonacci - pseint/ (visitado
04-04-2023).
[5] Parzibyte. “Sucesión fibonacci en Java: método iterativo
y recursivo.” (2019), dirección: https://parzibyte.me/blog/
2019/02/28/sucesion- fibonacci- java- metodo- iterativo-
recursivo/ (visitado 04-04-2023).
Los créditos de las fotografı́as pertenecen a sus autores. ©
https://www2.ual.es/jardinmatema/sucesion-de-fibonacci/
https://www2.ual.es/jardinmatema/sucesion-de-fibonacci/
https://es.wikipedia.org/wiki/Sucesi%5C%C3%5C%B3n_de_Fibonacci
https://es.wikipedia.org/wiki/Sucesi%5C%C3%5C%B3n_de_Fibonacci
https://keepcoding.io/blog/que-es-el-algoritmo-de-fibonacci/
https://keepcoding.io/blog/que-es-el-algoritmo-de-fibonacci/
https://pseudocodigoejemplos.com/algoritmo-serie-de-fibonacci-pseint/
https://pseudocodigoejemplos.com/algoritmo-serie-de-fibonacci-pseint/
https://parzibyte.me/blog/2019/02/28/sucesion-fibonacci-java-metodo-iterativo-recursivo/
https://parzibyte.me/blog/2019/02/28/sucesion-fibonacci-java-metodo-iterativo-recursivo/
https://parzibyte.me/blog/2019/02/28/sucesion-fibonacci-java-metodo-iterativo-recursivo/
	Introducción
	Desarrollo
	Programa desarrollado
	Resultados
	Conclusiones