Finden des kleinsten Elements in einem Array (rekursiv und ohne Schleifen)

Roflkopf

Hallo zusammen,

ich habe eine Aufgabe bekommen, bei der ich eine Methode schreiben muss, die aus einem übergebenen int-Array das kleinste Element zurückgibt. Diese Methode soll ganz ohne Schleifen auskommen und rekursiv arbeiten. Als Hinweis ist gegeben, dass wir den übergebenen Array in 2 (möglichst) gleichgroße Teile aufteilen sollen. Das habe ich noch hinbekommen, allerdings weiß ich jetzt nicht wirklich wie es weitergehen soll.

Bis jetzt habe ich folgendes:

Code

public int getSmallestElement(int[] array, int start, int ende){

       int smallest = 0;
       int[] hilf1;
       int[] hilf2;
       int length1 = array.length / 2;
       int length2 = (array.length / 2) + 1;

       if(array.length % 2 == 0)
       {
           hilf1 = new int[array.length / 2];
           System.arraycopy(array, start, hilf1, 0, array.length/2);
           hilf2 = new int[array.length / 2];
           System.arraycopy(array, array.length/2, hilf2, 0, array.length/2);
       }
       else
       {
           hilf1 = new int[length1];
           System.arraycopy(array, start, hilf1, 0, length1);
           hilf2 = new int[length2];
           System.arraycopy(array, length2-1, hilf2, 0, length2);
       }

       return smallest; //damit ist noch nichts passiert, ich weiß :P
   }

Alles anzeigen

Der Array soll beliebig lang sein und, dass start bzw ende übergeben werden, war vorgegeben.

Ich bitte um Tipps, nicht um die Lösung.

Ach und wir benutzen BlueJ.

LG

2#4u

Rekursionen sind am Anfang ein bisserl schwer zu verstehen, aber im Prinzip ist es ganz einfach:

Du unterteilst in jedem Aufruf deiner Methode das Array in 2 Teile - das hast du ja schon.
Und sinnvollerweise machst du jetzt etwas mit diesen 2 Arrays. Nämlich was? Richtig! Weiter unterteilen. Und wie unterteilen wir ein Array - Ach ja - hast du ja schon geschrieben

Wenn jetzt immer weiter unterteilt wird, kommt irgendwann der Punkt an dem nicht mehr weiter unterteilt werden kann.
Sprich: Bei genau einem Element kann nicht mehr weiter unterteilt werden. Und gleichzeitig ist das minimale Element in einem Array mit nur einem Element genau dieses eine Element.

Interessant wird es aber bei einem Array mit 2 oder mehr Elementen:
- Was man mit einem Array mit N Elementen machen muss, wissen wir bereits. Unterteilen...
- Die spannende Frage ist aber was man mit den Ergebnissen der rekursiven Aufrufe macht - Denk mal drüber nach und bei Fragen meld dich wieder.

spinball

Zitat

Ich bitte um Tipps

Wenn int start, int ende in der Angabe steht, dann will dein Lehrer, dass du keinen Speicherplatz verschwendest. Folgendes muss weg:

PHP

int[] hilf1;
int[] hilf2;
new int[ ... ];
System.arraycopy( ... );

Stattdessen will er, dass du nur start und ende veränderst. Modulo brauchst du auch nicht. Und weil es rekursiv sein soll, muss die Methode sich selbst wieder aufrufen (Hypertipp: in deinem Beispiel exakt zwei mal).

Kampi

du kannst dir auch den ersten teil von mergesort und die visualisierungen ansehen, das hilft wohl auch. dein problem ist sehr nahe dran, und auf die schnelle die einzige argumentation warum die ursprüngliche aufgabenstellung ueberhaupt sinn ergeben kann. sonst ist es eher ein "wir lernen rekursion anhand eines praxisuntauglichen beispiels".

Roflkopf

spinball
Ich hab nochmal nachgefragt und du hast Recht, start bzw. ende sollen verändert werden.
Habe jetzt nochmal neu angefangen und bin auf Folgendes gekommen:

Code

public int getSmallestElement(int[] array, int start, int ende){         
if (start==ende)
       return array[start];

return Math.min(getSmallestElement(array, start, ende/2), getSmallestElement(array, (ende/2), ende)); 

   }

Da bekomme ich allerdings jetzt einen StackOverflowError, was start==ende betrifft
Irgendwelche weiteren Tipps? :p

Lacuno

Die linke Rekursion ist ok, jedoch liefert dir die rechte eine Endlosrekursion.

