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

  • 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:

    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

  • 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.

    Stefan Spelitz
    [Computergraphik UE Tutor 2017SS]

  • 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).

  • 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".

    Willfähriges Mitglied des Fefe-Zeitbinder-Botnets und der Open Source Tea Party.

  • 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

  • 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.

  • 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 :)

  • Wir scheinen wohl an der gleichen Uni zu sein :D

    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? 8|

  • 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?

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • Also zum IndexOutOfBounds sieht der Code bei mir so aus:


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


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

  • @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.

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • @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.

    Einmal editiert, zuletzt von Ycul (8. Dezember 2013 um 19:16)


  • 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.

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

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

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!