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]

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

Nach dieser Schulung beherrschen Sie die Grundlagen des TFS. Sie erledigen administrative Aufgaben schnell und sicher.

C# Grundlagen

Die Schulung vermittelt Ihnen die Grundlagen von C# in der Arbeit mit Datentypen sowie bei Klassenbibliotheken. Sie lernen, mit Variablen umzugehen und deren verschiedene Formen zu konvertieren. 

 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!