Informatik 12/13 (G9)

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen: • monitor
rekursion:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
rekursion:start [2024/09/08 13:28] – [Aufgabe 3: Die Türme von Hanoi] Martin Pabstrekursion:start [2024/11/15 09:09] (aktuell) – [Aufgabe 5: größter gemeinsamer Teiler] Martin Pabst
Zeile 1: Zeile 1:
-====== 1. Rekursion ======+====== 1. Rekursion (Einführung) ======
  
 ===== Beispiel 1: Berechnung von Fakultäten ===== ===== Beispiel 1: Berechnung von Fakultäten =====
Zeile 41: Zeile 41:
 <WRAP center round info 60%> <WRAP center round info 60%>
 **Definition:** \\ **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> </WRAP>
  
Zeile 50: Zeile 52:
 <WRAP center round info 60%> <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. \\ \\  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> </WRAP>
    
Zeile 61: Zeile 63:
 <WRAP center round info 60%> <WRAP center round info 60%>
 Die [[https://en.wikipedia.org/wiki/Fibonacci_sequence|Fibonacci-Folge]] ist wie folgt definiert: Die [[https://en.wikipedia.org/wiki/Fibonacci_sequence|Fibonacci-Folge]] ist wie folgt definiert:
 +$$ f_0 = 1 $$
 $$ f_1 = 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: 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$$ $$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ \ldots$$
Zeile 125: Zeile 127:
 </HTML> </HTML>
  
-====== Aufgabe 2: Fraktaler Baum ======+===== Aufgabe 2: Fraktaler Baum =====
 <WRAP center round todo 80%> <WRAP center round todo 80%>
 Erstelle mit Hilfe rekursiver Methodenaufrufe ein Programm, das einen fraktalen Baum zeichnet. Hier die Zeichnung nach der 12. Iteration: \\  Erstelle mit Hilfe rekursiver Methodenaufrufe ein Programm, das einen fraktalen Baum zeichnet. Hier die Zeichnung nach der 12. Iteration: \\ 
Zeile 137: Zeile 139:
  
 </WRAP> </WRAP>
-[[.fraktalerBaum:start6048|Lösung]]+[[.fraktalerBaum:start3826|Lösung]]
  
 <WRAP center round tip 60%> <WRAP center round tip 60%>
Zeile 187: Zeile 189:
 </WRAP> </WRAP>
  
-[[.hanoi:loesung:start8042|Lösung]]  \\ +[[.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]]
rekursion/start.1725802126.txt.gz · Zuletzt geändert: 2024/09/08 13:28 von Martin Pabst
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki