Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [05.02.2023 16:46] – angelegt 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)''.
+----
 {{:aufgabe.png?nolink  |}}
 === (A2) Ficonacci mit Baum ===
@@ Zeile 13: / Zeile 60: @@
 Die Fibonacci-Funktion (auch als Fibonacci-Folge bezeichnet) ist definiert als:
-f (n)=
-{
+{{:faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:bildschirmfoto_vom_2023-02-05_17-47-15.png?400|}}
-wenn n = 0
-wenn n = 1
-f(n−1)+f (n−2)
-sonst
 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:
+  wenn n ≤ 1:
-gib n zurück
+    gib n zurück
-sonst:
+  sonst:
-gib fib(n-1) + fib(n-2) zurück
+    gib fib(n-1) + fib(n-2) zurück
-(a) Geben Sie die vier Werte der Fibonacci-Folge an, die auf das Folgenglied 13 folgen.
+</code>
-(b) Stellen Sie die ausgeführten Methodenaufrufe bei der Ausführung von fib(4) als
-Baum dar.
+(A) Gib die vier Werte der Fibonacci-Folge an, die auf das Folgenglied 13 folgen.
-(c) Begründen Sie, warum die Anzahl der Methodenaufrufe für fib(n) weniger als 2
-beträgt.
+(B) Stelle die ausgeführten Methodenaufrufe bei der Ausführung von ''fib(4)'' als
-n+1
+Baum dar. Gibt es Aufrufe von ''fib'', die mehr als einmal durchgeführt werden?
-(d) Implementieren Sie eine Methode fibIterativ(n: int): int, die dasselbe Er-
-gebnis wie fib berechnet, die aber ohne Rekursion arbeitet.
+++++ 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.
+++++