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:Diese Variable habe ich einfach genommen, um bei einer Überschreibung den Zustand zu ändern. Man hätte ja auch einen boolean nehmen können, der dann von false auf true gesetzt wird. Hier wird diese Variable von 0 auf 1 gesetzt.
Also, ganz ehrlich: Ich habe keine Zeit und Lust, mich mit Code zu beschäftigen, der völlig unnötigerweise derart irreführend geschrieben ist und mich deshalb unnötig viel Zeit kostet.

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 »

Wäre mein Code perfekt und nicht "derart irreführend" geschrieben, dann hätte ich ja keinen Grund in diesem Forum nach Hilfe zu suchen. Für mich ist es der 2. Versuch bei der AUD und diesen möchte ich nicht nochmal nach dem Motto "Nabla und noch irgendwie 10 Punkte" angehen. Und gerade fällt mir ein, was sie in einer Moodle-Mail zu diesem Thema geschrieben haben. Bei der Analyse der Nichtbestehensquote haben sie unter Punkt 8 angeführt, dass sich die Leute nicht intensiv mit Java beschäftigt haben. Diese These untermauerten sie damit, dass in diesem Forum und in den Sprechstunden wenig nachgefragt worden ist.
Jetzt kommt eine Nachfrage und diese wird von Ihnen abgelehnt. Die zeitlichen Gründe kann ich bis zu einem gewissen Grad nachvollziehen, nicht jedoch die mangelnde Lust sich mit dem Thema/Code auseinanderzusetzen.
Ich habe meinen ursprünglichen Code dahingehend verändert, dass ich die Variable counter durch einen boolean ersetzt habe. Ich hoffe, dass die Verständlichkeit nun verbessert worden ist.

Code: Alles auswählen

public boolean overwriteAll (TreeNode<T> wurzel, <T> ow, <T> tf){

   if (wurzel == null) return false;

   return help (wurzel,ow,tf,false);
}

public boolean help (TreeNode<T> wurzel, <T> ow, <T> tf, boolean helper){

   if (wurzel == null && helper) return true;

   if (wurzel != null){
   
      if (wurzel.key1.equals(tf)){
      
         wurzel.key1 = ow;
         helper = true;
      }
      if (wurzel.key2 != null && wurzel.key2.equals(tf)){
         
         wurzel.key2 = ow;
         helper = true;
      }
      return help (wurzel.left,ow,tf,helper) || help (wurzel.middle,ow,tf,helper) ||
            help (wurzel.right,ow,tf,helper);
   }
   return false;
}
Bei diesem Code habe ich mir folgendes überlegt. Ausgehend von der Wurzel wird für jeden Knoten die Methode help aufgerufen. Die Methode help verwendet die gleichen Parameter wie die Methode overwriteAll und noch einen zusätzlichen boolean helper. Dieser boolean soll anzeigen, ob schon Schlüsselwerte überschrieben worden sind oder nicht. Deshalb wird er zunächst mit false aufgerufen (in overwriteAll) und dann, falls key1 oder key2 mit dem gesuchten Wert übereinstimmen auf true gesetzt. Für die nachfolgenden rekursiven Aufrufe der Methode bleibt dieser Wert dann true. Die Methode soll immer dann true zurückgeben, wenn eine wurzel == null ist und helper == true ist. Also wenn man in einem Teilbaum auf keine Nachfolger mehr stößt.

Ich hoffe, diese kurze Erklärung kann das Verständnis des Codes erhöhen!


Ich hoffe darauf, auch in Zukunft weiter adäquate Antworten auf Fragen zu bekommen, damit eine gute Vorbereitung auf die anstehende Klausur gewährleistet ist.

Vielen Dank!

D'Angelo
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:
Jetzt kommt eine Nachfrage und diese wird von Ihnen abgelehnt.
Ich muss sagen, ich finde Ihre Verdrehung infam. Wenn ich es richtig sehe, habe ich schon einige Fragen von Ihnen hier beantwortet, und das hat mich viel Zeit gekostet.

