8.581
Bearbeitungen
Jneug (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Jneug (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
Zeile 26: | Zeile 26: | ||
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}} | {{Aufgabe:Start}} | ||
Zeile 56: | Zeile 56: | ||
== Binäre Suche rekursiv == | == Binäre Suche rekursiv == | ||
Die Möglichkeiten zur Suche | 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 | 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}} | {{Aufgabe:Start}} | ||
Implementiere die rekursive binäre Suche in einer Methode mit der Signatur | Implementiere die rekursive binäre Suche in einer Methode mit der Signatur | ||
< | <syntaxhighlight lang="java"> | ||
public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis ) | 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. | 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}} | {{Aufgabe:End}} | ||
{{Lösung:Start}} | {{Lösung:Start}} |
Bearbeitungen