# rekursive Teile und Herrsche Methode zum Teiler bestimmen



## Greenhorn (22. Jun 2011)

Hallo zusammen,

ich habe folgende Aufgabe zu bewältigen:

_Entwickeln Sie eine rekursive Java-Methode *int rmeth(int left, int right, int z);*
die in einem Array von Integer-Zahlen mit Hilfe des Teile-und-herrsche-
Prinzips alle Zahlen, die durch z teilbar sind, durch 0 ersetzt und die Anzahl,
wieviele *Ersetzungen* durchgefÄuhrt worden sind, als RÄuckgabewert zurÄucklie-
fert._

*Folgend mein Code*, leider ist aber die Aussgabe nicht richtig, da er einfach alle Feldkomponenten ausgibt. Die System.out.println Anweisungen in der while-Schleife dienen nur zum manuellen Debuggen. Leider bis her ohne Erfolg.


```
public class Main {
	
	public Main (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));
	       
	}
	
    private final int[] array;
    private int count = 0; 

   
    public int rmeth(int left, int right, int z) {
    	 
    	int i = 0;
    	int j = array.length-1;
    	i = left;
    	j = right;
    	//Quick sort
    	int pivot = array[(left + right)/2];
    	 
    	
    	System.out.println("vor"); 									//zum Debuggen
    	
    	while(i <= j){ 			
    		while(array[i] < pivot && i < j){
    			i++;
    			System.out.println("array[i]: " +array[i]);		//zum Debuggen
    			System.out.println("pivot: " +pivot);		//zum Debuggen
    		}
    		
    		
    		while(array[j] >= pivot && j > i){
    			j--;
    			System.out.println(array[j]);
    			System.out.println(pivot);
    		}
    		
    		if(i < j){
    			if(((pivot/z)%2)==0){
    				pivot = 0;
    				count++;
    			}
    			i++;
    			j--;
    		}
    		
    	}
    	
    	System.out.println("nach2");						 //zum Debuggen
    	
    	//Rekursion
    	if(left < j){
    		rmeth(left, j, z);
    	}
    	if(i < right){
    		rmeth(i,right, z);
    	}
    	
    	   	
    	return count;
    }
 
    public static void main(String... args) {
        new Main(3, 6,9,12,5,7,5,3,14);
    }
}
```


In der Konsole wird ausgeben:

```
vor
3
5
7
5
5
5
12
5
9
5
```

Was ich nicht verstehe??? Wahrscheinlich sehe ich den Wald vor lauter Bäumen nicht mehr, aber ich find da keinen grundsätzlichen Fehler.

Es wäre wirklich hilfreich wenn mich jemand bei der Fehlersuche unterstützt, denke es ist ein Anfängerfehler!

Daher greenhorn ;-)

Gruß und danke im Voraus


----------



## Final_Striker (22. Jun 2011)

Du brauchst keine Schleifen, du sollst das doch rekursiv machen.


----------



## Greenhorn (22. Jun 2011)

Vielen Dank Final Stryker für die sehr schnelle Reaktion!

Aber die einzigen Schleife die ich benutze (3x while), dienen doch dem "Teile-und-herrsche-Verfahren" und nicht der Iteration, oder? die While-Schleifen dienen doch nur der Zerlegung des Problems in unteren Hälfte (links) und obere Hälfte (rechts).

Nach "Teile-und-Herrsche" rufe ich doch durch folgenden Zeile die Methode slbst wieder auf:


```
//Rekursion
        if(left < j){
            rmeth(left, j, z);
        }
        if(i < right){
            rmeth(i,right, z);
        }
```

Oder?


----------



## Final_Striker (22. Jun 2011)

