studyklar
GdI 1 · Übungsblatt 10 · Aufgabe 2

Fibonacci-Zahlen: Kaninchenpaare von Hand und rekursiv in Java

Wie viele Kaninchenpaare gibt es nach n Jahren? Die Antwort sind die Fibonacci-Zahlen. Jede ist die Summe der beiden davor. In a) rechnen wir f(5) und f(10) von Hand aus. In b) schreiben wir eine Java-Methode fib, die sich selbst aufruft. Rechts steht in a) die Reihe der Zahlen, in b) der Baum aller Aufrufe für ein kleines Beispiel. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 10.2

Leonardo Fibonacci hat 1202 die Frage nach der Anzahl an Kaninchenpärchen untersucht. Unter der Annahme, dass im Jahr 1 mit einem Paar begonnen wird, jedes Pärchen vom zweiten Jahr an ein weiteres Pärchen Nachwuchs bekommt und die Kaninchen unendlich lange leben, wie viele Paare gibt es nach n Jahren? Die Populationsgröße f(n) kann in diesem Fall durch die sogenannten Fibonacci-Zahlen rekursiv ausgedrückt werden:

f(n)={0fu¨r n=01fu¨r n=1f(n−1)+f(n−2)fu¨r n>1f(n) = \begin{cases} 0 & \text{für } n = 0 \\ 1 & \text{für } n = 1 \\ f(n-1) + f(n-2) & \text{für } n > 1 \end{cases}

a) Berechnen Sie f(5) und f(10) ohne Zuhilfenahme eines Computers!

b) Ergänzen Sie das in der Datei A10_2.java vorgegebene Java-Programm A10_2 um die rekursive Methode fib derart, dass die Populationsgröße f(n) korrekt ermittelt wird!

Die vorgegebene Datei A10_2.java:

class A10_2 {    // Fibonacci-Zahlen rekursiv berechnen     //    // Fügen Sie die Methode fib hier ein.    //      public static void main (String[ ] args) {         Out.print("Geben Sie eine Ganzzahl n größer oder gleich 0 ein: ");        int n = In.readInt();        Out.println();        Out.println("f(" + n + ") = " + fib(n));        Out.println();    }}

Die Formel sagt, wie man f(n) bekommt. Für n = 0 und n = 1 steht der Wert direkt da. Für jedes größere n braucht man zwei kleinere Werte: f(n − 1) und f(n − 2). Eine Formel, die auf sich selbst zurückgreift, heißt rekursiv.

In a) werden die Werte von unten nach oben ausgerechnet: f(2), f(3), … bis f(10). In b) soll die Methode fib die Formel wörtlich umsetzen: Sie ruft sich selbst mit kleinerem n auf.

Merke: Eine rekursive Methode braucht zwei Dinge. Einen Basisfall, der ohne neuen Aufruf ein Ergebnis liefert. Und einen Rekursionsfall, der die Aufgabe auf kleinere Aufgaben derselben Art zurückführt.
  1. a) Die Formel lesen.
  2. a) f(2) bis f(5) ausrechnen.
  3. a) Weiter bis f(10).
  4. b) Den Kopf der Methode fib in die Vorlage setzen.
  5. b) Die Basisfälle n = 0 und n = 1.
  6. b) Der Rekursionsfall.
  7. b) Der Ablauf für fib(4).
  8. b) Testläufe mit n = 5 und n = 10.
  9. Ergänzung: warum fib für großes n langsam wird.

Die Formel lesen

Startwerte und die Regel für alle n ab 2
f(n)={0fu¨r n=01fu¨r n=1f(n−1)+f(n−2)fu¨r n>1f(n) = \begin{cases} 0 & \text{für } n = 0 \\ 1 & \text{für } n = 1 \\ f(n-1) + f(n-2) & \text{für } n > 1 \end{cases}

Die ersten zwei Zeilen der Formel sind die Startwerte: f(0) = 0 und f(1) = 1. Im Jahr 1 gibt es also ein Paar.

Die dritte Zeile gilt ab n = 2. Sie hat zwei Teile. f(n − 1): Alle Paare aus dem Vorjahr leben weiter. f(n − 2): Jedes Paar, das schon zwei Jahre vorher da war, ist alt genug und bekommt ein neues Paar. Zusammen ergibt das die Paare im Jahr n.

f(2) bis f(5)

Jede Zeile nutzt die zwei Ergebnisse davor
f(2)=f(1)+f(0)=1+0=1f(3)=f(2)+f(1)=1+1=2f(4)=f(3)+f(2)=2+1=3f(5)=f(4)+f(3)=3+2=5\begin{aligned} f(2) &= f(1) + f(0) = 1 + 0 = 1 \\ f(3) &= f(2) + f(1) = 1 + 1 = 2 \\ f(4) &= f(3) + f(2) = 2 + 1 = 3 \\ f(5) &= f(4) + f(3) = 3 + 2 = \mathbf{5} \end{aligned}

Für f(2) braucht man f(1) und f(0), beide sind bekannt. Danach ist f(2) bekannt, und damit f(3). So geht es Zahl für Zahl weiter: Jede neue Zahl ist die Summe der zwei Zahlen davor. Nach vier Additionen steht f(5) = 5 da.

Noch 8 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Abbildung 1a) f(5) und f(10) von Hand

von unten nach oben addieren

f(0)0
f(1)1
f(2)?
f(3)?
f(4)?
f(5)?
f(6)?
f(7)?
f(8)?
f(9)?
f(10)?
LegendeAufrufbaum von fib(4).