Java-Übungsaufgaben - Lösungsvorschlag

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben: bei der Aufgabe Remove auf einer LL besteht das Problem, dass das erste Element irgendwie nicht gelöscht wird. Ich habe keine Ahnung, was man hier noch ändern soll, sodass es geht.
Ich habe mir nur die Signatur der Methode angeschaut: Es kann von vornherein mit dem ersten Listenelement nicht klappen, und zwar genau aus demselben Grund, den ich in meinem Posting von Mo 27 Mär, 2017 1:00 pm in diesem Thread für Ihre Implementation von insert angesprochen hatte.

KW

Sonne34
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 3. Mai 2015 18:10

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Sonne34 »

Hallo,

ich wollte mal fragen, ob jemand über meinen Code drüber schauen könnte. Ich weiß er ist nicht perfekt und ich denke ich habe einen Denkfehler :roll: drin, daher bin ich um jede Hilfe dankbar.
Es handelt sich um die Aufgabe 5 für teilweise besetzte Arrays.

Code: Alles auswählen

public void (PartiallyUsedArray <T> array, T wert, Comparator <T> comp) {
	// Wenn das Array leer ist
	if (array == null)
		return;
	for (int i = 0; i < array.numberOfUsedSlots, i++) {
	// Wenn im Array der Wert der eingefügt werden soll gefunden wurde
		if (comp.compare(array.theArray[i], wert) =0) {
			array.theArray[i] = wert;
		}
		// Wenn der aktuelle Wert des Arrays größer ist, dann füge hier den Wert ein	
		else if (comp.compare(array.theArray[i], wert) > 0) {
			array.theArray[i] = wert;
		}
		// Wenn der aktuelle Wert kleiner ist, als der einzufügende
		else if (comp.compare(array.theArray[i], wert) < 0) {
			//überprüfe, ob er nächste Wert größer ist und hier der Wert eingefügt werden soll
				if(comp.compare(array.theArray[i+1], wert) > 0) {
				array.theArray[i]= wert;
				}
		} 
	}
}


Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

[quote="Sonne34"]

Code: Alles auswählen

public void (PartiallyUsedArray <T> array, T wert, Comparator <T> comp) {
Name der Methode fehlt.

Code: Alles auswählen

		if (comp.compare(array.theArray[i], wert) =0) {
			array.theArray[i] = wert;
		}
Test auf Gleichheit geht mit "=="; "=" ist Zuweisung.

Diese if-Anweisung ist doch ohne jeden Effekt, oder? Denn Sie besagt doch: Falls array.theArray den Inhalt "wert" hat, soll array.theArray den Inhalt "wert" erhalten. Das heißt, "wert" soll mit "wert" überschrieben werden!?

Was genau ist die Idee Ihres Algorithmus?

Es wäre nett, wenn Sie dazuschreiben, dass es um insert geht, damit man nicht erst im Übungsblatt nachschlagen muss.

KW

Sonne34
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 3. Mai 2015 18:10

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Sonne34 »

Vielen Dank für Ihre schnelle Antwort. :)

Aufgabe ist es den zweiten Paramter in den ersten einzufüge und zwar so, sodass die Schlüsselwerte die aufsteigende Sortierung bei behalten.

Meine Idee war dann, dass ich schaue wenn es den Wert gibt, dann kann ich ihn hier direkt auch einfügen.
Wenn mein aktuell betachteter Wert kleiner ist, dann weiß ich ja nicht ob danach nicht auch noch ein Wert kommt, der kleiner als der einzusetzende Wert ist. Daher prüfe ich das in einer weitern if ab. Wenn der aktuelle Wert kleiner und der nachfolgende größer ist, dann ist hier der Platz, an dem der Wert eingefügt werden muss.
Wenn allerdings der Wert größer ist und davor keine anderen Werte im Array waren, dann füge den Wert an dieser Stelle ein.

Geht meine Idee in die richtige Richtung oder bin ich hier auf einem Holzweg? :roll:

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Hallo zusammen,

