Seite 1 von 1

klausur vordipl. WS/02

Verfasst: 27. Aug 2009 17:55
von jjtud
Servus,
ich habe zur Vorbereitung auf die AI2 Klausur die Klausur vom WS/02 vom Strippenzieher bearbeitet.
Die Musterlösung zur 7. Aufgabe kann ich nicht nachvollziehen. Ist diese Lösung richtig?

http://strippenzieher.org/login/files/A ... 2-loes.pdf
http://strippenzieher.org/login/files/A ... r-ws02.pdf

Kann mir jemand die Lösung erklären?

Noch eine allgemeine Frage an die Tutoren zur Klausur:
Wenn mehrere Teilaufgaben ein zusammenhängendes Programm ergeben, sollen dann die { } Klammern pro Teilaufgabe geschlossen werden oder als zusammenhängender Code geschrieben werden.

Gruß

PS für Strippenzieher: Login: etit, Passwort: hexagon

Re: klausur vordipl. WS/02

Verfasst: 27. Aug 2009 21:02
von 0li
Sicher dass es eine gute Idee ist hier Strippenzieher zu posten? ^^

Re: klausur vordipl. WS/02

Verfasst: 28. Aug 2009 12:07
von Daniel S.
Ich gehe mal davon aus, dass die while-/if-Bedingung klar ist und dass es nur um die Vertauschnung geht.

Also, wir haben beispielsweise die Liste
A -> B -> C -> D -> E -> ... gegeben und es wird erwartet
A -> C -> B -> E -> D -> ... zu erzeugen.

Um die erste Vertauschung durchzuführen müssen drei Verweise geändert werden, um zunächst die Liste
A -> C -> B -> D -> E -> ... zu erhalten:
  • der Nachfolger von A muss auf C gesetzt werden
  • der Nachfolger von C muss auf B gesetzt werden
  • der Nachfolger von B muss auf D gesetzt werden
Dann kann das gleiche, also eine Vertauschnung der nächsten beiden Elemente, für das nächste Paar durchgeführt werden, indem von B ausgegangen wird.

Statt Buchstaben sind in der Aufgabe jedoch Items, und zwar nur das erste, mit dem Bezeichner x. Das macht aber nichts, da durch die Verkettung über das next-Attribut auch auf die anderen Elemente zugegriffen werden kann.
Das x entspricht dem ersten Element, also dem A. Dann entspricht x.next dem B, x.next.next dem C und x.next.next.next entspricht D.
Dann kann man es fast einfach so hinschreiben:

x.next = x.next.next; //Nachfolger von A auf C setzten
x.next.next.next = x.next; //Nachfolger von C auf B setzten
x.next.next = x.next.next.next; //Nachfolger von B auf D setzten


Das Problem ist, dass nun x.next zu Beginn überschrieben wird und somit die zweite Zuweisung nicht das gewünschte Ergebnis liefert. Deshalb muss man sich das als erstes überschirbene Element merken (Item temp = x.next;) und im nächsten Schritt das gemerkte Item verwenden (x.next.next.next = temp;). Das gleiche Problem hätte man nun nochmal mit der zeiten und dritten Zeile, aber hier kann man sich das Merken sparen, indem man die Zeilen vertauscht:

Item temp = x.next; //Element merken
x.next = x.next.next; //Nachfolger von A auf C setzten
x.next.next = x.next.next.next; //Nachfolger von B auf D setzten
x.next.next.next = temp; //Nachfolger von C auf B setzten


Nun muss x noch auf B gesetzt werden, das ist zufällig in temp gespeichert, also genügt es

x = temp; //mit nächstem Paar fortfahren

zu schreiben und mit der Schleife bzw. Rekursion fortzufahren.
Wenn man mit der Musterlösung vergleicht sieht man, dass man sich auch ein anderes Item merken könnten, dann muss aber auch in einer anderen Reihenfolge vertauscht werden.

Re: klausur vordipl. WS/02

Verfasst: 31. Aug 2009 11:56
von jogo
hallo,
wäre das dann so für die rekursive methode richtig?

Code: Alles auswählen

void vertausche (Item liste)
{
    if ( liste == null || liste.next == null || liste.next.next == null )
    return;
    Item x = liste;
    vertausche ( liste.next.next );
    Item temp = x.next;
    x.next = x.next.next;
    x.next.next = x.next.next.next;
    x.next.next.next = temp;
}
und viel wichtiger, liege ich hiermit richtig:

durch das
vertausche ( liste.next.next );
geht die methode die liste so lange durch, bis die if-klausel greift und erst dann wird "rückwärts" das vertauschen durchgeführt?!?
oder hab ich das mit der rekursion immer noch nicht verstanden...

Re: klausur vordipl. WS/02

Verfasst: 31. Aug 2009 14:54
von Daniel S.
Hallo.
jogo hat geschrieben:hallo,
wäre das dann so für die rekursive methode richtig?
Ich würde sagen, dass es so richtig ist. Um sicher zu gehen, können sie es auch selbst in BlueJ ausprobieren.
und viel wichtiger, liege ich hiermit richtig:

durch das
vertausche ( liste.next.next );
geht die methode die liste so lange durch, bis die if-klausel greift und erst dann wird "rückwärts" das vertauschen durchgeführt?!?
oder hab ich das mit der rekursion immer noch nicht verstanden...
Ja, richtig, bei dieser Lösung werden die Vertauschungen rückwärts durchgeführt. Was müssten Sie ändern, falls in der Aufgabenstellung explizit gefordert ist das Vertauschen vorwärts durchzuführen?

Re: klausur vordipl. WS/02

Verfasst: 31. Aug 2009 15:12
von jogo
ich vermute man müsste das

Code: Alles auswählen

vertausche ( liste.next.next )
an das ende schreiben

Code: Alles auswählen

void vertausche (Item liste)
{
    if ( liste == null || liste.next == null || liste.next.next == null )
    return;
    Item x = liste;
    Item temp = x.next;
    x.next = x.next.next;
    x.next.next = x.next.next.next;
    x.next.next.next = temp;
    vertausche ( liste.next.next );
}
?

Re: klausur vordipl. WS/02

Verfasst: 31. Aug 2009 17:13
von Daniel S.
Korrekt.