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
GFU-Schulungen  [Anzeige]

VB.NET 2017/2015/2013 Einführung

Das Seminar befähigt Sie zur eigenständigen Entwicklung von anwenderorientierten Programmen in VB.NET, worin auch der Einsatz von Datenbanken enthalten ist.

VB.NET Aufbau

Sie verfügen nach der Schulung über fundierte Kenntnisse in der Arbeit mit objektorientierten Modellen in VB.NET und können wiederverwendbare Komponenten eigenständig erzeugen.

 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!