Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben - Versionsgeschichte

Jneug am 12. Februar 2022 um 09:06 Uhr

2022-02-12T09:06:26Z

← Nächstältere Version		Version vom 12. Februar 2022, 11:06 Uhr
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 ~~sehr gut~~ iterativ lösen.		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 ~~ein~~ 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 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 ~~auch gut~~ rekursiv umsetzen: Der Algorithmus zerlegt das Problem in zwei (in etwa) ~~gleichgroß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. ~~So lange~~, bis das Element gefunden wurde, oder bis das aktuelle Teilproblem leer ist.		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

	<~~pre~~>		<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 )
	</~~pre~~>		</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.

	~~Überlegen sie sich~~ zunächst konkret, wie die drei Bestandteile der Rekursion hier aussehen müssen.		Überlege zunächst konkret, wie die drei Bestandteile der Rekursion hier aussehen müssen.
	{{Aufgabe:End}}		{{Aufgabe:End}}
	{{Lösung:Start}}		{{Lösung:Start}}

Jneug am 13. November 2021 um 14:52 Uhr

2021-11-13T14:52:58Z

← Nächstältere Version		Version vom 13. November 2021, 16:52 Uhr
Zeile 1:		Zeile 1:
	{{Navigation}}		{{Navigation}}
	Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.		Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.
	{{~~Hinweis~~\|		{{Kasten\|
	Hast du die drei Bestandteile noch vor Augen?}}		Hast du die drei Bestandteile noch vor Augen?
			\|Farbe={{Farbe:Info}}}}

Jneug am 13. November 2021 um 14:52 Uhr

2021-11-13T14:52:17Z

← Nächstältere Version		Version vom 13. November 2021, 16:52 Uhr
Zeile 1:		Zeile 1:
	{{Navigation}}		{{Navigation}}
	Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.		Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.
	{{~~Fenster~~\|		{{Hinweis\|
	Hast du die drei Bestandteile noch vor Augen?		Hast du die drei Bestandteile noch vor Augen?}}
	~~\|Farbe={{Farbe:Info}}~~}}

Jneug am 6. Februar 2020 um 20:33 Uhr

2020-02-06T20:33:32Z

