Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
pruefungen:bachelor:aud:loesung-miniklausur-14 [20.07.2019 12:02] – Dbadtf_385pruefungen:bachelor:aud:loesung-miniklausur-14 [20.07.2019 15:59] (aktuell) – Dbadtf_385
Zeile 169: Zeile 169:
     return Math.max(without, with);      return Math.max(without, with); 
 } }
 +
 +/*Anmerkung anderer Student:
 +Ich bin mir nicht wirklich sicher, ob der obige Code korrekt alle Corner Cases abgedeckt. Wuerde man z.B. die Methode auf einem TenTree ausfuehren, der nur aus Wurzel und einer einzigen Kante in children[0] besteht, dann gibt diese Methode 0 zurueck, das richtige Ergebnis waere aber (falls ich die Aufgabe richtig verstanden habe) 1, da eine Kante hierbei die laengste Distanz im Baum darstellen wuerde.
 +
 +Anbei meine Loesung: */
 +static int longest (TenTree tree) {
 +    //Basisfall
 +    if(tree == null) return 0;
 +    //Fall1: Wurzel ist *nicht* Teil des laengsten Pfads
 +    int without = 0;
 +    for(int i = 0; i<tree.children.length;i++) {
 +        if(tree.children[i]!= null) {
 +     without = Math.max(without,  longest(tree.children[i]));
 + }
 +    }
 +
 +    //Fall 2: Wurzel *ist* Teil des laengsten Pfads
 +    int with = 0;
 +    int tmpmax = 0;
 +    int cnt = 0;
 +    for(int i = 0; i<tree.children.length;i++) {
 +        if(tree.children[i]!= null) {
 +     cnt ++;
 +     for(int j = i+1; j< tree.children.length;j++) {
 +         if(tree.children[j] != null) {
 +         // 2. Pfad gefunden: Pruefe ob die Distanz zwischen den Blaettern der beiden Pfade maximal ist
 +             tmpmax = Math.max(tmpmax, height(tree.children[i]) + height(tree.children[j]));
 +         }
 +            }
 +       }
 +    }
 +    //es wurden min. 2 Pfade gefunden: Zum laengsten Pfad muessen jetzt noch die zwei Kanten addiert werden,
 +    //welche die Verbindung zur aktuellen Wurzel darstellen
 +    if(cnt>1) {
 +        with = tmpmax +2;
 +    } else {
 +    // es gab nur 0-1 Pfade von dieser Wurzel aus. Die Laenge ist demnach 0 oder 1
 +        with = cnt; 
 +    }
 +    return Math.max(with, without);
 +}
 +
 </code> </code>