Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Fibonacci-Zahlen berechnen - dynamische Programmierung

Einige Strategien, um Algorithmen zu entwerfen, treten immer wieder auf, weil sie so erfolgreich sind - so zum Beispiel auch die Strategie, die als dynamische Programmierung bezeichnet wird.

Dynamische Programmierung

Der Begriff dynamische Programmierung ist historisch bedingt, er beschreibt unglückseligerweise nicht das Wesentliche dieser Entwurfsmethode. Eine wirklich treffende Bezeichnung ist noch niemandem eingefallen – vielleicht kommt akkumulierende Berechnung der Sache am nächsten.

Es geht bei der Berechnung nämlich darum, anfallende Ergebnisse von Teilproblemen zu speichern und für das Gesamtergebnis weiterzuverwenden.

Fibonacci-Zahlen berechnen

Ein Paradebeispiel ist die Berechnung der nn-ten Fibonacci-Zahl fnf_n. Die Fibonacci-Folge f0,f1,f2,...f_0, f_1, f_2, ... lautet

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Die Fibonacci-Zahl fnf_n berechnest du aus der Summe der beiden vorhergehenden Fibonacci-Zahlen fn1f_{n-1} und fn2f_{n-2}.

  • Um also fnf_n zu berechnen, musst du zuerst fn1f_{n-1} und fn2f_{n-2} berechnen,

  • um fn1f_{n-1} zu berechnen, musst du fn2f_{n-2} und fn3f_{n-3} berechnen,

  • um fn2f_{n-2} zu berechnen, musst du fn3f_{n-3} und fn4f_{n-4} berechnen

  • usw.

Du siehst, dass du fn2f_{n-2} an mehreren Stellen benötigst, ebenso fn3f_{n-3} usw. Statt diese Werte immer wieder von vorne zu berechnen, berechnest du sie nur einmal und speicherst sie für eine spätere Weiterverwendung.

Iterative Berechnung: Zwischenergebnisse speichern

Du füllst hierzu eine Liste ff nach und nach mit der Fibonacci-Folge, indem du schon berechnete Fibonacci-Zahlen in der Liste speicherst.

Du initialisierst die Liste mit [1,1][1, 1] und berechnest dann jeweils den nächsten Wert, indem du einfach die beiden letzten berechneten Werte f[1]f[-1]und f[2]f[-2] aus der Liste ausliest, addierst und diesen neuen Wert an die Liste anhängst.

In der Programmiersprache Python sieht das so aus:

# berechnet die Fibonacci-Folge f[0],...,f[n]
def fibo(n):
    f=[1, 1]
    for _ in range(n-1):
        f+=[f[-1]+f[-2]]
    return f[n]

Das Ganze beansprucht nur lineare Zeit, also nn Schritte für die nn-te Fibonacci-Zahl.

Wenn dich nur die nn-te Fibonacci-Zahl fnf_n interessiert, dann brauchst du auch nicht die ganze Liste zu speichern, weil du ja immer nur die beiden letzten Werte f[1]f[-1] und f[2]f[-2] der Liste benötigst. Du speicherst die jeweiligen letzten beiden Werte einfach in zwei Variablen ff und gg.

# berechnet die n-te Fibonacci-Zahl (iterativ)
def fibo(n):
    f, g = 1, 1
    for _ in range(n-1):
        f, g = g, f+g
    return g

Rekursive Berechnung

Wenn du dagegen jede Fibonacci-Zahl jedes Mal von vorne berechnest, benötigst du exponentielle Zeit, etwa in der folgenden rekursiven Implementierung:

# berechnet die n-te Fibonacci-Zahl (rekursiv)
def fibo(n):
    if n==0 or n==1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

Achtung: Don't use it. Dieses Programm ist ein Beispiel dafür, wie du es nicht machen solltest.

Programme ausprobieren

Probiere einmal die iterative und die rekursive Berechnung aus.

Bereits bei fibo(35) tritt dem rekursiven Programm der Schweiß auf die Stirn…

Für die iterative Implementierung ist selbst fibo(100) kein Problem (Ergebnis: 573147844013817084101)

Mit der angegebenen rekursiven Implementierung ist die Berechnung von fibo(100) dagegen völlig undurchführbar.

 

Beispiele für dynamische Programmierung

Es gibt eine ganze Reihe von Algorithmen, die auf dynamischer Programmierung bzw. akkumulierender Berechnung basieren. Meist wird dabei ein zweidimensionales Array mit Zwischenergebnissen gefüllt.

Einfach zu verstehen ist die Berechnung der Editierdistanz, um die Ähnlichkeit von zwei Wörtern zu bestimmen (zum Beispiel von DSCHUNGEL und DUSCHGEL).

Weitere Beispiele sind der Floyd-Algorithmus zur Berechnung der kürzesten Wege zwischen allen Knoten in einem Graphen sowie der CYK-Algorithmus zur Erkennung von Wörtern einer kontextfreien Grammatik.


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?