Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 4c aus Übungsklausur
Hi, kann mir jemand bei dem Code erklären wie sich das “with” und “without” beim “Abstieg” in die Kindesknoten erhöht? Ich erkenne das wiederholende Erhöhen um 1 nicht… Und wieso wird beim with am Ende das um n+2 erhöht?
Die Aufgabe ist aus der diesjährigen Miniklausur 4c
https://www2.cs.fau.de/teaching/WS2014/AuD/organisation/oldexams/secure/15-01-12_mini_klausur.pdf
Das würde mir voll helfen 
static int longest(Tentree tree){
int without = 0;
int tmp = 0;
for( int i = 0; i < 10; ++i )
{
if( children[i] != null )
tmp = longest( children[i] );
if( without < tmp )
without = tmp;
}
int with = 0;
int n = 0;
tmp = 0;
for( int i = 0; i < 10; ++i )
{
if( children[i] != null )
{
tmp = height( children[i] );
if( with < tmp ) {
n = with
with = tmp;
} else if( n < tmp ) {
n = tmp;
}
}
}
with += n + 2;
return Math.max(without, with); Die Variablen with bzw. without sollen am Ende die Laengen der laengsten Pfade sein, die die Wurzel enthalten bzw. nicht enthalten.
Zu without: wenn der Pfad die Wurzel nicht enthaelt, liegt er komplett in einem der Teilbaeume. Es genuegt also rekursiv zu den Kindknoten ueberzugehen.
Zu with: der laengste Pfad der die Wurzel enthaelt, geht von der Wurzel in zwei verschiedene Teilbaeume (TODO: was, wenn es weniger als zwei gibt?) und dort jeweils moeglichst weit nach unten. Da uns hier gar nicht der Pfad selbst interessiert, sondern nur seine Laenge, reicht es die Hoehen der Teilbaueme zu betrachten, und davon die beiden groessten, dann kann man die Laenge des Pfades einfach berechnen. Diese beiden groessten Hoehen werden in with und n gespeichert (unglueckliche Namenswahl, finde ich).
Das gibt es mit diesem Ansatz auch nicht wirklich.
Das ist das Berechnen der Pfadlaenge.
Im Uebrigen sollte es wohl immer tree.children statt children sein.
Danke für die Antwort!
Was ich immer noch nicht ganz verstehe, ist wie sich die Länge berechnet. Man steigt ja mit der Rekursion longest(tree.children(i)) in die Kindesknoten hinab und beim “Auflösen” der Rekursion wird doch immer das return(Math.max(with, without)) von Ebene zu Ebene zurückgegeben.
Bei der Aufgabe b) haben wir da ja z.B. return height + 1 und da erkenne ich das sozusagen die Länge von Knoten zu Knoten bei der Rekursion wächst und in dieser Aufgabe sehe ich nicht wie das without bzw. tmp zunimmt…
Haben wir bei “with” ein +2 weil wir zwei Teilbäume gleichzeitig betrachten oder? Mit tmp = height(tree.children(i)) bekommt man ja die Länge von dem Teilbaum und dass man dann die zwei längsten addiert verstehe ich auch nur nicht wie das +2 zustande kommt und wie man sicherstellt, dass die 2 Teilbäume zusammenhängen.
Vielleicht hilft ja dieses Bild:
with ist der Fall links, without der Fall rechts.
Das soll auch nicht zunehmen, beachte dass im Fall rechts der laengste Pfad im linken Teilbaum nicht weiter verlaengert werden kann.
Wir betrachten ja Teilbaeume, deren Wurzeln b und c Kinder unserer urspruenglichen Wurzel a sind. Den laengsten Pfad bekommen wir dann, indem wir die laengsten Pfade von b und c zu Blaettern nehmen (deren Laenge ist jeweils die Hoehe des Teilbaums) und diese durch die Kanten (a,b) und (a,c) zu einem grossen Pfad verbinden (das entspricht dem +2).
Ich hätte auch mal eine Frage zu der Teilaufgabe, und zwar was ist hier eigentlich der Basisfall?
if(tree.children[i] == null) ??
bzw was return ich dann in diesem Fall, 0 oder 1?
Der Basisfall ist if(tree == null) und sollte in diesem Code ganz am Anfang der Methode eingebaut werden. In diesem Fall wird 0 zurückgegeben.
1 Like
Alles klar, vielen Dank!
hab mla eine Frage dazu, deswegen kram ich mla den Thread aus, undzwar. in der 4B wird ja mit der methode height() die höhe berechnet… wäre es zulässig diese Methode zu recyclen als Antwort in der C… im sinne das man halt ab jedem kindsknoten der wurzel den längsten Pfad berechnet… die höchsten zwei speichert… und fertig aus die maus? Es gibt halt klausuraufgaben die explizit erwähnen das man vorherige MEthoden nutzen darf… daher meine Frage.
P.S.: sehe auch grad das in de rFSI loesung auch height methode wiederverwendet wurde.