Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:uebungen03:start [07.02.2023 13:51] – 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?
+++++ 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.
@@ Zeile 108: / Zeile 113: @@
 </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.