ich habe eine Frage zu einer Aufgabe auf einem Vielweg-Baum. Und zwar erhält meine Methode die Wurzel eines solchen Baumes und ein Element vom Typ Integer als Eingabe. Die Methode soll nun rekursiv ermitteln, wie oft das übergebene Element in der Datenstruktur zu finden ist und anschließend soll die Anzahl des Vorkommens zurückgegeben werden. Ich glaube das grobe Skelett meines Algorithmus ist soweit korrekt, allerdings hapert es (leider immer noch zu häufig) daran, die Verknüpfung dieser zweiseitigen Rekursion herzustellen. Ich hoffe, jemand kann mir hier helfen. Ich habe meinen Code etwas kommentiert.

Ich glaube in der Methode helpCK2 an der Stelle des Fragezeichens liegt der Fehler.

Code: Alles auswählen

	// Hauptmethode zum starten der Rekursion
	static int countKey (TreeNode wurzel, int elem){
		
		if (wurzel == null) return 0;
		
		return helpCK(wurzel,elem,0);
	}

	// die Methode bekommt einen Knoten und aktualisiert anhand der Schlüsselwerte des Knotens den Stand des Counters
	// dann ruft die Methode die 2. Hilfsmethode helpCK2 auf, um auch jeden Nachfolger des aktuellen Knotens zu bearbeiten
	static int helpCK (TreeNode node, int elem, int counter){
		
		if (node == null) return counter;
		
		counter = countNodeKeys(node, elem, 0, 0);
		
		return helpCK2(node.theSuccessors,elem,counter,0,node.numberOfKeys);
	}
	
	// die Methode bekommt ein Array mit Nachkommen und soll auf jeden dieser Nachkommen die Methode helpCK anwenden, 
	// sodass zum einen der counter weiterhin aktualisiert wird und zum anderen jeder Knoten des Baumes bearbeitet wird
	static int helpCK2 (TreeNode[] sucs, int elem, int counter, int index, int nok){
		
		if (index > nok) return counter;
		
		//?
	}
	
	// die Methode überrpüft alle Schlüsselwerte eines Knotens und erhöht bei Vorkommen des gesuchten Elements den counter um eins
	// anschliessend wird der aktuelle Stand des counters zurückgegeben
	static int countNodeKeys (TreeNode node, int elem, int counter, int index){
		
		if (index < node.numberOfKeys){
			
			if (node.theKeys[index] == elem){
				
				return countNodeKeys(node,elem,counter++,index++);
			}
			else return countNodeKeys(node,elem,counter,index++);
		}
		return counter;
	}
Generell fällt es mir beim Vielwegbaum schwer ein System zu sehen. Bei den anderen Datenstrukturen gibt es das ja auch. Und auch beim Vielweg-Baum sind ja Operationen wie die obige, max, find, overwrite alle ähnlich. Gibt es ein solches allgemeines System?

Vielen herzlichen Dank!
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

@sonne34: Ihr Algorithmus muss doch vier Dinge leisten:

1. Den Index finden, an dem "wert" einzufügen ist. Das ist der erste Index, an dem ein Inhalt >= wert steht (> statt >= ginge auch). Falls alle Inhalte im Array < wert sind, ist der Index numberOfUsedSlots der gesuchte.

2. Platz an diesem Index schaffen, indem alle Inhalte ab dem gefundenen Index jeweils um einen Index verschoben werden (siehe auch Foliensatz/Video ArrayList).

3. Wert einfügen.

4. numberOfUsedSlots um 1 erhöhen.

Das finde ich so nicht bei Ihrem Algorithmus wieder.

KW

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben: Ich glaube in der Methode helpCK2 an der Stelle des Fragezeichens liegt der Fehler.
Ich bin verwirrt: Da fehlt doch das meiste, oder? Was soll helpCK2 denn leisten?
D'Angelo Russell hat geschrieben: Generell fällt es mir beim Vielwegbaum schwer ein System zu sehen. Bei den anderen Datenstrukturen gibt es das ja auch. Und auch beim Vielweg-Baum sind ja Operationen wie die obige, max, find, overwrite alle ähnlich. Gibt es ein solches allgemeines System?
Mir ist nicht klar, was für ein allgemeines System Sie bei anderen Datenstrukturen sehen, das Sie bei Vielwegbäumen aber vermissen!?

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

