Analisis de algoritmos generadores de la secuencia de fibonacci

Análisis de Algoritmos Generadores de la Secuencia de Fibonacci
Benemérita Universidad Autónoma de Puebla Maestría en Ciencias de la Computación Análisis y diseño de Algoritmos

Catedrático: Dr. Abraham Sánchez López Alumno: David Núñez Ramírez

Análisis de Algoritmos de Generación de la Secuencia de Fibonacci

2

Introducción
La sucesión de Fibonacci es la secuencia infinita de losnúmeros naturales 1, 1, 2, 3, 5, 8, 13…, en la que cada uno de ellos es el resultado de la suma de los dos anteriores. El genio matemático Leonardo Fibonacci nacido en Italia en 1170 la describió en su libro Liber Abaci como la solución a un problema de la cría de conejos: “Un hombre tenía una pareja de conejos juntos en un lugar cerrado y desea saber cuántos son creados a partir de este par en unaño teniendo en cuenta que su naturaleza es parir otro par en un mes, y en el segundo mes los nacidos comienzan a parir también”. Los números de la secuencia de Fibonacci pueden generarse de diversas maneras. Cabe destacar que en cualquier valor de más de 3 la proporción entre números correlativos de la cadena de Fibonacci es de 1,618 o número dorado, cifra también llamada relación dorada o relacióndivina. Es un número irracional y se lo representa por la letra griega φ (fi). De manera natural la solución del problema se vislumbra recursiva, sin embargo existen otro tipo de implementaciones que pueden superar este comportamiento.

Objetivos
El objetivo de este proyecto es la evaluación de cinco algoritmos de generación de los números de la secuencia de Fibonacci tomando en cuenta sutiempo de ejecución y el número de funciones que se ejecutan para obtener dicha secuencia.

Metodología
Se diseño un programa en C# cuya tarea fue medir el tiempo de ejecución y el número de funciones ejecutadas de cada algoritmo de generación de los números de la secuencia de Fibonacci. El usuario proporciona el elemento de la secuencia de Fibonacci que desea encontrar y el programa devuelve dichasecuencia en un cuadro de despliegue. La información referente al tiempo de ejecución y funciones realizadas se guardan en un archivo de Excel que contiene una grafica con la información obtenida. El usuario puede elegir el tipo de algoritmo que quiere utilizar para generare la secuencia. Las pruebas se realizaron en una computadora personal con 2 GBytes de memoria RAM y un procesador de 2.4 GHz.Resultados
Durante el análisis práctico de los algoritmos se presentaron ciertas dificultadas provenientes del tipo de PC utilizada para realizar las pruebas y el framework elegido para desarrollar la aplicación. El menor intervalo de medición proporcionado por la propiedad del objeto de tipo TimeSpan llamada TotalMilliseconds es de 15.5 milisegundos dentro del lenguaje C#, por lo que lasevaluaciones de los mejores casos fueron desplegados como 0 en su tiempo medido por ser solo recorridos a los arreglos. Para los algoritmos iterativos, el
11 de diciembre de 2009

Análisis de Algoritmos de Generación de la Secuencia de Fibonacci

3

valor de la secuencia de Fibonacci es correcta hasta el término numero 47, para términos mayores a dicho numero la ejecución devuelve númerosnegativos. Comportamiento que se atribuye al uso del tipo de datos entero.

Algoritmo utilizando la función generatriz (numero de oro)
La secuencia de Fibonacci es de naturaleza recursiva y se define como:

Al resolver la ecuación de recurrencia obtenemos la siguiente función generatriz:

Donde

es la razón dorada, que se define de la siguiente manera:

El algoritmo implementado para elcálculo de los números de la secuencia de Fibonacci usando esta función generatriz es el siguiente:
public class FibonacciFuncionGeneratriz:Fibonacci { double RAZON_DORADA = (1.0 + Math.Sqrt(5.0)) / 2.0; public override int Calcular(int n) { _operaciones++; return (int)((Math.Pow(RAZON_DORADA, n) – Math.Pow(-RAZON_DORADA, -n)) / Math.Sqrt(5)); } }

Este algoritmo es de complejidad O(1) dado...