Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [05.02.2023 16:55] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [18.02.2025 06:45] (aktuell) – Frank Schiebel
@@ Zeile 3: / Zeile 3: @@
 {{: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 || 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)''.
 ----
@@ Zeile 14: / Zeile 61: @@
 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 |}}
+{{:faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:bildschirmfoto_vom_2023-02-05_17-47-15.png?400|}}
@@ Zeile 30: / Zeile 77: @@
 (B) Stelle die ausgeführten Methodenaufrufe bei der Ausführung von ''fib(4)'' als
-Baum dar.
+Baum dar. Gibt es Aufrufe von ''fib'', die mehr als einmal durchgeführt werden?
-(C) Begründe, warum die Anzahl der Methodenaufrufe für ''fib(n)'' weniger als 2<sup>n+1></sup> beträgt.
+++++ Lösung |
+{{ :faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:aufrufbaum_fib4.png?nolink |}}
+Die rot markierten Aufrufe finden mehr als einmal statt.
+++++
+(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.
+++++