Publiqué en mi otro blog sobre mates, física y otros temas un post acerca de la sucesión y la espiral de Fibonacci y gustándome como me gustan las funciones recursivas, no podía quedar atrás una implementación en C# de esta sucesión.
Para ellos, en este artículo expondré diversos métodos para calcular la sucesión de Fibonacci a los cuales se les pasará como argumento el valor de n de la función y que a continuación os muestro:
El primero de ellos será mediante la función recursiva. Este es el método natural de cálculo de la sucesión
espiral01.png

        public double GetRecursiveFunction(int n)
        {
            if ((n == 0) || (n == 1)) return 1;
            else return GetRecursiveFunction(n -1) + GetRecursiveFunction(n - 2);
        }

Este método tiene el inconveniente de la complejidad recurrente que se aplica sobre su cálculo, es decir que si solicitamos el valor del elemento 39, haríamos una llamada a GetRecursiveFunction(39) , la cual una vez dentro de esta, llamará a los elementos GetRecursiveFunction(38) y GetRecursiveFunction(37) de la misma función para sumarlos, y estos a su vez a sus dos anteriores hasta llegar a GetRecursiveFunction(0) o GetRecursiveFunction(1) devolviendo el valor de 1 a partir de entonces comenzará a sumar. Esto significa que para cada cálculo se realiza la suma de las iteraciones de los dos elementos anteriores más 1. Si para n igual a 6 se llama a la función 15 veces y para n igual a 7, 25 veces, para n igual a 8 se llamaría a la función 15 más 25 y más 1 de la primera llamada. Esto supone un gasto de recursos enorme ya que para n igual a 40 el número de iteraciones se elevaría a la suma de 78.176.337, 126.491.971 y 1, un total de 204.668.309 iteraciones para obtener el elemento 40 de la sucesión; en tiempo, aproximadamente unos 8 segundos en un dual core con SSD. A todos los efectos, no es eficiente.El siguiente método de cálculo de la sucesión de Fibonacci, será el de la función general extraída mediante la ecuación de recurrencia y sus raíces.espiral14.png

Esta función tiene como inconveniente la precisión y muestro el por qué. En primero lugar creo una propiedad de solo lectura para calcular ϕ (Phi) o el número áureo, el cual es igual a
Espiral04.png
provocando una falta de precisión; por otra parte el uso de la exponenciación a n, lo que a su vez provoca que un número excesivamente grande, sea tratado exponencialmente. Todo esto unido para un n grande, nos hace obtener un número extremadamente aproximado a cualquier elemento de la sucesión, pero sin llegar a serlo, por lo que debemos auxiliarnos de la función de redondeo para obtener unos resultados satisfactorios. A pesar de los complejos cálculos, es muy rápida.

        public double Phi
        {
            get
            {
                return (1 + Math.Sqrt(5)) / 2;
            }
        }

        public double GetGeneralFuncion(int n)
        {
            double result = (double)((Math.Pow(Phi, n) - Math.Pow((1 - Phi), n)) / Math.Sqrt(5));
            return Math.Round(result);
        }

La siguiente función es la iterativa. Esta parte de los dos primeros valores 0 y 1 y va obteniendo el siguiente en cada iteración, sencilla y muy rápida. No tiene problemas de redondeo. El inconveniente que tiene es que no almacena los valores anteriores, sino que simplemente los calcula.

        public double GetIterativeFunction(int n)
        {
            double f0 = 0;
            double f1 = 1;
            for (int i = 1; i < n; i++)
            {
                f1 = f0 + f1;
                f0 = f1 - f0;
            }

            return f1;
        }

Por último, una función parecida a la iterativa pero en la cual quedan almacenados los elementos de la sucesión mediante un objeto List, de este modo se asignan los dos primeros valores y se van generando los siguientes añadiéndolos a la lista según se van calculando.

        public List numbers = new List();
        public void GetArrayListFunction(int n)
        {
            numbers.Clear();
            numbers.Add(0);
            numbers.Add(1);
            for (int i = 2; i < n; i++)
            {
                numbers.Add(numbers[i - 1] + numbers[i - 2]);
            }
        }

Una vez que hemos visto las funciones para obtener los elementos de la sucesión de Fibonacci, vamos a calcular la espiral de Fibonacci mediante dos métodos, XAML y código puro y duro.
Si lo hacemos con XAML, creamos un objeto Path y dentro de Path.Data con el siguiente código:

        <Path Stroke="Red" StrokeThickness="2" >
        <Path.Data>
            <PathGeometry>
                <PathGeometry.Figures>
                    <PathFigureCollection>
                            <PathFigure StartPoint="610,610">
                                <PathFigure.Segments>
                                <PathSegmentCollection>
                                        <ArcSegment Point="600, 600" Size="10 10" />
                                        <ArcSegment Point="590, 610" Size="10 10" />
                                        <ArcSegment Point="610, 630" Size="20 20" />
                                        <ArcSegment Point="640, 600" Size="30 30" />
                                        <ArcSegment Point="590, 550" Size="50 50" />
                                        <ArcSegment Point="510, 630" Size="80 80" />
                                        <ArcSegment Point="640, 760" Size="130 130" />
                                        <ArcSegment Point="850, 550" Size="210 210" />
                                        <ArcSegment Point="510, 210" Size="340 340" />
                                        <ArcSegment Point="-40, 760" Size="550 550" />
                                        <ArcSegment Point="850, 1650" Size="890 890" />
                                        <ArcSegment Point="2290, 210" Size="1440 1440" />
                                    </PathSegmentCollection>
                            </PathFigure.Segments>
                        </PathFigure>
                    </PathFigureCollection>
                </PathGeometry.Figures>
            </PathGeometry>
        </Path.Data>
        </Path>

Lo que hacemos es crear objetos ArcSegment como tantos elementos de la sucesión queramos incluir, pero su límite es evidente, por lo que podríamos crear un método genérico que creara una espiral en base al argumento n, de modo que llamamos por ejemplo a la función iterativa basada en List y con los datos almacenados en esta lista, usarlos para crear tanto objetos ArcSegment como elementos tenga la sucesión. El problema es que la sucesión de Fibonacci tiene un crecimiento alto y la espiral desaparecerá rápidamente de nuestra ventana, pero calcular, calcula correctamente la espiral.
He creado dos propiedades para el centro de la espiral, x e y un ángulo como variable angular. (También podríamos haber usado la función polar de la espiral, pero he escogido esta para mostrar cada arco de segmento).
Para seleccionar el centro de cada arco, he ingeniado un método que mediante el seno y coseno del ángulo de la función, sume o reste los valores de la sucesión y asigne correctamente el centro.
Una vez creados los arcos, los añadimos al objeto Figure y como en XAML vamos añadiendo a la colección.

        public double CenterX { get; set; } = 512;
        public double CenterY { get; set; } = 384;
        public double Angle { get; set; } = Math.PI;

        void create(int n)
        {

            Fibonacci fib = new Fibonacci();
            fib.GetArrayListFunction(n);

            PathGeometry pathGeometry = new PathGeometry();

            PathFigure figure = new PathFigure();
            figure.StartPoint = new Point(CenterX, CenterY);

            for (int i =0; i < fib.numbers.Count; i++)
            {
                double sign = (i % 2 == 0 ? 1 : -1);
                double x = sign==1? Math.Round(Math.Cos(Angle)) : Math.Round(Math.Sin(Angle));
                double y = sign == 1 ? Math.Round(Math.Sin(Angle - Math.PI / 2)) : Math.Round(Math.Cos(Angle-Math.PI/2));
                double a = Math.Round(fib.numbers[i] * sign * x);
                double b = Math.Round(fib.numbers[i] * sign * y);

                CenterX = CenterX + a;
                CenterY = CenterY + b;

                ArcSegment arcSegment = new ArcSegment(new Point(CenterX, CenterY),
                    new Size(fib.numbers[i], fib.numbers[i]),
                    0,false,SweepDirection.Counterclockwise,true);

                figure.Segments.Add(arcSegment);
                Angle += Math.PI/2;

            }

            pathGeometry.Figures.Add(figure);
            path.Data = pathGeometry;
            path.Stroke = Brushes.Green;
        }

el resultado en ambos casos

fib02.png
y esto es todo,
saludos!
Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s