Feedback

C# - Über Fibonacci Zahlen iterieren

Veröffentlicht von am 31.07.2015
(0 Bewertungen)
Diese kleine Struktur enthält alles um einfach über die Fibonacci Zahlen zu iterieren. Dabei kann auch ein nullbasierter Index angegeben werden mit dem gestartet werden soll. Der dort dahinter stehende Code stammt aus diesem Snippet: http://dotnet-snippets.de/snippet/fibonacci-zahl-mittels-matrix-berechnen/3866

Benötigte Namespaces
System.Collections.Generic;
using System.Numerics

Zusätzlich benötigte Assembly
System.Numerics

Beispielanwendung
static void Main(string[] args)
{
foreach (var fib in Fibonacci.Enumerate())
{
Console.WriteLine(fib);
Thread.Sleep(500);
}
}
/// <summary>
/// Stellt Methoden bereit um über die Liste der Fibonacci Zahlen zu iterieren.
/// </summary>
public struct Fibonacci
{
    #region static

    /// <summary>
    /// Durchläuft alle Fibonacci Zahlen ab 1 bzw. dem angegebenen Nullbasierten Index.
    /// </summary>
    /// <param name="start">Der Nullbasierte Index der Fibonacci Zahl mit der gestartet werden soll.</param>
    /// <returns>Eine Auflistung aller Fibonacci Zahlen ab 1 bzw. dem angegebenen Nullbasierten Index.</returns>
    public static IEnumerable<Fibonacci> Enumerate(uint start = 0)
    {
        BigInteger a, b;
        FibonacciAtPosition(start, out a, out b);

        yield return new Fibonacci(start++, a);
        while (true)
        {
            yield return new Fibonacci(start++, b);
            var tmp = a;
            a = b;
            b = tmp + b;
        }
    }

    /// <summary>
    /// Berechnet 2 aufeinander folgende Fibonacci Zahlen an der angegebenen Position.
    /// </summary>
    /// <seealso href="http://dotnet-snippets.de/snippet/fibonacci-zahl-mittels-matrix-berechnen/3866"/>
    static void FibonacciAtPosition(uint position, out BigInteger outA, out BigInteger outB)
    {
        ++position;//position is zero based, the algorithm is not
        BigInteger[,] fib = { { 1, 1 }, { 1, 0 } };
        BigInteger[,] blu = { { 1, 0 }, { 0, 1 } };

        while (position > 0)
        {
            if (position % 2 != 0)
                blu = ProcessMatrix(blu, fib);

            fib = ProcessMatrix(fib, fib);

            position /= 2;
        }
        outA = blu[0, 1];
        outB = blu[0, 0];
    }

    static BigInteger[,] ProcessMatrix(BigInteger[,] blu, BigInteger[,] fib)
    {
        return new BigInteger[,]
        {
            {
                blu[0, 0] * fib[0, 0] + blu[0, 1] * fib[1, 0],
                blu[0, 0] * fib[0, 1] + blu[0, 1] * fib[1, 1],
            },
            {
                blu[1, 0] * fib[0, 0] + blu[1, 1] * fib[1, 0],
                blu[1, 0] * fib[0, 1] + blu[1, 1] * fib[1, 1],
            }
        };
    }

    #endregion

    #region instance

    /// <summary>
    /// Ruft die Position der Fibonacci Zahl ab.
    /// </summary>
    public uint Position { get; private set; }
    /// <summary>
    /// Ruft die Fibonacci Zahl ab.
    /// </summary>
    public BigInteger Number { get; private set; }

    private Fibonacci(uint position, BigInteger number)
        : this()
    {
        this.Position = position;
        this.Number = number;
    }

    /// <summary>
    /// Ruft eine Zeichenfolgendarstellung der Fibonacci Zahl mit ihrem Index ab.
    /// </summary>
    public override string ToString()
    {
        return string.Format("{0}: {1}", this.Position, this.Number);
    }

    #endregion
}
Abgelegt unter Fibonacci, Iterator, LINQ.

Kommentare zum Snippet

 

Logge dich ein, um hier zu kommentieren!