```
public class Main {
	
	public Main (int z, int... array) {
		
	       this.array = array;
	       rmeth(0, array.length-1, z);
// Warum rufst du die Methode im Konstruktor auf? 1. unnötig 2. unschön 3. sehr unpraktisch

	       System.out.println("Ersetzungen: " +count);
	       System.out.println("Array: " + java.util.Arrays.toString(array));
	       
	}

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

   
    public int rmeth(int left, int right, int z) {
    	 
    	int i = 0;
    	int j = array.length-1;
    	i = left;
// erst weist du dem i eine 0 zu und 2 Zeilen später left, irgendwie unnötig, oder?
// wobei i und j genauso unnötig sind, du hast ja schließlich left und right
    	j = right;
    	//Quick sort
    	int pivot = array[(left + right)/2];
    	 
    	
    	System.out.println("vor"); 									//zum Debuggen
    	
    	while(i <= j){ 			
    		while(array[i] < pivot && i < j){
    			i++;
    			System.out.println("array[i]: " +array[i]);		//zum Debuggen
    			System.out.println("pivot: " +pivot);		//zum Debuggen
    		}
    		
    		
    		while(array[j] >= pivot && j > i){
    			j--;
    			System.out.println(array[j]);
    			System.out.println(pivot);
    		}
    		
// du rufst if in der Schleife auf, kann also nur falsch sein
    		if(i < j){
    			if(((pivot/z)%2)==0){
    				pivot = 0;
    				count++;
    			}
    			i++;
    			j--;
    		}
    		
    	}
    	
    	System.out.println("nach2");						 //zum Debuggen
    	
// die Methode rmeth hat einen Rückgabewert int, bei dir geht er einfach verloren.
    	if(left < j){
    		rmeth(left, j, z);
    	}
    	if(i < right){
    		rmeth(i,right, z);
    	}
    	
    	   	
    	return count;
    }
 
    public static void main(String... args) {
// erstelle ein Objekt und rufe dann die Methode meth auf
        new Main(3, 6,9,12,5,7,5,3,14);
    }
}
```

Edit:

Ach ja und die durch z teilbare Zahlen ersetzt du auch nirgends durch 0.


----------



## ChrisKu (22. Jun 2011)

Sorry, wenn ich mich mal kurz einmische, aber was ist das denn eine Methode rmeth()? Sollst Du einen Quicksort Algo implementieren oder die Zahlen ersetzen? Ich habe nur mal kurz gegoogelt, was eine Teil- und Herrsche Methode ist, aber m.E. würde folgendes funktionieren:

```
public int rmeth(int left, int right, int z) {
         
        if (array[left]%z == 0){
            System.out.println("Ersetze die" + array[left]);
            array[left] = 0;
            count ++;
        }
        left++;
        
        if (left <= right){
            rmeth(left, right, z);
        }
            
        return count;
    }
```


----------



## Greenhorn (22. Jun 2011)

@ Final-Striker: nochmals Danke für die vielen Anmerkungen im Code. Das muss ich erstmal alles checken. 

Aber zu Edit-Kommentar, dass ich durch z teilbare Zahlen nicht mit 0 ersetze, dazu sollte eigentlich die untere if-Abfrage dienen. Muss aber sagen, dass ich die Adaptierung von QuickSort auf Aufgabenstellung noch nicht ganz durchdrungen habe!


```
if(i < j){
                if(((pivot/z)%2)==0){
                    pivot = 0;
                    count++;
                }
                i++;
                j--;
            }
```


----------



## Greenhorn (22. Jun 2011)

@ChrisKu: Aufgabe ist es Zahlen die durch z teilbar sind mit 0 zu ersetzen. Ich habe dazu den QuickSort adaptiert, da es das einzige passende Verfahren (Teile-und-Herrsche + rekursiv) ist das ich im Skript habe. Statt swap tauschen, wollte ich eine Modulo Berechnung einfügen.

Zu deiner Lösung: Die sieht besser aus als meine. Gibt mir aber muht da ich so flasch nicht gelegen bin. Muss ich erstmal versuchen zusammen mit Final-_Strikers Anmerkungen einzufügen.


```
if(i < j){
                if(((pivot/z)%2)==0){
                    pivot = 0;
                    count++;
                }
                i++;
                j--;
            }
```

Vielen Dank!


----------



## Final_Striker (22. Jun 2011)

teile und herrsche bedeutet:

Teile das Problem so lange bis du es direkt lösen kannst. Dein Problem kannst du direkt lösen, wenn dein geteiltes Array nur noch 1 Element enthält, also *left* gleich *right* ist.


----------



## ChrisKu (22. Jun 2011)

> Muss aber sagen, dass ich die Adaptierung von QuickSort auf Aufgabenstellung noch nicht ganz durchdrungen habe!



