Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- rekursion:start [2024/09/11 08:14] – [Aufgabe 1: Die Fibonacci-Folge] 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:**
@@ Zeile 189: / Zeile 189: @@
 </WRAP>
-[[.hanoi:loesung:start8042|Lösung]]  \\
+[[.hanoi:loesung:start1832|Lösung]]  \\
@@ Zeile 198: / 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]]