Noch eine Frage zur Rekursion...

S

Soltan

Aktives Mitglied
Folgende Aufgabe:
Es dürfen keinerlei Schleifen verwendet werden.....

Schreiben Sie eine boolean-Methode containsValue(int[] arr, int val), die true liefert, wenn
eines der Elemente von arr dem Wert val entspricht. Die Methode soll in Ihrem Methodenrumpf
zwei rekursive Aufrufe haben, wobei ein rekursiver Aufruf die erste Hälfte des
Arrays durchsucht und der zweite die zweite Halfte. Hinweis: Sie konnen die Methode
Arrays.copyOfRange(...) nutzen.

Meine Frage: Damit die Rekursion einen Fortschritt erzielt muss ich ja pro Aufruf einen Wert verändern.... sagen wir im Index einen Schritt rauf etc. Das ist bei diesem Beispiel allerdings nicht möglich da val nicht verändert werden kann.Wie soll ich die einzelnen Indexe nach und nach überprüfen wenn ich in die Rekursion nur mit einem fixen Wert gehen kann ?!
 
Robat

Robat

Top Contributor
Durch geschicktes anwenden der Arrays.copyOfRange(..) Methode kannst du das array welches du übergibst ändern.
Die vordere Hälfte bekommst du bspw wenn du als Endindex arr.length / 2 und als Startindex 0 nimmst (für die Arrays.copyOfRange(..) Methode)
 
R

Rusticus1999

Mitglied
Hallo Soltan,
Ich verstehe die Frage noch nicht ganz. Also damit du die Methode rekursiv ausführen kannst musst du ja das array halbieren, in ein neues array schreiben und das dem rekursiven Aufruf übergeben. Das ganze wird solange gemacht bis die Länge des übergeben arrays 1 ist und an der Stelle solltest du dann checken ob der wert dem übergeben val gleicht. Du musst den Rückgabe wert dann immer weiter weiter Hochreichen und falls mindestens einer der beiden Unteraufrufe true zurück gibt auch true ausgeben. Das ganze funktioniert zwar, meiner Meinung nach wäre es aber effektiver das Array einfach mit ner schleife abzugehen.

Ich hoffe ich konnte helfen. Das war mein erster Beitrag. Wenn nicht frag bitte weiter.
 
S

Soltan

Aktives Mitglied
Wenn ich das array immer weiter halbiere bis nur eine Wert übrig bleibt ... vergleiche ich dann nicht eben nur diesen einen Wert mit Val ? Das ganze Beispiel zielt nur darauf ab Rekursion zu verstehen und sowas ohne Schleife zu lösen... Gott ich verstehe irgendwie nicht so ganz wie ich das angehe..... Ich spiel mich seit Stundne herum und trete auf der Stelle.
 
Zuletzt bearbeitet:
R

Rusticus1999

Mitglied
Wenn ich das array immer weiter halbiere bis nur eine Wert übrig bleibt ... vergleiche ich dann nicht eben nur diesen einen Wert mit Val ? Das ganze Beispiel zielt nur darauf ab Rekursion zu verstehen und sowas ohne Schleife zu lösen... Gott ich verstehe irgendwie nicht so ganz wie ich das angehe..... Ich spiel mich seit Stundne herum und trete auf der Stelle.
Genau. Das ist der sinn der Sache. Du teilst es solange auf bis jeder Aufruf nur noch eine Stelle hat und das vergleichst du mit val. Also
if(arr.length==1)
return(arr[0]==val);
else{
return(rekursion(arr.copyOfRange(0,arr.length/2))||rekursion(arr.copyOfRange(arr.length/2,arr.length)))
}
rekursion (...) Ist dabei die Methode die rekursiv ausgeführt wird , also "contains Value(), und du musst über der Klasse noch import java.util.Arrays.*; machen, damit du copy of range benutzen kannst.
 
S

Soltan

Aktives Mitglied
Ich habe offensichtlich einen Knoten im Kopf.... sollten nicht alle Werte überprüft werden ? Wie soll die Überprüfung von diesem einen Wert auf den wir das array sozusagen zusammen geschrumpft haben die übrigen auch auf val überprüft haben ?
 
R

Rusticus1999

Mitglied
Ich habe offensichtlich einen Knoten im Kopf.... sollten nicht alle Werte überprüft werden ? Wie soll die Überprüfung von diesem einen Wert auf den wir das array sozusagen zusammen geschrumpft haben die übrigen auch auf val überprüft haben ?
Wir bauen einen "Baum" von arrays auf. Die Blätter also die letzten aufrufe haben nur noch einen wert im array, aber wir haben genau so viele "Blätter" wie stellen im array, also wird im Endeffekt innernoch jeder wert verglichen.
 
