Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== 1. Rekursion (Einführung) ======

===== Beispiel 1: Berechnung von Fakultäten =====
<WRAP center round info 60%>
Erinnern Sie sich noch an die Fakultätsfunktion? Sie ist so definiert:
$$0! = 1$$ und
$$n! = 1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)\cdot n \ \mathrm{für}\ n \in \mathbb{N} \backslash \{0\},$$
also beispielsweise:
$$5! = 1\cdot 2\cdot 3\cdot 4 \cdot 5 = 120$$
\\ 
  * Probieren Sie das folgende Programm aus, auch im Einzelschrittmodus.
  * Analysieren Sie das Programm genau und überlegen Sie, welche Anweisungen der Reihe nach ausgeführt werden. 
</WRAP>

<HTML>

<div class="java-online" style="height: 450px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'fakultaet1', 'speed': 100000}">

<script type="text/plain" title="Hauptprogramm.java">
Matheklasse m = new Matheklasse();

println(m.fakultät(4));

class Matheklasse {
   
   int fakultät(int n) {
      if(n == 0) {
         return 1;
      }

      int ergebnis = n * fakultät(n - 1);

      return ergebnis;
   }

}
</script>
</div>
</HTML>

<WRAP center round info 60%>
**Definition:** \\
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.
  * 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>


=== Erklärung des Programmablaufs: ===
<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. \\ \\ 

</WRAP>
 
{{ :rekursion:rekursion_erklaerung.png?direct&600 |}}
Hier etwas gröber dargestellt:
{{ :rekursion:rekursion.svg |}}

===== Aufgabe 1: Die Fibonacci-Folge =====

<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_n = f_{n-2} + f_{n-1}\ \ \mathrm{für}\ \ n > 1 $$
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$$
</WRAP>

<WRAP center round todo 60%>
  * Programmieren Sie eine Methode, die das n-te Glied der Fibonacci-Folge berechnet. Nutzen Sie dazu rekursive Methodenaufrufe und orientiere Dich am vorherigen Programm (Fakultätsberechnung).
  * Welchen wesentlichen Unterschied zum vorherigen Programm bemerken Sie? Wie wirkt er sich auf die obigen Diagramme zur Erklärung aus?
</WRAP>

[[.fibonacci:start|Musterlösung -> Bitte erst nach der Informatikstunde ansehen!]]

