Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [05.02.2023 18:16] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [06.01.2024 13:37] (aktuell) – Marco Kuemmel
@@ Zeile 46: / Zeile 46: @@
 ++++
-Die rekursiven Aufrufe können in einem Baum veranschaulicht werden, hier am Beispiel ''pascal(3,2)'':
+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)''.
 ----
@@ Zeile 77: / Zeile 79: @@
 Baum dar.
-(C) Begründe, warum die Anzahl der Methodenaufrufe für ''fib(n)'' weniger als 2<sup>n+1></sup> beträgt.
+(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.
+++++