Zeit, die ich übrigens sehr gerne in Sie und alle Mitforisten investiere (wie man an meinem Record im Forum leicht sieht) :!:

Aber ich denke, es ist nicht unbillig von mir zu fordern, dass Sie erst einmal Ihren Teil zum Gelingen dazu beitragen, indem Sie Ihren Code im Hinblick auf Verständlichkeit gründlich überdenken, bevor Sie ihn hier posten. :wink:

Zu Ihrem Code: Ich finde tatsächlich keinen Fehler, mir scheint, er ist korrekt. :)

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 »

Ich wollte mit meinem Post nicht sagen, dass sie sich hier nicht um die Belange der Studenten kümmern. Sie sind sehr aktiv und das finde ich persönlich sehr gut. Ich war nur gestern etwas verwundert über ihre Aussage.

Vielen Dank also für ihre Antwort und auch für ihre Mühe und Zeit, die sie in dieses Forum investieren! :lol:
I got ice in my veins! 8)

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,

ich habe noch eine Frage zur Insert-Methode auf einem Ternärbaum (Aufgabe 5). Und zwar was passiert, wenn ich im Baum nach unten steige und auf einem Knoten dann der 2. Schlüssel null ist, kann ich dann dort meinen Parameter einfach an diese Stelle setzen (also key2 mit dem Übergabeparameter überschreiben), sodass ich gar keinen neuen Knoten anlegen muss? Meine Lösung würde dann wie folgt aussehen:

Code: Alles auswählen

public boolean insert (TreeNode<T> node, <T> insert, Comparator<T> cmp){

	if (node == null) return;

	Stack stack = new Stack<TreeNode>();
	stack.push(node);

	while (!(stack.isEmpty())){
	
		TreeNode actual = stack.pop();
	
		if (cmp.compare(insert,actual.key1) == -1 || cmp.compare(insert,actual.key1 == 0)){
		
			if (wurzel.left == null){
			
				TreeNode<T> add = new TreeNode<T>();
				add.key1 = insert;
				actual.left = add;
				return;			
			}
			else if (actual.key2 == null && actual.left.left == null){
			
				actual.key2 = insert;
				return;
			}
			stack.push(actual.left);
		}
		else if (cmp.compare(insert.actual.key1) == 1 &&
				(cmp.compare(insert,actual.key2) == -1 || cmp.compare(insert,actual.key2) == 0)){
				
				if (actual.middle == null){
				
					TreeNode<T> add = new TreeNode<T>();
					add.key1 = insert;
					actual.middle = add;
					return;
				}
				else if (actual.middle.key2 == null && actual.middle.left == null){
				
					actual.middle.key2 = insert;
					return;
				}
				stack.push(actual.middle);
		}
		else {
		
			if (actual.right == null){
			
				TreeNode<T> add = new TreeNode<T>(); 
				add.key1 = insert;
				actual.right = add;
				return;
			}
			else if (actual.right.key2 == null && actual.right.left == null){
			
				actual.right.key2 = insert;
				return;
			}
			stack.push(actual.right);
		}
	}
	return;
}
Ich schaue mir immer die Range der Keys im Knoten an und entscheide dann, welchen Knoten ich hinabsteigen muss (left,middle,right). Dann existieren ja zwei Möglichkeiten: Entweder der komplette Knoten, zu dem hinabgestiegen werden muss, ist null, sodass ein neuer Knoten erstellt werden muss. Oder nur key2 dieses Knotens ist null, sodass key2 mit dem Übergabeparameter überschrieben werden kann. Dieser Fall wird in den drei inneren else-if-Fällen abgefangen. Denn wenn ich key2 überschreiben kann, dann muss es ja ein Blatt sein. Dafür muss dann auch noch der übernächste Nachfolger von actual null sein. Macht das Sinn?

