# Rekursive Teile und Herrsche Methode zum Teiler bestimmen



## bLaSt (7. Jun 2011)

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



Vielen Dank schon mal für eure Hilfe

Gruß

blast


----------



## Andi_CH (7. Jun 2011)

Beginn mal damit uns das "teile und herrsche" Prinzip zu erklären - bei der Umsetzung in Java helfen wir dann schon.


----------



## XHelp (7. Jun 2011)

Welche Ansätze hast du und was erwartest du von uns?


----------



## bLaSt (7. Jun 2011)

bLaSt hat gesagt.:


> Hey Leute. Ich hab folgendes Problem und keine Ahnung wie ich es angehen soll:
> Anhang anzeigen 2985
> 
> 
> ...



Das Problem ist halt das ich keine Ahnung hab wie ich den algorithmus überhaupt machen soll.


----------



## Andi_CH (7. Jun 2011)

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 (7. Jun 2011)

Ungefähr so:


```
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);
    }
}
```


----------



## chalkbag (7. Jun 2011)

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.



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


----------



## bLaSt (7. Jun 2011)

Andi_CH hat gesagt.:


> 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 (7. Jun 2011)

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


----------



## Landei (8. Jun 2011)

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

Ansonsten: Rekursion ? Kamelopedia


----------



## Andi_CH (8. Jun 2011)

bLaSt hat gesagt.:


> 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 (8. Jun 2011)

Landei hat gesagt.:


> 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 (11. Jun 2011)

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


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


----------



## XHelp (11. Jun 2011)

bLaSt hat gesagt.:


> Was ist das hier denn für ein Konstrukt?



Du willst vermutlich auf 
	
	
	
	





```
int...
```
 hinaus: Galileo Computing :: Java ist auch eine Insel – 3.7 Arrays


----------



## bLaSt (11. Jun 2011)

XHelp hat gesagt.:


> Du willst vermutlich auf
> 
> 
> 
> ...



ja das schon...das mit den mehreren Punkten zeigt ja an,dass noch nicht bekannt ist wie lang es werden soll wenn ich mich recht erinnere. Aber ich hab das mit dem "public new" noch nie gesehn^^


----------



## Landei (11. Jun 2011)

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


----------



## bLaSt (12. Jun 2011)

Landei hat gesagt.:


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



ah super...thy^^


----------

