Frage 23

Programmierung mit Python

Berechnung der Fibonacci-Folge

Einleitend ist die Rechenvorschrift in Erinnerung zu rufen, mit der die Werte der Fibonacci-Folge berechnet werden. Es sind gegeben:

• Der Wert des ersten Folgenelements
• Der Wert des zweiten Folgenelements
• Eine Formel, mit der aus den beiden zuletzt berechneten Folgenelementen das nachfolgende Folgenelement berechnet wird.

Die lehrbuchkonforme Fibonacci-Folge verwendet für ihre beiden Startwerte den Wert 1:

a0 = 1
a1 = 1
an = an-1 + an-2

Um ein noch unbekanntes Folgenelement zu berechnen, benötigt man also immer die beiden zuletzt bestimmten Folgenelemente. Alle anderen Folgenelemente werden nicht benötigt.

Das folgende Programm macht sich den eben festgestellten Sachverhalt zunutze:

• Es werden nur die beiden zuletzt berechneten Folgenelemente gespeichert, also jene, die für die Weiterführung der Rechnung noch benötigt werden.
• Die Speicherung der noch benötigten Werte geschieht in den Variablen a0 und a1.
• Nach der Berechnung eines weiteren Folgenelements wird der in a0 festgehaltene Wert nicht mehr benötigt. Weiterhin benötigt werden die Werte a1 sowie der neu berechnete Wert a2.
• Um die Rechnung in einer Wiederholungsanweisung weiterführen zu können, überträgt man den Wert von a1 in die Variable a0 und sodann den Wert von a2 in die Variable a1. Diese Umspeicherung zweier Werte ist die Kernidee des nachfolgenden Programms.

a0 = 1
a1 = 1
print("Berechnung der Fibonacci-Folge")
print("Bitte geben sie die obere Schranke ein:")
n = int(input())
print(a0)
print(a1)
while (a0 + a1) < n:
    a2 = a0 + a1
    print(a2)
    a0 = a1
    a1 = a2

Die Eingabe einer negativen Zahl ist hier unschädlich; für negative Werte der Variablen n wird die Schleife niemals durchlaufen. Gleichwohl könnte man mehr leisten und den Benutzer auf eine wohl fehlerhafte Eingabe aufmerksam machen.