Vielen Dank für die Hilfe!
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: ich habe noch eine Frage zur Insert-Methode auf einem Ternärbaum (Aufgabe 5). Und zwar was passiert, wenn ich im Baum nach unten steige und auf einem Knoten dann der 2. Schlüssel null ist, kann ich dann dort meinen Parameter einfach an diese Stelle setzen (also key2 mit dem Übergabeparameter überschreiben), sodass ich gar keinen neuen Knoten anlegen muss?
Kurzantwort: kommt drauf an :!: :shock:

Langantwort: Schauen Sie einmal auf Folie 3 von MultiWayTrees.pdf bzw. hören Sie sich dazu die Tonspur im Video zu BTrees an. Es kommt darauf an, wie ternäre Bäume spezifiziert sind:

Falls Sie wie bei binären Bäumen erlauben, dass die Anzahl Nachfolger eines Knotens geringer als eins plus die Anzahl Schlüsselwerten im Knoten ist, dann können Sie einfach den neuen Schlüsselwert einfügen und fertig.

Ansonsten müssten Sie bis zu dem Blatt hinabsteigen, in dessen Range die neu einzufügende Schlüsselwert ist. Sollte dieses Blatt voll sein, müssten Sie dann wie bei B-Bäumen ein "split" anwenden.

Probieren Sie doch einfach beides zu Übungszwecken!

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 »

Alles klar! Vielen Dank für Ihre Antwort!

Was mich aber noch interessiert, wie dann die Definition von Ternärbäumen in der Klausur ist? Denn die Implementierungen unterscheiden sich ja schon deutlich, je nachdem welche Definition letztendlich gewählt wird. :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: Was mich aber noch interessiert, wie dann die Definition von Ternärbäumen in der Klausur ist?
Ggf. wird sie eindeutig aus der Aufgabenstellung hervorgehen.

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 »

Hallo,

ich habe eine kurze Frage zur iterativen Methode Insert auf einer linearen Liste (Aufgabe 5). Meine Methode arbeitet soweit wie gewünscht, allerdings fügt sie Elemente, die kleiner sind als der head nicht korrekt an. Greift man aber allerdings mittels head.back.key auf dieses Element zu, so kann es angezeigt werden. Allerdings sollte ja die Methode selbst das Element als neuen head und nicht als head.back der Liste anfügen. Im entsprechenden if-Fall habe ich alles schon überprüft, allerdings kann ich dort keinen Fehler ausmachen.

Vielen Dank! :D

Code: Alles auswählen

public void insert (ListItem<T> head, <T> insert, Comparator<T> cmp){

	if (head == null) return;

	ListItem<T> actual = head;
	ListItem<T> last = null;

	while (actual != null){
	
		if (cmp.compare(insert,actual.key) == -1 || cmp.compare(insert,actual.key) == 0){
		
			ListItem<T> add = new ListItem<T>();
			add.key = insert;
			
			// Element muss vorne an die Liste angefügt werden
			if (last == null){
				
				add.next = actual;
				head = add;
				actual.back = add
				return;
			}
			// Element muss irgendwo mitten in der Liste angefügt werden
			else{
			
				last.next = add;
				add.next = actual;
				actual.back = add;
				last.back = add;
				return;
			}	
		}
		last  = actual;
		actual = actual.next;
	}
	//Element muss als letztes Element der Liste angefügt werden
	if (actual == null){
	
		last.next = add;
		add.back = last;
		add.next = null;
	}
	return;
}
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 Methode arbeitet soweit wie gewünscht, allerdings fügt sie Elemente, die kleiner sind als der head nicht korrekt an. Greift man aber allerdings mittels head.back.key auf dieses Element zu, so kann es angezeigt werden.
Im Gegensatz zu anderen Programmiersprachen können Sie in Java einen Parameter innerhalb der Methode nicht so ändern, dass diese Änderung an der Stelle, wo die Methode aufgerufen wird, wirksam wird. Daher muss man in Java leider einen Workaround basteln, zum Beispiel, indem Sie den neuen Listenkopf zurückgeben:

