Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben: Unterschied zwischen den Versionen
Thi (Diskussion | Beiträge) |
Jneug (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
(13 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der | {{Navigation}} | ||
{{ | Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad|Definition}} implementiert werden. | ||
{{Kasten| | |||
Hast du die drei Bestandteile noch vor Augen? | Hast du die drei Bestandteile noch vor Augen? | ||
|Farbe={{Farbe:Info}}}} | |||
{{ | |||
== Kästchen auf einem Gitter == | == Kästchen auf einem Gitter == | ||
Auf einem Schachbrett kann man entlang der Kanten Quadrate zeichnen. Wie viele Quadrate aller Längen passen denn auf ein Schachbrett bzw. Gitter? | Auf einem Schachbrett kann man entlang der Kanten Quadrate zeichnen. Wie viele Quadrate aller Längen passen denn auf ein Schachbrett bzw. Gitter? | ||
[[Datei:05 Kaestchen.png|center]] | |||
Um dieses Problem zu lösen, solltest du zunächst das Problem für kleine Gitter lösen um dann ein allgemeines Muster für große Gitter zu bestimmen. | Um dieses Problem zu lösen, solltest du zunächst das Problem für kleine Gitter lösen, um dann ein allgemeines Muster für große Gitter zu bestimmen. | ||
{{Aufgabe:Start}} | {{Aufgabe:Start}} | ||
Bestimme die Anzahl der Kästchen in einem | Bestimme die Anzahl der Kästchen in einem | ||
* 2x2-Gitter, | |||
* 3x3-Gitter, | |||
* 4x4-Gitter. | |||
{{Aufgabe:End}}{{Lösung:Start|Lösung 2x2 und 3x3}} | |||
{{ | * 2x2-Gitter: vier 1x1 Kästchen und ein 2x2 Kästchen . | ||
* 3x3-Gitter: neun 1x1 Kästchen und vier 2x2 Kästchen und ein 3x3 Kästchen. | |||
Die Zahlen 1,4,9,16, usw. werden als Quadratzahlen bezeichnet. | Die Zahlen 1, 4, 9, 16, usw. werden als ''Quadratzahlen'' bezeichnet. | ||
{{ | {{Lösung:End}}{{Lösung:Start|Lösung 4x4}} | ||
Für das 4x4-Gitter gibt es sechzehn 1x1 Kästchen, neun 2x2 Kästchen, vier 3x3 Kästchen und ein 4x4 Kästchen. Insgesamt also <math>1+4+9+16 = 30</math>. | |||
{{ | {{Lösung:End}} | ||
Für das 4x4-Gitter gibt es | |||
{{ | |||
Natürlich lässt sich auch eine Methode für die Anzahl der Kästchen programmieren. Die Beobachtungen aus den Beispielen für ein 2x2, 3x3 und 4x4-Gitter können bei der Formulierung einer rekursiven Formel helfen. | Natürlich lässt sich auch eine Methode für die Anzahl der Kästchen programmieren. Die Beobachtungen aus den Beispielen für ein 2x2, 3x3 und 4x4-Gitter können bei der Formulierung einer rekursiven Formel helfen. | ||
Aber dieses Problem lässt sich auch | Aber dieses Problem lässt sich auch ohne Weiteres iterativ lösen. | ||
{{Aufgabe:Start}} | |||
{{ | Implementiere eine rekursive und eine iterative Lösung für das Kästchen-Problem. | ||
<syntaxhighlight lang="java"> | {{Aufgabe:End}} | ||
public int k_rek(int n){ | {{Lösung:Start|Rekursive Lösung}} | ||
<syntaxhighlight lang="java" line="1"> | |||
public int k_rek(int n) { | |||
if(n > 1) { | |||
return n*n+k_rek(n-1); | |||
} else { | |||
return 1; | |||
} | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{ | {{Lösung:End}} | ||
{{Lösung:Start|Iterative Lösung}} | |||
<syntaxhighlight lang="java" line="1"> | |||
{{ | public int k_it(n) { | ||
<syntaxhighlight lang="java"> | int sum = 0; | ||
public int k_it(n){ | for(int i = 1; i<n+1 ;i++) { | ||
sum = sum + i*i; | |||
} | |||
return sum; | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{ | {{Lösung:End}} | ||
== Binäre Suche rekursiv == | |||
Die Möglichkeiten zur Suche in einem Array ist dir schon bekannt. Sind die Daten nicht vorsortiert, dann muss die ''lineare Suche'' angewandt werden, liegen die Daten sortiert vor, dann kann die Suche mit der ''binären Suche'' beschleunigt werden. | |||
Die binäre Suche lässt sich rekursiv umsetzen: Der Algorithmus zerlegt das Problem in zwei (in etwa) gleich große Teilprobleme. Das eine kann sofort entschieden werden: Es enthält das gesuchte Element auf keinen Fall. Auf den anderen Teil wird derselbe Algorithmus wieder angewandt. Solange, bis das Element gefunden wurde, oder bis das aktuelle Teilproblem leer ist. | |||
{{Aufgabe:Start}} | |||
Implementiere die rekursive binäre Suche in einer Methode mit der Signatur | |||
<syntaxhighlight lang="java"> | <syntaxhighlight lang="java"> | ||
public | public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis ) | ||
</syntaxhighlight> | |||
Die Methode soll als Ergebnis die Position des Elements im Array zurückgeben, oder <code>-1</code>, wenn es nicht vorhanden ist. | |||
Überlege zunächst konkret, wie die drei Bestandteile der Rekursion hier aussehen müssen. | |||
{{Aufgabe:End}} | |||
{{Lösung:Start}} | |||
<syntaxhighlight lang="java" line="1"> | |||
public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis ) { | |||
if( von > bis ) { // Abbruchbedingung | |||
return -1; // Abbruch der Rekursion | |||
} else { | |||
// (int) "schneidet" die Nachkommastellen ab | |||
int mitte = (int)((von+bis)/2); | |||
if( suchzahl < sucharray[mitte] ) { | |||
// Rekursionsaufruf und Reduktion auf die linke Hälfte | |||
return binaereSucheRekursiv(suchzahl, sucharray, von, mitte-1); | |||
} else if( sucharray[mitte] < suchzahl ) { | |||
// Rekursionsaufruf und Reduktion auf die rechte Hälfte | |||
return binaereSucheRekursiv(suchzahl, sucharray, mitte+1, bis); | |||
} else { | |||
// Element gefunden | |||
return mitte; | |||
} | |||
} | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Lösung:End}} | |||
In der Regel werden nicht einfach nur Zahlen sortiert, sondern Objekte mit Eigenschaften, die verglichen werden. Die Sortierung kann dann nach verschiedenen Kriterien erfolgen. | |||
Spielkarten werden zum Beispiel zuerst nach der [[wikipedia:Farbe_(Kartenspiel)|Farbe]] und dann nach dem Kartenwert sortiert. | |||
<syntaxhighlight lang="java" line="1"> | |||
<syntaxhighlight lang="java"> | public class Karte { | ||
public class | private String farbe; | ||
private int wert; | |||
public Karte( String pFarbe, int pWert ) { | |||
farbe = pFarbe; | |||
wert = pWert; | |||
} | } | ||
public String getFarbe() { | |||
return farbe; | |||
} | } | ||
public int getWert() { | |||
return wert; | |||
} | } | ||
} | |||
</syntaxhighlight> | </syntaxhighlight> | ||
{{ | {{Aufgabe:Start}} | ||
Implementiere eine binäre Suche für Karten-Objekte der Klasse <code>Karte</code> oben. | |||
{{Aufgabe:End}} |
Aktuelle Version vom 12. Februar 2022, 11:06 Uhr
Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der Definition implementiert werden.
Hast du die drei Bestandteile noch vor Augen?
Kästchen auf einem Gitter
Auf einem Schachbrett kann man entlang der Kanten Quadrate zeichnen. Wie viele Quadrate aller Längen passen denn auf ein Schachbrett bzw. Gitter?
Um dieses Problem zu lösen, solltest du zunächst das Problem für kleine Gitter lösen, um dann ein allgemeines Muster für große Gitter zu bestimmen.
Bestimme die Anzahl der Kästchen in einem
- 2x2-Gitter,
- 3x3-Gitter,
- 4x4-Gitter.
- 2x2-Gitter: vier 1x1 Kästchen und ein 2x2 Kästchen .
- 3x3-Gitter: neun 1x1 Kästchen und vier 2x2 Kästchen und ein 3x3 Kästchen.
Die Zahlen 1, 4, 9, 16, usw. werden als Quadratzahlen bezeichnet.
Für das 4x4-Gitter gibt es sechzehn 1x1 Kästchen, neun 2x2 Kästchen, vier 3x3 Kästchen und ein 4x4 Kästchen. Insgesamt also [math]\displaystyle{ 1+4+9+16 = 30 }[/math].
Natürlich lässt sich auch eine Methode für die Anzahl der Kästchen programmieren. Die Beobachtungen aus den Beispielen für ein 2x2, 3x3 und 4x4-Gitter können bei der Formulierung einer rekursiven Formel helfen.
Aber dieses Problem lässt sich auch ohne Weiteres iterativ lösen.
Implementiere eine rekursive und eine iterative Lösung für das Kästchen-Problem.
public int k_rek(int n) {
if(n > 1) {
return n*n+k_rek(n-1);
} else {
return 1;
}
}
public int k_it(n) {
int sum = 0;
for(int i = 1; i<n+1 ;i++) {
sum = sum + i*i;
}
return sum;
}
Binäre Suche rekursiv
Die Möglichkeiten zur Suche in einem Array ist dir schon bekannt. Sind die Daten nicht vorsortiert, dann muss die lineare Suche angewandt werden, liegen die Daten sortiert vor, dann kann die Suche mit der binären Suche beschleunigt werden.
Die binäre Suche lässt sich rekursiv umsetzen: Der Algorithmus zerlegt das Problem in zwei (in etwa) gleich große Teilprobleme. Das eine kann sofort entschieden werden: Es enthält das gesuchte Element auf keinen Fall. Auf den anderen Teil wird derselbe Algorithmus wieder angewandt. Solange, bis das Element gefunden wurde, oder bis das aktuelle Teilproblem leer ist.
Implementiere die rekursive binäre Suche in einer Methode mit der Signatur
public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis )
Die Methode soll als Ergebnis die Position des Elements im Array zurückgeben, oder -1
, wenn es nicht vorhanden ist.
Überlege zunächst konkret, wie die drei Bestandteile der Rekursion hier aussehen müssen.
public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis ) {
if( von > bis ) { // Abbruchbedingung
return -1; // Abbruch der Rekursion
} else {
// (int) "schneidet" die Nachkommastellen ab
int mitte = (int)((von+bis)/2);
if( suchzahl < sucharray[mitte] ) {
// Rekursionsaufruf und Reduktion auf die linke Hälfte
return binaereSucheRekursiv(suchzahl, sucharray, von, mitte-1);
} else if( sucharray[mitte] < suchzahl ) {
// Rekursionsaufruf und Reduktion auf die rechte Hälfte
return binaereSucheRekursiv(suchzahl, sucharray, mitte+1, bis);
} else {
// Element gefunden
return mitte;
}
}
}
In der Regel werden nicht einfach nur Zahlen sortiert, sondern Objekte mit Eigenschaften, die verglichen werden. Die Sortierung kann dann nach verschiedenen Kriterien erfolgen.
Spielkarten werden zum Beispiel zuerst nach der Farbe und dann nach dem Kartenwert sortiert.
public class Karte {
private String farbe;
private int wert;
public Karte( String pFarbe, int pWert ) {
farbe = pFarbe;
wert = pWert;
}
public String getFarbe() {
return farbe;
}
public int getWert() {
return wert;
}
}
Implementiere eine binäre Suche für Karten-Objekte der Klasse Karte
oben.