Kurzes Beispiel:
Du hast 5 Elemente in deinem Array und rufst jetzt deine getSmallestElement-Methode auf (getSmallestElement(array, 0, 4) )
Die linke Rekursion ruft nun getSmallestElement(array, 0, 2) auf und die rechte Rekursion ruft getSmallestElement(array, 2, 4) auf.
Ich ignorier jetzt mal die linke Rekursion und geh weiter auf die rechte ein:
Diese wird erneut getSmallestElement(array, 2, 4) aufrufen (Da sich ende/2 zu 2 auswertet).
Usw..

Du darfst hier also nicht annehmen, dass der Start immer 0 ist.

Roflkopf

Super, danke Lacuno, hat mir sehr geholfen. Ich habs jetzt endlich geschafft :thumb:

Code

public int getSmallestElement(int[] array, int start, int ende){  
       if (start==ende)
           return array[start];

       int mittel = (start+ende)/2;
       return Math.min(getSmallestElement(array, start, mittel), getSmallestElement(array, mittel+1, ende)); 

   }

Danke nochmal an alle und LG

Ycul

Wir scheinen wohl an der gleichen Uni zu sein

Ich hatte den Code auch erst wie am Anfang, hatte es dann mit dem letzten Code von Roflkopf etwas anders versucht, aber da bekam ich StackOverflow. Und wenn ich das gleiche if verwende kommt bei mir ArrayIndexOutOfBoundsException. Bist du sicher, dass der Code richtig ist?

Bradon

StackOverflow laesst auf eine Endlosrekursion schliessen. Bist du sicher, dass du den Code richtig uebernommen hast?
Bei einer ArrayIndexOutOfBoundsException wuerde ich vermuten, dass dein initialer Aufruf nicht korrekt ist.. Uebergibst du vielleicht array.length als ende?

Ycul

Also zum IndexOutOfBounds sieht der Code bei mir so aus:

Code

public int getSmallestElement(int[] array, int start, int ende) {


       if (start == ende) {
            return array[start];
       }

       else { 
       int mid = (start+ende)/2;
       return Math.min(getSmallestElement(array, start, mid), getSmallestElement(array, mid+1, ende)); 
       }
    }

Alles anzeigen

Also im Vergleich zu Roflkopf hab ich nur mittel zu mid geändert.
Und beim StackOverflow hatte ich

Code

public int getSmallestElement(int[] array, int start, int ende) {


       if (array.length == 1) {
            return array[0];
       }

       else { 
       int mid = (start+ende)/2;
       return Math.min(getSmallestElement(array, start, mid), getSmallestElement(array, mid+1, ende)); 
       }
    }

Alles anzeigen

bzw. zuerst array.length<=1, aber da kam das gleiche.

Bradon

@IndexOutOfBounds: Ich meinte den Aufruf in der main-Methode, der die Rekursion beginnt

stackoverflow: Das Array-Objekt ist in jedem rekursiven Aufruf das gleiche, das heisst seine Laenge veraendert sich nie. Es kann daher auch nie die Laenge 1 erreichen.

Ycul

Zitat von Bradon

@IndexOutOfBounds: Ich meinte den Aufruf in der main-Methode, der die Rekursion beginnt

Äh... Das ist die einzige Methode dazu.

Zitat

stackoverflow: Das Array-Objekt ist in jedem rekursiven Aufruf das gleiche, das heisst seine Laenge veraendert sich nie. Es kann daher auch nie die Laenge 1 erreichen.

Ja, dass das nicht stimmt wurde mir auch schon gesagt, deswegen hab ich das geändert.

Edit: Ich hab das darüber getestet, dass ich ein neues Objekt erzeuge und da die Methode ausführ. Hab da 7 Elemente eingegeben für das array, start = 0 und ende = 7, weil in der Aufgabe steht, das Intervall soll [start;ende) sein, also exklusive ende. Hab jetzt mal statt 7 6 eingegeben für ende und es ging.

Bradon

Zitat von Ycul

Edit: Ich hab das darüber getestet, dass ich ein neues Objekt erzeuge und da die Methode ausführ. Hab da 7 Elemente eingegeben für das array, start = 0 und ende = 7, weil in der Aufgabe steht, das Intervall soll [start;ende) sein, also exklusive ende. Hab jetzt mal statt 7 6 eingegeben für ende und es ging.

Richtig, ein Array mit 7 Elementen hat die Indices 0-6, der Zugriff auf array[7] fuehrt zu einer ArrayIndexOutOfBoundsException. Daher muss der ende-Parameter 6 sein.

Ycul

Zitat von Bradon

Richtig, ein Array mit 7 Elementen hat die Indices 0-6, der Zugriff auf array[7] fuehrt zu einer ArrayIndexOutOfBoundsException. Daher muss der ende-Parameter 6 sein.

In der Aufgabenstellung steht eben [start;ende), demnach müsste ende ja eigentlich eins höher als der letzte Index sein.

Jetzt mitmachen!