← Nächstältere Version		Version vom 6. Februar 2020, 22:33 Uhr
Zeile 1:		Zeile 1:
			{{Navigation}}
	Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.		Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.
	{{Fenster\|		{{Fenster\|

Jneug: /* Binäre Suche rekursiv */

2020-02-06T20:32:48Z

Binäre Suche rekursiv

← Nächstältere Version		Version vom 6. Februar 2020, 22:32 Uhr
Zeile 60:		Zeile 60:

	{{Aufgabe:Start}}		{{Aufgabe:Start}}
	~~Implementieren sie~~ die rekursive binäre Suche in einer Methode mit der Signatur		Implementiere die rekursive binäre Suche in einer Methode mit der Signatur

	<pre>		<pre>

Jneug: /* Suche in einem Array */

2020-01-28T22:04:45Z

Suche in einem Array

Änderungen zeigen

Jneug: /* Suche in einem Array */

2020-01-28T21:12:37Z

Suche in einem Array

← Nächstältere Version		Version vom 28. Januar 2020, 23:12 Uhr
Zeile 71:		Zeile 71:

	{{Aufgabe:Start}}		{{Aufgabe:Start}}
	<~~zuordnung>~~		<lückentext>
	~~Eine kleine Beschreibung~~		Fügen Sie die Methode <code>public int gibPosition(int z)</code> zusammen, die die Position einer Zahl im Array zurückgibt. Falls die Zahl nicht vorhanden ist, soll <code>-1</code> als Position zurückgegeben werden.
	~~::1::Ein Satz~~		'''public_int_gibPosition(int_z){'''
	~~::2::wort~~		'''int pos = -1;'''
	~~::3::Text::Lücke~~		'''for(int i=0; i < zahlen.length; i++){'''
	~~</zuordnung>~~		'''if(zahlen[i]==z){'''
			'''pos = i;'''
	~~<zuordnung~~>		'''}'''
	Fügen Sie die Methode ~~*~~public int gibPosition(int z)~~*~~, die die Position einer Zahl im Array zurückgibt. Falls die Zahl nicht vorhanden ist, soll -1 als Position zurückgegeben werden.		'''}'''
	~~::1::~~public_int_gibPosition(int_z){		'''return pos;'''
	~~::2::~~int pos = -1;		'''}'''
	~~::3::~~for(int i=0; i < zahlen.length; i++){		</lückentext>
	~~::4::~~if(zahlen[i]==z){
	~~::5::~~pos = i;
	~~::6::~~}
	~~::7::~~}
	~~::8::~~ return pos;
	~~::9::~~}
	</~~zuordnung~~>
	{{Aufgabe:End}}		{{Aufgabe:End}}

Jneug: /* Kästchen auf einem Gitter */

2020-01-28T21:05:08Z

Kästchen auf einem Gitter

← Nächstältere Version		Version vom 28. Januar 2020, 23:05 Uhr
Zeile 6:		Zeile 6:

	== Kästchen auf einem Gitter ==		== Kästchen auf einem Gitter ==
	~~[[Datei:05 Kaestchen.png \| right]]~~
	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.

Jneug am 28. Januar 2020 um 21:02 Uhr

2020-01-28T21:02:48Z

← Nächstältere Version		Version vom 28. Januar 2020, 23:02 Uhr
Zeile 1:		Zeile 1:
	Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der ~~[[Lernpfad:Rekursion in Java/Definition~~ \| Definition]] implementiert werden.		Um eine rekursive Methode zu schreiben müssen die drei Bestandteile der {{Pfad\|Definition}} implementiert werden.
	{{~~Aufgabe:Start}}~~		{{Fenster\|
	Hast du die drei Bestandteile noch vor Augen?		Hast du die drei Bestandteile noch vor Augen?
			\|Farbe={{Farbe:Info}}}}
	{{~~Aufgabe~~:~~End~~}}


Zeile 10:		Zeile 9:
	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?

	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.		* 2x2-Gitter,
	# 3x3-Gitter.		* 3x3-Gitter,
	# 4x4-Gitter.		* 4x4-Gitter.
	~~Lösung für 2x2 und 3x3~~:		{{Aufgabe:End}}{{Lösung:Start\|Lösung 2x2 und 3x3}}
	{{~~Collapse~~:Start}}		* 2x2-Gitter: vier 1x1 Kästchen und ein 2x2 Kästchen .
	~~#Für das~~ 2x2-Gitter ~~gibt es~~: 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.
	~~#Für das~~ 3x3-Gitter ~~gibt es~~: 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.
	{{~~Collapse~~:End}}		{{Lösung:End}}{{Lösung:Start\|Lösung 4x4}}
	~~Lösung für 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>.
	{{~~Collapse~~:Start}}		{{Lösung:End}}
	Für das 4x4-Gitter gibt es:sechzehn 1x1 Kästchen ~~und~~ neun 2x2 Kästchen ~~und~~ vier 3x3 Kästchen und ein 4x4 Kästchen ~~und~~.
	{{~~Collapse:End}}~~
	~~{{Aufgabe~~:End}}

	~~{{Aufgabe:Start}}~~
	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 sehr gut iterativ lösen.		Aber dieses Problem lässt sich auch sehr gut iterativ lösen.

	~~Rekursive~~ Lösung		{{Aufgabe:Start}}
	{{~~Collapse~~: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}}
	if(n > 1){		<syntaxhighlight lang="java" line="1">
	return n*n+k_rek(n-1);		public int k_rek(int n) {
	}else{		if(n > 1) {
	return 1;		return n*n+k_rek(n-1);
	}		} else {
			return 1;
			}
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	{{~~Collapse~~:End}}		{{Lösung:End}}
			{{Lösung:Start\|Iterative Lösung}}
	~~Iterative Lösung~~		<syntaxhighlight lang="java" line="1">
	{{~~Collapse~~:Start}}		public int k_it(n) {
	<syntaxhighlight lang="java">		int sum = 0;
	public int k_it(n){		for(int i = 1; i<n+1 ;i++) {
	int sum = 0;		sum = sum + i*i;
	for(int i = 1; i<n+1 ;i++){		}
	sum = sum + i*i;		return sum;
	}
	return sum;
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	{{~~Collapse:End}}~~		{{Lösung:End}}
	~~{{Aufgabe~~:End}}

	== Suche in einem Array ==		== Suche in einem Array ==

Thi: /* Suche in einem unsortieren Array */

2019-01-09T08:54:04Z

Suche in einem unsortieren Array

← Nächstältere Version		Version vom 9. Januar 2019, 10:54 Uhr
Zeile 87:		Zeile 87:
	<zuordnung>		<zuordnung>
	Fügen Sie die Methode *public int gibPosition(int z)*, die die Position einer Zahl im Array zurückgibt. Falls die Zahl nicht vorhanden ist, soll -1 als Position zurückgegeben werden.		Fügen Sie die Methode *public int gibPosition(int z)*, die die Position einer Zahl im Array zurückgibt. Falls die Zahl nicht vorhanden ist, soll -1 als Position zurückgegeben werden.
	1::public_int_gibPosition(int_z){		::1::public_int_gibPosition(int_z){
	2::int pos = -1;		::2::int pos = -1;
	3::for(int i=0; i < zahlen.length; i++){		::3::for(int i=0; i < zahlen.length; i++){
	4::if(zahlen[i]==z){		::4::if(zahlen[i]==z){
	5::pos = i;		::5::pos = i;
	6::}		::6::}
	7::}		::7::}
	8:: return pos;		::8:: return pos;
	9::}		::9::}
	</zuordnung>		</zuordnung>
	{{Aufgabe:End}}		{{Aufgabe:End}}