Algorithmensammlung: Zahlentheorie: Fibonacci-Folge

Aus Wikibooks
Wechseln zu: Navigation, Suche

Algorithmensammlung: Zahlentheorie

Programme zur Berechnung des n-ten Wertes Fn der  Fibonacci-Folge aus den Startwerten F0 = 0 und F1 = 1

Basic C64[Bearbeiten]

Fibonaccizahlen in binärer Darstellung
 5 REM FIBONACCI 
 10 A = 1
 20 B = 1
 30 FOR X = 1 TO 20
 40 PRINT A
 50 PRINT B
 60 A = A + B
 70 B = A + B
 80 NEXT

Gibt es ein Programm mit nur einer Variablen A ?

 10 PHI = (1 + 5^0.5) / 2
 20 FOR N = 1 TO 20
 30 FIB = INT(((PHI^N - (1-PHI)^N) / 5^0.5)+0.5)
 40 PRINT N,FIB
 50 NEXT

Wegen Rundungsfehlern ist die Folge nicht ganz korrekt.

Eine Variante mit einem Array

 10 REM FIBONACCI FOLGE
 20 CLS
 30 REM DER ARRAY F WIRD MIT DEN FIBONACCI ZAHLEN GEFUELLT
 40 DIM F(50) 
 50 F(0) = 0
 60 F(1) = 1
 70 N = 1
 80 LET F(N+1) = F(N) + F(N-1)
 90 LET N = N + 1
 100 PRINT F(N);", ";
 110 REM STOP NACH 50 ZAHLEN
 120 IF N < 50 THEN GOTO 80

Basic X11[Bearbeiten]

 REM FIBONACCI 
 A = 1 
 B = 1 
 FOR X = 1 TO 20 
 PRINT A 
 PRINT B 
 A = A + B 
 B = A + B 
 NEXT

Visual Basic for Applications (VBA)[Bearbeiten]

Public Function Fibonacci(n As Long) As Variant
    Dim i As Long, a, b
    
    a = 0 ' =F(0)
    b = 1 ' =F(1)
    
    For i = 2 To n Step 2
        ' Abwechselnd a und b erhöhen
        a = a + b
        b = a + b
    Next i
    
    ' Zutreffenden Wert zurückgeben
    Fibonacci = IIf(n Mod 2 = 0, a, b)
End Function

Der Rückgabewert ist je nach Größe vom Datentyp Long oder Double. Die Funktion enthält keine Fehlerbehandlung bei n < 0.

Haskell[Bearbeiten]

Werden Matrizen der Form

addiert oder multipliziert, ergibt sich erneut eine Matrix dieser Form. Für die Darstellung solcher Matrizen ist die zweite Zeile redundant. Außerdem ist

.
data M r = M !r !r deriving (Eq, Show)

instance Num r => Num (M r) where
    fromInteger n = M (fromInteger n) 0
    M a b + M c d = M (a+c) (b+d)
    M a b - M c d = M (a-c) (b-d)
    M a b * M c d = M (a*c+b*d) (a*d+b*c+b*d)
    abs = undefined
    signum = undefined
    
fib :: Num r => Integer -> r
fib n = b where
    M a b = M 0 1 ^ n

Hier wird eine Num-Instanz für Matrizen der angegebenen Form definiert. Diese wird von der vordefinierten Exponentiation (^) :: (Integral b, Num a) => a -> b -> a benutzt, welche ihrerseits als  binäre Exponentiation implementiert ist.

Julia[Bearbeiten]

Rekursiver naiver Fibonacci-Algorithmus in Julia.

function fib(n)
    if n < 2
        return n
    else
        return fib(n-1) + fib(n-2)
    end
end

Python[Bearbeiten]

Die folgende Implementierung ist rekursiv:

# Getestet unter Python 3.4, sollte mit allen 3.x-Versionen funktionieren
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Diese Funktion stimmt direkt mit der Definition der Folge überein und ist somit gut für Lernzwecke geeignet. Die Geschwindigkeit ist allerdings nicht ausreichend für einen praktischen Einsatz. Dieser Mangel lässt sich z. B. mit  Memoisation teilweise ausmerzen. Sobald die Zahlen allerdings etwas größer werden, ist die direkte Berechnung der Werte über die  Formel von Moivre-Binet weitaus schneller:

# Getestet unter Python 3.4, sollte mit allen 3.x-Versionen funktionieren
import math


def moivre_binet(n):
    näherung = (1/math.sqrt(5)) * (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**n)
    return int(abs(näherung))
    # nötig wegen möglicherweise irritierender Rundungsfehler durch mangelhafte 
    # maschineninterne Darstellung der irrationalen Wurzel aus 5

Geschwindigkeitstechnisch lässt sich da auch noch dran feilen, dazu lese man den dazugehörigen Wikipedia-Artikel, für die ersten Schritte sollte der Quelltext aber genügen.