Rekursive Teile und Herrsche Methode zum Teiler bestimmen

bLaSt

Aktives Mitglied
Hey Leute. Ich hab folgendes Problem und keine Ahnung wie ich es angehen soll:
Unbenannt.JPG


Vielen Dank schon mal für eure Hilfe

Gruß

blast
 

Andi_CH

Top Contributor
Wie geht der Algorithmus denn? Ich bin 100% sicher, dass von dir nichts verlangt wird, was nicht zuvor besprochen wurde ;-)
Ansonsten google, wikipedia - sorry, aber wir helfen bei Java.
 

Landei

Top Contributor
Ungefähr so:

Java:
public class BinMalNichtSoWeilGleichFeieraberndIst {

    private final int[] array;
    private int count = 0; 

    public new BinMalNichtSoWeilGleichFeieraberndIst(int z, int... array) {
       this.array = array;
       rmeth(0, array.length-1, z);
       System.out.println("Ersetzungen: count");
       System.out.println("Array: " + java.util.Arrays.toString(array));
    }
   
    public void rmeth(int left, int right, z) {
         //ist der Abschnitt leer -> fertig
         //ist der Abschnitt genau 1 Element lang: Schauen, ob man ersetzen muss (dann immer schön count hochzählen)
         //ist der Abschnitt länger als 1, Mitte bestimmen und rekursiv beide Teilabschnitte aufrufen
    }

    public static void main(String... args) {
        new BinMalNichtSoWeilGleichFeieraberndIst(3, 27,11,63,6454,23,5,3,67);
    }
}
 
Zuletzt bearbeitet:

chalkbag

Bekanntes Mitglied
Der Quicksort funktioniert nach diesem Prinzip,

einfach folgende Methode (Quelle: Wikipedia) umschreiben, so dass nicht sortiert sondern eben gewünschter Effekt durchgeführt wird. Zusätzlich noch mitzählen und als Ergebnis der rekursiven Methode zurückgeben.


Java:
 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler-1)
         quicksort(teiler+1, rechts)
     ende
 ende
 

bLaSt

Aktives Mitglied
Wie geht der Algorithmus denn? Ich bin 100% sicher, dass von dir nichts verlangt wird, was nicht zuvor besprochen wurde ;-)
Ansonsten google, wikipedia - sorry, aber wir helfen bei Java.

Das IST Java^^
Aber es wird einem halt nicht alles vorgekaut. Wir hatten das Teile-und-Herrsche Prinzip und Rekursion und daraus entstand die Aufgabe.
 

bLaSt

Aktives Mitglied
das umschreibt wohl am besten das Teile-&Herrsche Prinzip:
Bei einem „teile und herrsche“-Ansatz wird das eigentliche Problem so lange in kleinere und einfachere Teilprobleme zerlegt, bis man diese lösen („beherrschen“) kann. Anschließend wird aus diesen Teillösungen eine Lösung für das Gesamtproblem (re-)konstruiert.

Mein Problem ist einfach,dass ich nicht weiß wie ich das anpacken soll. die signatur der methode für den algorithmus ist ja vorgegeben. steht ja in der aufgabe. und naja...iwie keine ahnung^^
 

Andi_CH

Top Contributor
Das IST Java^^
Aber es wird einem halt nicht alles vorgekaut. Wir hatten das Teile-und-Herrsche Prinzip und Rekursion und daraus entstand die Aufgabe.

Ein Alogrithums wie "Teile und herrsche" hat NICHTS mit Java zu tun - der kann in jeder beliebigen Sprache implementiert oder sogar ohne Computer durchgespielt werden.
Solche aufgaben haben immer zwei Ziele. Einerseits solltest du den im Unterricht besprochenen Alogrithums begreifen indem du ihn umsetzt und nebenbei noch Java lernen.
Andreresetis könnte es auch ein Ziel sein euch auf das reale Leben vorzubereiten indem eben nicht alles vorgegeben ist und wo du erst einmal Inforamtionen z.B bei wikipeida beshaffen und dann umsetzen musst.

Kopieren von fertigen Lösungen bringen die keinen Mikrometer weiter.
 

bLaSt

Aktives Mitglied
Da schreib ich mir oben die Finger wund... Hast du dir das wenigstens mal angeschaut? Wenn ja, wo klemmts noch?

Ansonsten: Rekursion ? Kamelopedia

Sorry natürlich hab ichs durchgelesen. Danke das hilft mir schon weiter.

@Andi: Ich will ja auch keine Lösung zum rauskopieren. Einfach einen Ansatz, und das Beispiel,dass wir in der Vorlesung dazu hatten, war nicht wirklich hilfreich. Ich wusste nur nicht, wie ich anfangen sollte. Aber Landei hat mir schon sehr gut geholfen. Ich hab halt allgemein ein bisschen Probleme damit eine geeignete Rekursion für ein Problem zu finden.
Aber wenn man nicht mal nach Ansätzen fragen darf, wozu gibt es dann dieses Forum? Ich dachte genau dafür ist es doch da.

Gruß

blast
 

bLaSt

Aktives Mitglied
Hey Landei. Also ich hätte da noch eine Frage an dich. Was ist das hier denn für ein Konstrukt?

Java:
public new BinMalNichtSoWeilGleichFeieraberndIst(int z, int... array) {
       this.array = array;
       rmeth(0, array.length-1, z);
       System.out.println("Ersetzungen: count");
       System.out.println("Array: " + java.util.Arrays.toString(array));
    }
Das versteh ich einfach nicht, weil irgendwie ist das ja eine Methode aber auch iwie eine Array Erzeugung oder wie?
Danke schonmal!
 

Landei

Top Contributor
Oh sorry, das sollte ein ganz normaler Konstruktor werden - das [c]new[/c] ist zuviel

Wahrscheinlich hatte ich den Namen von weiter unten kopiert und das new versehentlich mitgenommen...
 
Zuletzt bearbeitet:

Neue Themen


Oben