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# Komplett

Sie kennen sich in objektorientierter Programmierung aus. Sie schreiben C++ oder Java? Und nun stehen Sie vor der Aufgabe, in C# Anwendungen zu erstellen. Das C# Komplett-Seminar verschafft Ihnen umfassende Programmierkenntnisse in dieser Sprache. Nach der Schulung entwickeln Sie selbständig Anwendungen mit C#. Sie kennen die Datentypen und Klassenbibliotheken der objektorientierten Programmiersprache C#. Der Komplettkurs setzt bei den Grundlagen von C# ein. Sie arbeiten mit Variablen und konvertieren Typen. Multithreading, Delegates, Generics sind nach dem Seminar für Sie kein Geheimnis mehr.

Visual Studio Team Foundation Server 2017/2015 (TFS) für Entwickler - Kompakt

Nach Teilnahme an dieser Schulung kennen Sie alle wesentlichen Funktionen des TFS für Entwickler. Sie setzen Software-Entwicklung mit dem Visual Studio Team Foundation Server erfolgreich um.

 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!