helpCK2 soll zum einen, auf jedem Element des Successors Arrays die Methode helpCK aufrufen und zum anderen durch einen Selbstaufruf in diesem Array an die nächste Position rücken. Dieses Zusammenspiel dieser beiden Methoden (helpCK und helpCK2) soll dann gewährleisten, dass jeder Knoten des Baumes angeschaut worden ist und auch jeder Key im Baum korrekt gezählt wurde. Leider fällt es mir schwer, diese Ideen irgendwie in Java Code umzusetzen.

Zu dem allgemeinen System. Viele Operationen auf den Datenstrukturen bestehen ja darin, eine Datenstruktur zu durchlaufen, bis ein bestimmtes Element gefunden wird. Ist das gesuchte Element gefunden, erfolgt ja meistens eine Aktion. Also overwrite, Rückgabe eines booleans, delete usw.
Iterativ bei allen Datenstrukturen klar, rekursiv habe ich gerade bei den Vielwegbäumen noch so meine Probleme. Zum Beispiel funktioniert ja der Durchlauf durch einen Binärbaum nahezu immer gleich.

Danke! :D
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:helpCK2 soll zum einen, auf jedem Element des Successors Arrays die Methode helpCK aufrufen und zum anderen durch einen Selbstaufruf in diesem Array an die nächste Position rücken.
Ok, aber wenn Sie wollen, dass in Ihrem Code von helpCK2 nach Fehlern gesucht wird (so verstehe ich Ihre Frage), dann müssten Sie den Code aber auch hinschreiben!?
D'Angelo Russell hat geschrieben: Zu dem allgemeinen System. Viele Operationen auf den Datenstrukturen bestehen ja darin, eine Datenstruktur zu durchlaufen, bis ein bestimmtes Element gefunden wird. Ist das gesuchte Element gefunden, erfolgt ja meistens eine Aktion. Also overwrite, Rückgabe eines booleans, delete usw.
Iterativ bei allen Datenstrukturen klar, rekursiv habe ich gerade bei den Vielwegbäumen noch so meine Probleme. Zum Beispiel funktioniert ja der Durchlauf durch einen Binärbaum nahezu immer gleich.
Und bei Vielwegbäumen ist der Durchlauf nicht "nahezu immer gleich"?

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Mir fehlt völlig der Ansatz, da jetzt irgendwas in Java-Code hinzuschreiben. Vielmehr war ich in diesem Fall auf der Suche nach einer konkreten Lösung des Problems. Ich habe da nur den theoretischen Ansatz aus dem vorherigen Post.

Ich bin mir fast sicher, dass es ihn gibt, allerdings bin ich leider noch nicht richtig durchgestiegen.
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:helpCK2 soll zum einen, auf jedem Element des Successors Arrays die Methode helpCK aufrufen und zum anderen durch einen Selbstaufruf in diesem Array an die nächste Position rücken.
Erscheint mir nicht sehr sinnvoll, ich wüsste da auch nicht weiter. :shock:

Ich würde versuchen, das Problem so zu strukturieren:

Code: Alles auswählen

  static int countOccurrencesOfKey ( TreeNode wurzel, int elem ) {
      return countOccurrencesOfKey ( wurzel, elem, 0 );
   }
   
   static int countOccurrencesOfKey ( TreeNode wurzel, int elem, int numberFoundSoFar ) {
      numberFoundSoFar += countOccurrencesOfKey ( wurzel.theSuccessors[0], elem, numberFoundSoFar );
      numberFoundSoFar += countOccurrencesOfKey ( wurzel, elem, numberFoundSoFar, 1 );
   }
