Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [05.02.2023 17:35] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [18.02.2025 06:45] (aktuell) – Frank Schiebel
@@ Zeile 37: / Zeile 37: @@
 public int pascal(int z, int s)
     {
-        if ( z==0 || z==1 || s==0 || s==z ) {
+        if ( z==0 || s==0 || s==z ) {
             return 1;
         } else {
@@ Zeile 77: / 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.
@@ Zeile 101: / Zeile 106: @@
     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 dar. Gib bei jedem Knoten den Inhalt des Arrays cache an, nachdem der jeweilige Methodenaufruf beendet ist.
+(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.
+++++