===== Beispiel 2: Die Kochkurve =====
<WRAP center round info 60%>
Die **Kochkurve** und die aus ihr gewonnene Kochsche Schneeflocke werden [[https://de.wikipedia.org/wiki/Koch-Kurve|in diesem Wikipedia-Artikel]] schön beschrieben. Die Kochkurve ergibt sich, indem man von einer waagrechten Strecke ausgeht und bei jedem Iterationsschritt jede Strecke folgendermaßen ersetzt:
{{ :rekursion:pasted:20240908-142937.png?300 }}
Die **Kochsche Schneeflocke** erhält man, wenn man von einem gleichseitigen Dreieck ausgehend dieselbe Iterationsvorschrift immer wieder anwendet.
</WRAP>


<HTML>

<div class="java-online" style="height: 400px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'hanoiloesung', 'speed': 100000}">

<script type="text/plain" title="Hauptprogramm.java">
new World(800, 800);
new Kochkurve(4);

class Kochkurve extends Turtle {
   
   Kochkurve(int tiefe) {
      super(100, 600);
      setBorderWidth(1);
      
      // Zeichne das gleichseitige Dreieck:
      vorwärts(600, tiefe);
      turn(120);
      vorwärts(600, tiefe);
      turn(120);
      vorwärts(600, tiefe);
      turn(120);
   }

   void vorwärts(double länge, int tiefe) {
      if(tiefe == 0) {
         forward(länge);
      } else {
         vorwärts(länge / 3, tiefe - 1);
         turn(-60);
         vorwärts(länge / 3, tiefe - 1);
         turn(120);
         vorwärts(länge / 3, tiefe - 1);
         turn(-60);
         vorwärts(länge / 3, tiefe - 1);
      }
   }

}
</script>
</div>
</HTML>

===== Aufgabe 2: Fraktaler Baum =====
<WRAP center round todo 80%>
Erstelle mit Hilfe rekursiver Methodenaufrufe ein Programm, das einen fraktalen Baum zeichnet. Hier die Zeichnung nach der 12. Iteration: \\ 
{{ :rekursion:pasted:20240908-150155.png }}
\\ 
Die Zeichnung beginnt mit einer vertikalen Linie und folgt folgender Iterationsvorschrift: \\ 
{{ :rekursion:fraktaler_baum.svg?600 |}}
\\ 
**Tipp:** \\ 
Mit der Methode ''penUp()'' kannst Du den Stift der Turtle anheben, so dass sie nicht mehr zeichnet. Mit der Methode ''penDown()'' kannst Du ihn wieder herabsenken, so dass die Turtle wieder zeichnet. 

</WRAP>
[[.fraktalerBaum:start3826|Lösung]]

<WRAP center round tip 60%>
**Für Interessierte:** \\ \\ 
Neben der Kochkurve und fraktalen Bäumen gibt es viele weitere schöne [[https://de.wikipedia.org/wiki/Fraktal|fraktale]] Punktmengen, die mit wenig Aufwand durch einfach rekursive Methoden gezeichnet werden können:
  * [[https://de.wikipedia.org/wiki/Drachenkurve|Die Drachenkurve]]
  * [[https://de.wikipedia.org/wiki/Hilbert-Kurve|Die Hilbertkurve]]
  * usw.

Lassen Sie sich herausfordern!

</WRAP>

===== Aufgabe 3: Die Türme von Hanoi =====
Das Problem der Türme von Hanoi wird in diesem Video gut erklärt:
{{ youtube>UMPneeBzQHk?large }}
**Kurzgefasst:** \\ 
Vor Ihnen befinden sich drei Stäbe ("Türme"), wobei sich auf dem rechten der drei Stäbe ''n'' der Größe nach geordnete Scheiben befinden, die größte zuunterst. Die Aufgabe besteht darin, alle ''n'' Scheiben zum linken Stab zu bringen, wobei folgende Spielregeln gelten:
  * Bei jedem Schritt darf nur eine Scheibe bewegt werden.
  * Es darf **nie** zu einer Situation kommen, bei der auf einem der drei Stäbe eine größere Scheibe oberhalb einer kleinen zu liegen kommt.
\\ \\ 
<WRAP center round todo 60%>
**Aufgabe 3: Die Türme von Hanoi** \\ 
Die drei Türme bekommen die Nummern 1, 2 und 3. \\ \\ Schreibe eine Klasse ''Hanoi'' mit einer Methode ''erkläreLösung(int startTurmNummer, int zielTurmNummer, int n)'', die in Textform erklärt, wie man ''n'' Scheiben unter Einhaltung der im Video erklärten Regeln vom Turm ''startTurmNummer'' zum Turm ''zielTurmNummer'' bringt. \\ \\ 
Die Ausgabe von ''erkläreLösung(1, 3, 4)'' soll beispielsweise so aussehen: 
<code>
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 3
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 3 zu Turm 1
Bewege eine Scheibe von Turm 3 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 1
Bewege eine Scheibe von Turm 3 zu Turm 1
Bewege eine Scheibe von Turm 2 zu Turm 3
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 3
</code>
</WRAP>

<WRAP center round tip 60%>
**Lösungsidee/Tipps:** \\
  * Bei gegebenen Türmen ''x'' und ''y'' hat der übrige Turm dann immer die Nummer ''6 - x - y''
  * Um ''n'' Scheiben von Turm x zu Turm y zu bewegen, bewege zuerst ''n - 1'' Scheiben von Turm ''x'' zu Turm ''6 - x - y'', dann eine (die größte!) Scheibe von Turm ''x'' zur Turm ''y'' und dann ''n - 1'' Scheiben von Turm ''6 - x - y'' zu Turm ''y''. Die Methode ''erkläreLösung'' muss sich also nur geeignet selbst aufrufen.
</WRAP>

[[.hanoi:loesung:start1832|Lösung]]  \\ 


<WRAP center round tip 60%>
**Für Interessierte:** Quicksort \\
Stellen Sie sich ein Array mit ''n'' Elementen (z.B. Zahlen oder Zeichenketten) vor, das es zu (numerisch bzw. alphabetisch) zu sortieren gilt. Bei zufälliger Verteilung ist [[https://de.wikipedia.org/wiki/Quicksort|Quicksort]] im Mittel der schnellste Algorithmus für diesen Zweck.
[[.quicksort:start|Hier ist der Algorithmus erklärt und implementiert.]]
</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]]