Code: Alles auswählen

  public class X <T> {
    public static ListNode<T> insert ( ListNode<T> head, T key, Comparator<T> cmp ) { ... }
  }
  
  ...
  
  ListNode<Integer> head = bastleIrgendwieAusHeiteremHimmelEineIntegerListe ();
  
  head = X.insert ( head, new Integer(357) );
Normalerweise würde man eine solche Methode natürlich nicht als static-Methode einer Klasse X, sondern als non-static-Methode einer Listenklasse definieren, die ggf. das private-Attribut head umsetzt.

Beantwortet das Ihre Frage?

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 »

Ja das hilft mir sehr weiter! Besten Dank dafür! :D
Zum Einsatz von static: Was sich dahinter verbirgt ist mir schon länger schleierhaft. Immer wenn ich Methoden aus einer main heraus runnen möchte, dann dann meckert Eclipse zunächst rum und dann kann man in Eclipse eine Autokorrektur nutzen, die dieses Schlüsselwort an allen relevanten Stellen einfügt, sodass man die Methode ausführen kann.
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: Zum Einsatz von static: Was sich dahinter verbirgt ist mir schon länger schleierhaft.
Schauen Sie doch einmal in mein Video zu Klassen und Methoden in der Videothek Algorithmik :!: :idea:

Wenn Sie dann noch konkrete Fragen haben, kann ich gerne versuchen, sie zu beantworten.

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 »

Hallo allerseits, ich habe eine kurze Frage zur Aufgabe max auf einem Vielweg-Suchbaum. Und zwar habe ich mir folgende Lösung überlegt, allerdings verwendet die Musterlösung einen deutlich längeren Weg, sodass ich mir sehr unsicher bin, ob meine Lösung in Ordnung ist.

Code: Alles auswählen

public T max (TreeNode<T> node, Comparator<T> cmp){

	// Standardprüfung, ob die node null ist
	if (node == null) return null;
	
	// an jedem Knoten möchte ich nun den Nachfolger-Knoten ganz rechts anschauen (dieser liegt an der Position numberOfKeys)
	while (node.theSuccessors[node.numberOfKeys] != null){
	
		// node wird in jeder Iteration auf diesen Knoten gesetzt
		node = node.theSuccessors[node.numberOfKeys];
	}
	// wenn es keinen Knoten mehr gibt, der ganz rechts liegt, so muss theSuccessors an der Stelle numberOfKeys null sein => Blatt! 
	// in diesem Blatt wird dann der größte Key zurückgegeben
	return node.theKeys[node.numberofKeys-1];
}
Vielen herzlichen Dank vorab!
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:Hallo allerseits, ich habe eine kurze Frage zur Aufgabe max auf einem Vielweg-Suchbaum. Und zwar habe ich mir folgende Lösung überlegt, allerdings verwendet die Musterlösung einen deutlich längeren Weg, sodass ich mir sehr unsicher bin, ob meine Lösung in Ordnung ist.
Erscheint mir nach Durchsicht voll und ganz richtig.

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 »

Hallo zusammen,

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.

Code: Alles auswählen

//Iterativ Liste
		public <T> boolean removeListIt(ListItem<T> list, T elem){
			if (list == null) return false;
			
			ListItem<T> a = list;
			if (a.key == elem) {				
				a.next.back = null;
				a = a.next;
				return true;
			}
			
			while (a.next != null){
				if (a.next.key == elem){
					if (a.next.next != null)
					a.next.next.back = a;
					a.next = a.next.next;
					return true;
				}
				a = a.next;
			}
			
			return false;
		}
Vielen Dank!
I got ice in my veins! 8)

Antworten

Zurück zu „AuD: Programmieraufgaben“