Noch eine Frage zur Rekursion...

[Soltan]

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]

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)

 

[Rusticus1999]

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.

 

[Soltan]

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.

 

[Rusticus1999]

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.

 

[Soltan]

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 ?

 

[Rusticus1999]

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.

 

[Soltan]

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?

 

[Rusticus1999]

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.

 

[Rusticus1999]

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.

 

[Soltan]

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!!

 

[Rusticus1999]

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!!

Viel Erfolg. Wie gesagt. Versuch den binarySearchTree zu verstehen.