S

Soltan

Aktives Mitglied
Wir vergleichen doch arr nur einmal an der Stelle 0 ( das letzte Blatt ) und dieses Blatt ( auf das man durch die Teilung des arrays durch 2 kommt ) gibt es auch nru einmal ? Der erste und einzige Vergleich ist wenn das array nurmehr eine Stelle hat. Dann vergleichen wir eine Stelle eine Zahl bevor das ganze wieder rauf terminiert und nie mehr.... Viele Bäume ( arrays ) sind dann darüber aber alle haben mehrere Blätter und werden nicht mit val verglichen.
*seufz* Ich stehe ziemlich auf der Leitung mit dieser Rekursion Geschichte :/ Danke für eure Hilfe.

Mein Compiler akzeptiert den obigen Code übrigens nicht..."arr.copyOfRange(0,arr.length/2))" versteht er nicht. auch mit den java utils. Die Verkleinerung funkt nur wenn ich ein neues array anlege und dann Arrays.copyOfRange(...) benutze. Sicher dass man direkt auf den array namen diese methode aufrufen kann?
 
R

Rusticus1999

Mitglied
Falls möglich guck dir mal ein Videotutorial zum binarySearchTree an, das ist sehr ähnlich zu dieser Aufgabe und könnte deinem rekurions Verständnis helfen.
 
R

Rusticus1999

Mitglied
Wir vergleichen doch immer nur arr an der Stelle 0 ( das letzte Blatt ) und dieses Blatt ( auf das man durch die Teilung des arrays durch 2 kommt ) ist doch zwangsläufig immer dasselbe oder? Der erste und einzige Vergleich ist wenn das array nurmehr eine Stelle hat. Dann vergleichen wir eine Stelle eine Zahl bevor das ganze wieder rauf terminiert und nie mehr....
Mein Compiler akzeptiert den obigen Code übrigens nicht..."arr.copyOfRange(0,arr.length/2))" versteht er nicht. auch mit den java utils. Die Verkleinerung funkt nur wenn ich ein neues array anlege und dann Arrays.copyOfRange(...) benutze. Sicher dass man direkt auf den array namen diese methode aufrufen kann? *seufz* Ich stehe ziemlich auf der Leitung mit dieser Rekursion Geschichte :/ Danke für eure Hilfe.
Sorry klar.
The java.util.Arrays.copyOfRange(short[] original, int from, int to) method copies the specified range of the specified array into a new array.The final index of the range (to), which must be greater than or equal to from, may be greater than original.length, in which case (short)0 is placed in all elements of the copy whose index is greater than or equal to original.length - from. The length of the returned array will be to - from.
Du musst copyOfRange(arr, 0, arr.length/2)
Du musst das array mit übergeben und nich die Methode auf das array ausführen. Entschuldige die weitere Verwirrung. Wenn du array out of bounds kriegst. Musst du bei der letzten hälfte copyOfRange(arr, arr.length/2, arr.length-1) machen weil arr. Length die 0. Stelle mitzählt.
 
S

Soltan

