Bestimme die Anzahl der Kästchen in einem
- 2x2-Gitter,
- 3x3-Gitter,
- 4x4-Gitter.
Implementiere eine rekursive und eine iterative Lösung für das Kästchen-Problem.
🔎 Lösung: Rekursiv
public int k_rek(int n) {
if(n > 1) {
return n*n+k_rek(n-1);
} else {
return 1;
}
}🔎 Lösung: Iterativ
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 der Vorlage unten. 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.
🔎 Lösung
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.
Implementiere eine binäre Suche für Karten-Objekte der Klasse Karte.