Ich glaube, das hat nichts miteinander zu tun. Wenn ich das Prinzip "Teile und Herrsche" richtig verstanden haben bedeutet es, ein größeres Problem in kleinere aufzuteilen, die leicht zu lösen sind. Ob das bei Deinem speziellen Problem wirklich sinnvoll ist, dieses Prinzip anzuwenden, sei dahingestellt. Aber ich vermute, es geht bei der Aufgabe erst einmal nur um das Prinzip der rekursiven Aufrufe. Und dabei hilft Dir der ganze Sortiercode in den while Schleifen glaube ich nicht.


----------



## Greenhorn (22. Jun 2011)

okay, also wenn ich euch richtig verstanden habe, dann ist der Ansatz von ChrisKu der richtige und bei mir vermischt sich u.a. zu viel sinnloses durch zu starke Orientierung an QuickSort, ergo die ganzen While-Schleifen müssen raus? Deshalb wahrscheinlich auch die erste Amerkung von Final Striker?


----------



## Final_Striker (22. Jun 2011)

Greenhorn hat gesagt.:


> While-Schleifen müssen raus?


Jep.



```
public int meth(int l, int r, int z){

		if(l == r){
			// Problem gelöst
			// kann direkt entscheiden
			...
		}
		else{
			// Problem nicht gelöst
			// muss weiter teilen (am besten das Array in 2 Teile teilen)
			...
		}
	}
```


----------



## Greenhorn (22. Jun 2011)

okay, 

prinzipiell hab ich´s jetzt schon eher verstanden! ChrisKu Version funktioniet, wollte mein Programm entsprechend eueren Kommentaren anpassen, aber meine CPU ist bei 100% und ich bekomm gar nix mehr in eclipse eingetippt, daher  dauert´s wohl länger bis ich das alles vollends korregieren kann. Schließe ich Eclipse bin ich noch bei 3% CPU

Aber auf jeden Fall schon mal vielen Dank für euere sehr guten Kommentare! :toll:


----------



## Greenhorn (22. Jun 2011)

@ChrisKu

 Deine Lösung wirkt simpel und gut zugleich, aber ich versteh nicht ganz wo sich das Prinzip Teile und Herrsche erkennbar macht. Im Grunde läuft die Methode doch nun von unten links immer eins nach oben (left++), also wie in einer normalen Schleife, oder? Oder entspricht die Zeile 
	
	
	
	





```
if (array[left]%z == 0){
```
 Final-Strikers Ansatz mit 
	
	
	
	





```
if(l == r)
```
?

Leider kann ichs nicht vollends testen weil meine CPU dann auf 100% hochschnellt.



```
public  int rmeth(int left, int right, int z) {       
        if (array[left]%z == 0){
            System.out.println("Ersetze die " + array[left]);
            array[left] = 0;
            count ++;
        }
        left++;
```


----------



## Final_Striker (23. Jun 2011)

Greenhorn hat gesagt.:


> aber ich versteh nicht ganz wo sich das Prinzip Teile und Herrsche erkennbar macht.



Gar nicht, aus diesem Grund haben ich dazu geschrieben, dass man das Array in 2 Teile teilen soll.
Außerdem ist das mit dem *count* nicht korrekt. Eine globale Variable count ist nicht notwendig.


```
if (left <= right){
            rmeth(left, right, z); // hier wieder der Rückgabewert nicht verwendet
        }
```


----------



## Greenhorn (23. Jun 2011)

Ich kappiere es einfach nicht ganz!:bahnhof:

 Wie teile ich das Feld in 2 Teile auf? Siehe Fragen im Code



```
package a1;

public class Test2 {

	public Test2 (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));
	}
	
	private  final int[] array;
	private  int count = 0;
		
	public int rmeth(int left, int right, int z) { 
		
		if(left == right){
			if (array[left]%z == 0){
	            array[left] = 0;
	            count ++;			
			}			
			left++;
		}
		else{
			/*wie kann ich hier das Feld in 2 Teile teilen ohne i,j und pivot zu nutzen?
			 * int pivot = array[(left + right)/2] wie bei Quicksprt gilt ja nicht mehr!?
			 * gilt einfach:
			 *  left = array[(left + right)/2];
			 *  rmeth(left, right, z);
			 *  ??
			 */
		}
		    
        if (left <= right){
            rmeth(left, right, z);
        }
            
        return count;
    }


	public static void main(String... args) { 
		//Test2 test = new Test2 (3, 6,9,12,5,7,5,3,14);
		//test.rmeth(0, array.length-1, z);
		new Test2(3, 6,9,12,5,7,5,3,14);
	}


}
```