Die Implementation der Methode mit vier Parametern überlasse ich Ihnen. Der vierte Parameter ist der Index in den Arrays wurzel.theKeys und wurzel.theSuccessors. Dieser Parameter wird durch Rekursion fortgeschaltet.

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Leider finde ich ihren Lösungsvorschlag etwas verwirrend, weil die Methoden den gleich Namen haben. Verstehe ich ihn so korrekt?

Code: Alles auswählen

 static int countOccurrencesOfKey ( TreeNode wurzel, int elem ) {
      return help1 ( wurzel, elem, 0 );
   }
   
   static int help1 ( TreeNode wurzel, int elem, int numberFoundSoFar ) {
   	// weitere Implementierungen
      numberFoundSoFar += help1 ( wurzel.theSuccessors[0], elem, numberFoundSoFar );
      numberFoundSoFar += help2 ( wurzel, elem, numberFoundSoFar, 1 );
   }
   
   static int help2 (TreeNode wurzel, int elem, int numberFoundSoFar, int index){
   
  // Weitere Implementierungen
   
   }
Ansonsten vielen Dank für den Denkanstoß, mal sehen ob ich es hinbekomme.
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:Leider finde ich ihren Lösungsvorschlag etwas verwirrend, weil die Methoden den gleich Namen haben.
Das ist Überladung von Methoden(-namen). Daran werden Sie sich gewöhnen müssen. 8)
D'Angelo Russell hat geschrieben: Verstehe ich ihn so korrekt?
Wenn ich es richtig sehe, haben Sie nur die Methodennamen abgeändert. Dann ist natürlich der Algorithmus derselbe.

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Meine nächste Frage dreht sich um die rekursive Methode secondMax auf dem Vielwegbaum. Ich habe schon einiges am Code versucht, allerdings finde ich den Fehler nicht. Aus welchen Gründen auch immer, erhalte ich für jede Eingabe 0 als Rückgabe. Auch in der Logik meines Codes finde ich selbst keinen Fehler. Ich hoffe, hier kann mir jemand behilflich sein. Ich habe den Code wieder stichpunktartig kommentiert.

Code: Alles auswählen

	static int secondMax (TreeNode root, Comparator cmp){
		
		if (root == null) return 0;
		
		return secondMaxHelp1(root,cmp,0,0);
	}

	static int secondMaxHelp1 (TreeNode node, Comparator cmp, int max, int smax){
		
		if (node != null){
			
			smax = secondMaxHelp1(node.theSuccessors[0],cmp,max,smax);
			smax = secondMaxHelp2(node,cmp,max,smax,1);
		}
		return smax;
	}
	
	static int secondMaxHelp2 (TreeNode node, Comparator cmp, int max, int smax, int index){
		
		if (index > node.numberOfKeys) return smax;
		
		// es wird in größerer Wert als max gefunden, somit wird der max Wert neu gesetzt und smax wird auf den Wert von max gesetzt
		else if (cmp.compareInt(max, node.theKeys[index-1]) == -1){
			
			smax = max;
			max = node.theKeys[index-1];
			
			smax = secondMaxHelp2(node,cmp,max,smax,index+1);
		}
		
		// es wird in größerer Wert als smax gefunden, somit wird smax auf den neuen größeren Wert gesetzt
		else if (cmp.compareInt(smax, node.theKeys[index-1]) == -1){
			smax = node.theKeys[index-1];
			
			smax = secondMaxHelp2(node,cmp,max,smax,index+1);
		}
		
		// weder max noch smax müssen verändert werden, der Index rückt einfach um eins nach vorne
		else smax = secondMaxHelp2(node,cmp,max,smax,index+1);
		
		return secondMaxHelp1(node.theSuccessors[index],cmp,max,smax); 
	}
Herzlichen Dank!
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:Meine nächste Frage dreht sich um die rekursive Methode secondMax auf dem Vielwegbaum.
Bekommen Sie es auf den einfacheren Datenstrukturen hin?

KW

Antworten

Zurück zu „AuD: Programmieraufgaben“