faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Übungen 3: Aufrufbäume ======

{{:aufgabe.png?nolink  |}}
=== (A1) Pascalsches Dreieck ===
{{ :faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:pascaltriangleanimated2.gif|}}((https://commons.wikimedia.org/wiki/File:PascalTriangleAnimated2.gif))


Beim Pascalschen Dreieck werden die jeweils oberhalb liegenden Felder addiert und ergeben das darunter liegende Feld, wie in der Animation rechts zu sehen ist. 

Man kann eine rekursive Funktion implementieren, die den Wert des Feldes in Zeile ''z'' und Spalte ''s'' des Pascalschen Dreiecks berechnet: ''pascal(int z, int s): int''.

(A) Implementiere ''pascal(int z, int s): int''.

++++ Tipp 1 | Ein mögliches Codegerüst könnte so aussehen:

<code java>
public int pascal(int z, int s)
    {
       if (  ) {
           return 1; 
       } else {
           return pascal( , );
       }
    }
</code>
++++

++++ Tipp 2 | 

  * Der Basisfall tritt immer dann ein, wenn das Element in Zeile 0 oder 1 oder in Spalte 0 oder z ist. Dann wird 1 zurückgegeben.
  * Im Rekursionsfalll wird ''pascal(z,s)'' zwei mal aufgerufen, nämlich so, das die beiden oberhalb liegenden Felder addiert werden: ''return pascal( , ) + pascal ( , )'' - was muss da als Argument in den Aufrufen stehen? 
++++

++++ Lösungsvorschlag | 

<code java>
public int pascal(int z, int s)
    {
        if ( z==0 || z==1 || s==0 || s==z ) {
            return 1; 
        } else {
            return pascal(z-1, s-1) + pascal(z-1,s);
        }
    }
</code>
++++

Die rekursiven Aufrufe können in einem **Aufruf-Baum** veranschaulicht werden, hier am Beispiel ''pascal(3,2)'' (Zählung von Zeile und Spalte beginnen in der Implementation des Lösungsvorschlags bei 0, d.h. das Element an der Spitze des Dreiecks ist ''pascal(0,0)=1''):

{{ :faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:pascal.drawio.png |}}


(B) Zeichne den Aufrufbaum für den Aufruf ''pascal(4,3)''.

----  
{{:aufgabe.png?nolink  |}}
=== (A2) Ficonacci mit Baum ===



Die Fibonacci-Funktion (auch als Fibonacci-Folge bezeichnet) ist definiert als:

{{:faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:bildschirmfoto_vom_2023-02-05_17-47-15.png?400|}}


Die ersten Werte der Fibonacci-Funktion sind 0, 1, 1, 2, 3, 5, 8, 13, …
Die Definition kann einfach in eine rekursive Methode übersetzt werden:
<code>
fib(n: int): int
  wenn n ≤ 1:
    gib n zurück
  sonst:
    gib fib(n-1) + fib(n-2) zurück
</code>

(A) Gib die vier Werte der Fibonacci-Folge an, die auf das Folgenglied 13 folgen.

(B) Stelle die ausgeführten Methodenaufrufe bei der Ausführung von ''fib(4)'' als
Baum dar.

(C) Begründe, warum die Anzahl der Methodenaufrufe für ''fib(n)'' weniger als 2<sup>n+1</sup> beträgt.

(D) Implementiere eine Methode ''fibIterativ(n: int): int'', die dasselbe Ergebnis wie ''fib'' berechnet, die aber ohne Rekursion arbeitet.

----  
{{:aufgabe.png?nolink  |}}
=== (A3) Fibonacci dynamisch-rekursiv (LF) ===

Bei manchen Problemen kann man Zeit sparen, indem man geeignete Zwischenergebnisse abspeichert und später wiederverwendet. Diese Technik wird als dynamische Programmierung oder Memoisation bezeichnet:

<code>
int[] cache;

fibDyn(n: int): int
  wenn n ≤ 1:
    gib n zurück
  cache = Array vom Typ int und der Länge n+1
  cache[0] = 0;
  cache[1] = 1;
  wiederhole für i von 2 bis n:
    cache[i] = -1;
  gib lookup(n) zurück
  
lookup(n: int): int
  wenn cache[n] < 0:
    cache[n] = lookup(n-1) + lookup(n-2);
  gib cache[n] zurück
</code>

(A) Die Methode ''fibDyn(4)'' wird aufgerufen. Stelle die ausgeführten Methodenaufrufe als Baum dar. Gib bei jedem Knoten den Inhalt des Arrays cache an, nachdem der jeweilige Methodenaufruf beendet ist.

(B) Begründe, warum die dynamische Implementierung effizienter ist als die rekursive von oben.


++++ Lösung A |

{{ :faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:bildschirmfoto_vom_2023-02-05_18-39-57.png |}}
++++


++++ Lösung B | 
Die ursprüngliche rekursive Implementation berechnet fast alle Funktionswerte mehrfach. Durch die Verwendung
des cache-Arrays wird ein einmal berechneter Wert direkt nachgeschlagen und eine Rekursion ist nicht
nötig.
++++