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]

C# 2017/2015/2013 Grundlagen

Nach Abschluss des Kurses sind Ihnen die Datentypen und Klassenbibliotheken von C# bekannt. Außerdem sind Sie in der Lage, mit Variablen umzugehen und deren Typen zu konvertieren. Sie definieren Namespaces und setzen diese ein, Sie erstellen eigene Klassen  und bauen Trouble Shooting ein.

XML und .NET Überblick

Um auf dem neuesten Wissensstand zu sein, sollten Sie unser aktuelles ASP .NET Komplett Seminar belegen.
Nach dem Seminar kennen Sie die wichtigsten Strömungen in der Software-Technologie

 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!