rekursive Teile und Herrsche Methode zum Teiler bestimmen

Greenhorn

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

Java:
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:
Code:
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
 
Zuletzt bearbeitet:

Greenhorn

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

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

Oder?
 

Final_Striker

Top Contributor
Java:
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.
 
Zuletzt bearbeitet:

ChrisKu

Bekanntes Mitglied
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:
Java:
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

Mitglied
@ 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!

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

Greenhorn

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

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

Vielen Dank!
 

Final_Striker

Top Contributor
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

Bekanntes Mitglied
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

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

Greenhorn

Mitglied
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

Mitglied
@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
Code:
 if (array[left]%z == 0){
Final-Strikers Ansatz mit
Code:
if(l == r)
?

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


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

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

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

Greenhorn

Mitglied
Ich kappiere es einfach nicht ganz!:bahnhof:

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


Java:
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);
	}


}
 

Greenhorn

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

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

Greenhorn

Mitglied
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?​
 
Zuletzt bearbeitet:

Final_Striker

Top Contributor
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

Mitglied
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

Top Contributor
Jo, kannst es auch Rückgabewert verwenden oder Rückgabewert speichern oder wie auch immer nennen. :)

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

Greenhorn

Mitglied
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

Mitglied
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

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

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

Mitglied
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?
Java:
 System.out.println("Ergänzungen: " + count)
gibts ja nicht mehr!
 

Greenhorn

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

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

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

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

Top Contributor
Könnte man auch so machen:

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

Greenhorn

Mitglied
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

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

Neue Themen


Oben