----------



## Final_Striker (23. Jun 2011)

Relativ einfach

rmeth(0, 7, 5) // Array von 0 bis 7

teilen ->

rmeth(0, 3, 5)  // Array von 0 bis 3
rmeth(4, 7, 5)  // Array von 4 bis 7


----------



## Greenhorn (23. Jun 2011)

ich erkenne:

1. Rekursion direkt in else einbauen.
2. zum teilen in else keine neuen variablen deklarieren
3. Prinzip des Teilens bleibt gleich wie bei Quicksort, d.h. die 3 im Beispiel oben entspricht pivot.

4. Was ich nicht verstehe wie sieht das im code dann aus, etwa:


```
}else{
  rmeth(left, (left+right/2), z);
  rmeth((left+right/2)+1, right, z);
}
```


----------



## Final_Striker (23. Jun 2011)

Greenhorn hat gesagt.:


> Was ich nicht verstehe wie sieht das im code dann aus, etwa:



Jep, nur das du den Rückgabewert der Methoden noch abfangen musst.


----------



## Greenhorn (23. Jun 2011)

1. Der Rückgabetyp ist ein int und dient für Ausgabe von count. 
2. Die Methode erwartet bei jedem Aufruf, also auch für die Rekursionen, eine Rückgabe von return count;
3. Bei der Rekursion will ich aber keine Rückgabewerte abgeben, da ja nur hochgezählt werden soll falls, if  ( (array%z == 0)

soweit korrekt?


4. Also brauche ich in dem rekrusiven Methodenaufruf eine Anweisung "no return"? Mit try, catch hat das hoffentlich nix zu tun, oder?​


----------



## Final_Striker (23. Jun 2011)

Du brauchst keine Variable count und genauso wenig ein "no return" (wüsste auch nicht das es so was gibt).

Rückgabewerte abfangen, addieren und weiter zurückgeben.


----------



## Greenhorn (23. Jun 2011)

Also ich kenne die Möglichkeit "Rückgabe abfangen" nicht! Über google find ich auch nix.

"no retrun" gibt es sicherlich nicht, war nur ein Ausdruck von mir um meinen Gedankengang zu erklären!


----------



## Final_Striker (23. Jun 2011)

Jo, kannst es auch Rückgabewert verwenden oder Rückgabewert speichern oder wie auch immer nennen. 


```
int i = rmeth(...); // Rückgabewert wird abfangen und kann verwendet werden
rmeth(left, (...); // Rückgabewert wird ignoriert und geht verloren
```


----------



## Greenhorn (23. Jun 2011)

Also,

else{
      int count= rmeth(left,(left+right/2), z);
         count = rmeth((left+right/2)+1, right, z);
 }

kann nicht sein, oder?

Verstehe den Sinn nicht


----------



## Greenhorn (23. Jun 2011)

Ne, also raff ich nicht! Sowas hab ich noch nie gesehen. Gut klar, ich hab in java auch noch nicht viel gesehen, aber trotzdem. Ich rufe eine Methode rekrusiv auf und weiß den aufruf einem int zu....??????:L


----------



## Final_Striker (23. Jun 2011)

Ich habe es jetzt so gelöst, aber es gibt da sicher auch viele andere Möglichkeiten.


```
public int meth(int l, int r, int z){
		
		if(l == r){
			if(arr[l]%z == 0){
				arr[l] = 0;
				return 1;
			}
			else
				return 0;
		}
		else{
			int m = (l + r)/2;
			return meth(l, m, z) + meth(m+1, r, z);
		}
	}
```


----------



## Greenhorn (23. Jun 2011)

Ok vielen Dank, wirkt noch komplizert auf mich, da ich ab 2 else noch nicht verstehe was passiert. Letzlich ist m doch ähnlich wie count, oder? 

Und wie gebe ich dann die Anzahl der Ersetzungen aus, wenn es dafür keine Variable mehr gibt? 
	
	
	
	





```
System.out.println("Ergänzungen: " + count)
```
 gibts ja nicht mehr!


----------



## Greenhorn (23. Jun 2011)

Ich wollte es grad mal über eclipse laufen lassen, aber er erkennt "array" im Konstruktor nicht mehr! 


```
public class Test3 {

	public Test3 (int z, int... array){
		this.array = array;
		System.out.println("Ersetzungen: " +rmeth(0, array.length-1, z));
		System.out.println("Array: " + java.util.Arrays.toString(array));
	}

	
	 public int rmeth(int links, int rechts, int z){
	        
	        if(links == rechts){
	            if(array[links]%z == 0){
	                array[links] = 0;
	                return 1;
	            }
	            else
	                return 0;
	        }
	        else{
	            int m = (links + rechts)/2;
	            return rmeth(links, m, z) + rmeth(m+1, rechts, z);
	        }
	  }

	 public static void main(String... args) { 
		 //Test2 test = new Test2 (3, 6,9,12,5,7,5,3,14);
		 //test.rmeth(0, array.length-1, z);
		 new Test3(3, 6,9,12,5,7,5,3,14);
	 }


}
```


----------



## Greenhorn (23. Jun 2011)

quatsch klar, das Feld sollte ich schon vorab dekalieren und initaliseren!


```
public class Test3 {

	public Test3 (int z, int... array){
		this.array = array;
		System.out.println("Ersetzungen: " +rmeth(0, array.length-1, z));
		System.out.println("Array: " + java.util.Arrays.toString(array));
	}

	private  final int[] array;
	
	 public int rmeth(int links, int rechts, int z){
	        
	        if(links == rechts){
	            if(array[links]%z == 0){
	                array[links] = 0;
	                return 1;
	            }
	            else
	                return 0;
	        }
	        else{
	            int m = (links + rechts)/2;
	            return rmeth(links, m, z) + rmeth(m+1, rechts, z);
	        }
	  }

	 public static void main(String... args) { 
		 new Test3(3, 6,9,12,5,7,5,3,14);
	 }


}public class Test3 {

	public Test3 (int z, int... array){
		this.array = array;
		System.out.println("Ersetzungen: " +rmeth(0, array.length-1, z));
		System.out.println("Array: " + java.util.Arrays.toString(array));
	}

	private  final int[] array;
	
	 public int rmeth(int links, int rechts, int z){
	        
	        if(links == rechts){
	            if(array[links]%z == 0){
	                array[links] = 0;
	                return 1;
	            }
	            else
	                return 0;
	        }
	        else{
	            int m = (links + rechts)/2;
	            return rmeth(links, m, z) + rmeth(m+1, rechts, z);
	        }
	  }

	 public static void main(String... args) { 
		 new Test3(3, 6,9,12,5,7,5,3,14);
	 }


}
```

Nur, wie gesagt, ist mir die 2. if-Abfrage noch nicht ganz klar. 

1. m dient als Zwischenspeicher und entpsricht dem pivot aus Quicksort "Teile"
2. In der return Anweisung wird dann die Rekursion für die obere und untere Hälfte (links/recht)
   aufgerufen
3. in return wird zudem das neue m als linke und rechte Grenze übergeben


----------



## Final_Striker (23. Jun 2011)

Könnte man auch so machen:


```
else{
                int mitte = (links + rechts)/2;
                int count = 0;
                count += rmeth(links, mitte, z);
                count += rmeth(mitte+1, rechts, z); 
                return count;
            }
```


----------



## Greenhorn (23. Jun 2011)

Gut, aber warum muss ich bei der Rekursion schon inkrementieren, dies ist doch nur nötig wenn der Fall (left==right) eintritt?

Kannst du mir mal die Zeilen erklären


```
else{
                int m = (links + rechts)/2;
                return rmeth(links, m, z) + rmeth(m+1, rechts, z);  <-<-???
            }
      }
```


----------



## Greenhorn (24. Jun 2011)

Nun ist alles klar, danke für die Unterstützung Final Striker. :toll:


----------

