Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- rekursion:start [2024/09/08 13:37] – Martin Pabst
+++ rekursion:start [2024/11/15 09:09] (aktuell) – [Aufgabe 5: größter gemeinsamer Teiler] Martin Pabst
@@ Zeile 41: / Zeile 41: @@
 <WRAP center round info 60%>
 **Definition:** \\
-Von **Rekursion** spricht man, wenn sich eine Methode entweder direkt selbst aufruft oder über eine Aufrufkette (z.B. Methode a ruft Methode b auf, die ruft Methode c auf, diese wiederum ruft Methode a auf). \\ \\
+Von **Rekursion** (von lateinisch //recurrere// == „zurücklaufen“) spricht man, wenn sich eine Methode entweder direkt selbst aufruft oder über eine Aufrufkette (z.B. Methode a ruft Methode b auf, die ruft Methode c auf, diese wiederum ruft Methode a auf). \\ \\
-**Wichtig:** Jede Rekursion benötigt eine **Abbruchbedingung**, die das Unterbrechen der Aufrufkette nach endlich vielen Schritten sicherstellt.
+**Wichtig:**
+  * Jede Rekursion benötigt eine **Abbruchbedingung**, die das Unterbrechen der Aufrufkette nach endlich vielen Schritten sicherstellt.
+  * Ruft sich die rekursive Methode genau ein Mal auf, so spricht man von **linearer Rekursion**. Ruft sie sich mehrmals auf, so spricht man von **verzweigter Rekursion** (siehe Aufgabe 1 unten).
 </WRAP>
@@ Zeile 50: / Zeile 52: @@
 <WRAP center round info 60%>
 Um zu verstehen, wieso ein rekursiver Aufruf einer Methode überhaupt funktionieren kann stellen Sie sich am besten vor, dass der Computer bei jedem Aufruf der Methode ''fakultät'' die Werte aller Parameter und lokalen Variablen "speichert" und bei jeder Rückkehr wiederherstellt. Bei jedem Betreten der Methode ''fakultät'' erhalten die Parameter und lokalen Variablen daher "neue" Werte. \\ \\
-TODO <Erklärung des Stacks für Interessierte>
 </WRAP>
@@ Zeile 61: / Zeile 63: @@
 <WRAP center round info 60%>
 Die [[https://en.wikipedia.org/wiki/Fibonacci_sequence|Fibonacci-Folge]] ist wie folgt definiert:
+$$ f_0 = 1 $$
 $$ f_1 = 1 $$
-$$ f_2 = 1 $$
+$$ f_n = f_{n-2} + f_{n-1}\ \ \mathrm{für}\ \ n > 1 $$
-$$ f_n = f_{n-2} + f_{n-1}\ \ \mathrm{für}\ \ n > 2 $$
 Jedes Folgenglied ist also die Summe der beiden vorhergehenden Folgenglieder. Hier die ersten Glieder:
 $$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ \ldots$$
@@ Zeile 187: / Zeile 189: @@
 </WRAP>
-[[.hanoi:loesung:start8042|Lösung]]  \\
+[[.hanoi:loesung:start1832|Lösung]]  \\
@@ Zeile 196: / Zeile 198: @@
 </WRAP>
+===== Aufgabe 4: Floodfill =====
+<WRAP center round info 60%>
+Gegeben ist eine Pixelgrafik mit einem beliebig geformten, zusammenhängenden Gebiet von Pixeln einer Farbe. Gesucht ist ein Algorithmus, der - ausgehend von einem Pixel dieses Gebietes - alle damit verbundenen Pixel gleicher Farbe rot färbt. \\ \\
+Ein Algorithmus, der dieses Problem löst, ist **Floodfill**. Er existiert in einer rekursiven Variante, die [[https://de.wikipedia.org/wiki/Floodfill|hier sehr anschaulich erklärt ist.]]
+\\ \\
+Gegeben ist das Programmgerüst unten, bei dem bereits dafür gesorgt ist, dass bei Mausklick auf den Punkt (x, y) die Methode ''fill(x, y, newColor)'' aufgerufen wird. Ergänzen Sie die Methode ''fillIntntern'' so, dass ausgehend vom Punkt (x, y) alle gleichfarbigen, damit verbundenen Punkte in der neuen Farbe eingefärbt werden.
+</WRAP>
+<HTML>
+<div class="java-online" style="height: 400px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'floodfillaufgabe', 'speed': 100000}">
+<script type="text/plain" title="Hauptprogramm.java">
+new FloodfillExample();
+class FloodfillExample extends Bitmap {
+   FloodfillExample() {
+      super(100, 100, 0, 0, 600, 600);
+      drawTestImage();
+   }
+   void fill(int x, int y, int newColor) {
+      int oldColor = getColorAsInt(x, y);
+      if(newColor == oldColor) {
+         return;
+      }
+      fillIntern(x, y, newColor, oldColor);
+   }
+   private void fillIntern(int x, int y, int newColor, int oldColor) {
+      // TODO:
+      //  - Überprüfen, ob der Punkt (x,y) sich innerhalb der Bitmap befindet
+      //  - Überprüfen, ob der Punkt die Farbe oldColor besitzt
+      //  - ggf. Einfärben des Punktes (Methode setColor), und rekursive Methodenaufrufe für die benachbarten Punkte
+   }
+   public void onMouseDown(double x, double y, int button) {
+      Position position = this.screenCoordinatesToBitmapCoordinates(x, y);
+      this.fill(position.x, position.y, 0xff0000);
+   }
+   void drawTestImage() {
+      for (int n = 0; n < 6000; n++) {
+         setColor(Random.randint(0, 99), Random.randint(0, 99), 0xffffff);
+      }
+   }
+}
+</script>
+</div>
+</HTML>
+[[.floodfillloesung:start1285|Lösung]]
+===== Aufgabe 5: größter gemeinsamer Teiler =====
+<WRAP center round info 80%>
+Sind $a, b \in \mathbb{N}$, so lässt sich der größte gemeinsame Teiler von $a$ und $b$ ("ggT(a, b)") auf folgende Art rekursiv berechnen:
+\\ $ ggT(a, b) = $
+  * $a$, falls $a = b$,
+  * $ggT(b, a-b)$, falls $ a > b$ und
+  * $ggT(a, b - a)$, falls $a < b$.
+Schreiben Sie eine Klasse ''MathTools'' mit einer Methode ''ggT'', die den ggT zweier Zahlen auf die oben beschriebene Art berechnet!
+</WRAP>
+[[.ggtLoesung:start|Lösung]]