klausur vordipl. WS/02

jjtud
Neuling
Neuling
Beiträge: 1
Registriert: 27. Aug 2009 17:36

klausur vordipl. WS/02

Beitrag 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

0li
Neuling
Neuling
Beiträge: 1
Registriert: 27. Aug 2009 20:59

Re: klausur vordipl. WS/02

Beitrag von 0li »

Sicher dass es eine gute Idee ist hier Strippenzieher zu posten? ^^

Daniel S.
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 25. Sep 2007 12:28
Wohnort: Mörfelden

Re: klausur vordipl. WS/02

Beitrag 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.
Mit freundlichen Grüßen
Daniel

jogo
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 14. Aug 2009 16:51

Re: klausur vordipl. WS/02

Beitrag 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...

Daniel S.
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 25. Sep 2007 12:28
Wohnort: Mörfelden

Re: klausur vordipl. WS/02

Beitrag 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?
Mit freundlichen Grüßen
Daniel

jogo
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 14. Aug 2009 16:51

Re: klausur vordipl. WS/02

Beitrag 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 );
}
?

Daniel S.
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 25. Sep 2007 12:28
Wohnort: Mörfelden

Re: klausur vordipl. WS/02

Beitrag von Daniel S. »

Korrekt.
Mit freundlichen Grüßen
Daniel

Antworten

Zurück zu „Archiv“