Aktives Mitglied
Ok ich mach mir mal weitere Gedanken.... Ich hoffe das ist eines dieser Dinge wo einem irgendwann ein Licht aufgeht und dann ist es im Grund eh recht einfach.... vielen lieben Dank auch!!
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
R Noch eine Frage: Breite des Applets im Browser ermitteln Java Basics - Anfänger-Themen 7
N Und noch eine Frage über getRuntime() Java Basics - Anfänger-Themen 4
A Kann man eine Methode als Variable speichern und danach noch verändern? Java Basics - Anfänger-Themen 6
I fertige xml-datein in eine noch aufzubauende xml-datei einfügen Java Basics - Anfänger-Themen 4
M Und noch eine Java Basics - Anfänger-Themen 2
marcooooo einmal noch schnell hilfe bitte:/ Java Basics - Anfänger-Themen 2
M In gleicher zeile hinter ausgabe noch etwas ausgeben Java Basics - Anfänger-Themen 1
M Untersuchen ob ein Graph nach entfernen einer Kante immer noch zusammenhängend ist Java Basics - Anfänger-Themen 70
V_Fynn03 Erste Schritte BubbleSort Quelltext funktioniert noch nicht Java Basics - Anfänger-Themen 1
J Zweck von Interfaces immer noch nicht klar Java Basics - Anfänger-Themen 3
P Cäsear verschlüsselung irgendwas passt noch nicht Java Basics - Anfänger-Themen 2
B java.util.Date noch zeitgemäß? Java Basics - Anfänger-Themen 6
A Kfz - Händler Klasse. JUnit-Test gibt noch Fehler an, aber finde Ursache nicht Java Basics - Anfänger-Themen 7
L Taschenrechner mit switch und while funktioniert noch nicht richtig Java Basics - Anfänger-Themen 22
M Variable noch erstellen oder lieber so? Java Basics - Anfänger-Themen 1
V Bin eigentlich noch VOR dem Anfang .... Java Basics - Anfänger-Themen 9
T Anzeige, wie lange es noch dauert bis ein File gesendet ist. Java Basics - Anfänger-Themen 2
A Wie kann ich mein Programm noch effizienter machen? Java Basics - Anfänger-Themen 1
O Starte Timer, während anderer Timer noch läuft. Ruft dies Schwierigkeiten hervor? Java Basics - Anfänger-Themen 0
M Noch immer Probleme mit exec Java Basics - Anfänger-Themen 15
H Geht dieser Code noch einfacher (try catch finally) Java Basics - Anfänger-Themen 7
P Geht dieser Code noch einfacher? Java Basics - Anfänger-Themen 16
M Java von kopf bis Fuß noch zeitgemäß ? Java Basics - Anfänger-Themen 18
S noch ein ArrayIndexOutOfBoundsException Fehler Java Basics - Anfänger-Themen 2
Q queue.remove Element trotzdem noch vorhanden. Java Basics - Anfänger-Themen 10
S Musik einfügen funktioniert noch nicht Java Basics - Anfänger-Themen 6
P Noch zum Thema Arrays Java Basics - Anfänger-Themen 13
K Wofür wird heute noch die Stack Klasse in Java genutzt Java Basics - Anfänger-Themen 4
O Noch einmal Methoden Java Basics - Anfänger-Themen 9
T socket.close aber verbindung besteht noch Java Basics - Anfänger-Themen 4
C Threads Auffindung noch laufender Programmteile Java Basics - Anfänger-Themen 2
M Weder Consolenausgabe noch Fehlermeldung! Java Basics - Anfänger-Themen 5
E Prüfen, ob entfernte JVM noch aktiv ist? Java Basics - Anfänger-Themen 5
S ArrayList nur ergänzen wenn Element noch nicht vorhanden Java Basics - Anfänger-Themen 4
J Wie java programm noch schneller machen? Java Basics - Anfänger-Themen 30
C Umsteiger hat noch ein paar Fragen Java Basics - Anfänger-Themen 11
M immer noch usedelimiter Java Basics - Anfänger-Themen 4
M file löschen, streams evtl noch offen Java Basics - Anfänger-Themen 7
T Interfaces: Braucht man abstrakte Klassen eigentlich noch? Java Basics - Anfänger-Themen 3
K Bestehenden Chat modifizieren (noch ein Anfänger!) Java Basics - Anfänger-Themen 7
C Hilfe!!! Ich werd noch wahnsinnig... Java Basics - Anfänger-Themen 3
I Module und Testumgebung noch nicht verstanden... Java Basics - Anfänger-Themen 6
G Weder IE noch Firefox zeigen mir Java Applets an Java Basics - Anfänger-Themen 5
K Scrollpane - versteh nur noch Fragezeichen Java Basics - Anfänger-Themen 6
K Alle noch nicht umgedrehte Karten umdrehen ? Java Basics - Anfänger-Themen 2
S @ override + noch was Java Basics - Anfänger-Themen 3
D Kann noch fast nichts, funktioniert auch fast nichts! Java Basics - Anfänger-Themen 8
K Hier noch ein Konstruktor aufbauen Java Basics - Anfänger-Themen 6
G Threads prüfen, ob diese noch laufen. Java Basics - Anfänger-Themen 3
S Wie runden man noch mal auf bestimmte stellen? Java Basics - Anfänger-Themen 8
N Ich habs immer noch nicht hinbekommen :( Java Basics - Anfänger-Themen 3
D noch ein kleines Problem Java Basics - Anfänger-Themen 4
M OOP und ich - irgendwie verträgt sich das noch nicht. Java Basics - Anfänger-Themen 6
F jbutton and noch was^^ Java Basics - Anfänger-Themen 15
R Noch ein paar Anfängerfragen. Java Basics - Anfänger-Themen 4
G Array-Länge bei Erzeugung noch unbekannt - wie erzeugen? Java Basics - Anfänger-Themen 12
T Binärbaum - noch ein "klitzekleiner Fehler" Java Basics - Anfänger-Themen 4
P Textdateischreiben, etwas fehlt noch bzw. 1 error kommt Java Basics - Anfänger-Themen 4
L Noch immer Threat-Problem Java Basics - Anfänger-Themen 8
J referenz auf noch nicht erzeugte objekte? Java Basics - Anfänger-Themen 2
J Noch ein Parser Problem Java Basics - Anfänger-Themen 7
M Noch eins: TextFeldArray hinzufügen Java Basics - Anfänger-Themen 7
M Zufallszahlen fertig! aber nice to have noch offen Java Basics - Anfänger-Themen 5
C Abfragen, ob Objekt noch existiert Java Basics - Anfänger-Themen 5
A wieviel platz ist noch frei? Java Basics - Anfänger-Themen 2
J objektorientiert - noch immer nicht begriffen Java Basics - Anfänger-Themen 6
A Noch ne kleine Beanshell Frage Java Basics - Anfänger-Themen 7
S Testen ob ein Char Array noch nicht belegt ist! Java Basics - Anfänger-Themen 3
M Testen ob ein Sample noch abgespielt wird Java Basics - Anfänger-Themen 6
N Mittelwert (fast fertig, nur noch 2 fehler ;-) ) Java Basics - Anfänger-Themen 14
D Programm läuft - trotzdem noch ein Fehler drin. Java Basics - Anfänger-Themen 21
G Trotz Abfrage immer noch Zahlen doppelt Java Basics - Anfänger-Themen 3
G Wie war das noch´mal mit den Objekten? Java Basics - Anfänger-Themen 9
S Noch ungelöst ! Klasse JTable und Klasse Drucken verknüpfen. Java Basics - Anfänger-Themen 8
A Noch ein Anfänger..... Java Basics - Anfänger-Themen 7
G Fenster maximieren? Suche genutzt geht aber noch nich :( Java Basics - Anfänger-Themen 16
A noch mal bitoperater Java Basics - Anfänger-Themen 2
Tino1993 for-Schleife, die eine vorgegebene Anzahl von Zeichen ausgibt Java Basics - Anfänger-Themen 3
newcomerJava Nach doppelter Zahl eine Ausgabe Java Basics - Anfänger-Themen 10
jonny_2k12 Wie kann ich eine ArrayList aus einer Klasse in eine andere übergeben? Java Basics - Anfänger-Themen 21
S Eine Liste kopieren Java Basics - Anfänger-Themen 13
A eine neue normale String-Array von einer String-Array, die in for schleife ist, schaffen Java Basics - Anfänger-Themen 3
java3690 eine liste sortieren Java Basics - Anfänger-Themen 12
N Input/Output Eine Frage über system.out.println. Java Basics - Anfänger-Themen 10
K Übergabe des Wertes einer Variable aus main() in eine Klassenmethode Java Basics - Anfänger-Themen 8
J Wie kann ich hier eine While schleife einbauen? Java Basics - Anfänger-Themen 3
P Was genau bringt mir es ein Array in eine Liste zu bringen Java Basics - Anfänger-Themen 3
J Eine Frage zur Schreibweise == ? : Java Basics - Anfänger-Themen 3
I Wo am besten eine String Konstante initialisieren? Java Basics - Anfänger-Themen 5
N Wie teste ich eine geworfene Exception? Java Basics - Anfänger-Themen 8
B Eine Methode erstellen Java Basics - Anfänger-Themen 3
L Konstruktor für eine Map-Datei/Map-Datei einlesen Java Basics - Anfänger-Themen 5
Y Methoden Wie kann ich eine if-Abfrage bei Setters bauen? Java Basics - Anfänger-Themen 6
I Sortiert eine HashMap nicht gleich wie eine ArrayList? Java Basics - Anfänger-Themen 1
L Iterieren durch eine ArrayList. Integer Array wird übergeben Java Basics - Anfänger-Themen 17
KogoroMori21 Mit einer Schleife eine Treppe zeichnen Java Basics - Anfänger-Themen 29
J Eine Position im String durch einen Integer - Wert teilen Java Basics - Anfänger-Themen 5
M Verständnisfrage zu eine Online Aufgabe Java Basics - Anfänger-Themen 7
N Wie kann ich eine meine Variable Final machen? Java Basics - Anfänger-Themen 1
H Datentypen Was für eine Format verbirgt sich hinter dem Integer-Wert 053? Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben