Feedback

C# - Fibonacci Zahl mittels Matrix berechnen

Veröffentlicht von am 20.05.2014
(0 Bewertungen)
Mit diesem iterativen Algorithmus lassen sich Fibonacci Zahlen in O(log n) berechnen.
Dieser Algorithmus ist schneller als der normale rekursive oder iterative Algorithmus der in O(n) die Fibonacci Zahl berechnet.

Die Theorie hinter diesem Algorithmus findet ihr hier:
http://de.wikipedia.org/wiki/Fibonacci-Folge#Darstellung_mit_Matrizen
 static int fibonacci(int n)
        {
            int[,] fib= {{1,1},{1,0}};
            int[,] blu= {{1,0},{0,1}};
            int a, b, c, d;
        
            while(n > 0)
            {
                if(n % 2 != 0)
                {
                    a = blu[0, 0] * fib[0, 0] + blu[0, 1] * fib[1, 0];
                    b = blu[0, 0] * fib[0, 1] + blu[0, 1] * fib[1, 1];
                    c = blu[1, 0] * fib[0, 0] + blu[1, 1] * fib[1, 0];
                    d = blu[1, 0] * fib[0, 1] + blu[1, 1] * fib[1, 1];

                    blu[0, 0] = a;
                    blu[0, 1] = b;
                    blu[1, 0] = c;
                    blu[1, 1] = d;
                }
        
                a = fib[0, 0] * fib[0, 0] + fib[0, 1] * fib[1, 0];
                b = fib[0, 0] * fib[0, 1] + fib[0, 1] * fib[1, 1];
                c = fib[1, 0] * fib[0, 0] + fib[1, 1] * fib[1, 0];
                d = fib[1, 0] * fib[0, 1] + fib[1, 1] * fib[1, 1];

                fib[0, 0] = a;
                fib[0, 1] = b;
                fib[1, 0] = c;
                fib[1, 1] = d;

                n/=2;
            }
            return (blu[0,1]);
        }
Abgelegt unter fibonacci, fibo, folge, matrix, iterative, O(logn).

1 Kommentare zum Snippet

Koopakiller schrieb am 31.07.2015:
Ich habe mir mal den Code des Snippets genommen, etwas verändert und eine Iterator-Methode drum herum gepackt. Das Ergebnis sieht dann so aus:
http://dotnet-snippets.de/snippet/ueber-fibonacci-zahlen-iterieren/7990
 

Logge dich ein, um hier zu kommentieren!