Konrad-Adenauer-Gymnasium Langenfeld

Informatik Grundkurs Q1

Aufgabe 21: Rangierproblem

(aus: Informatik in der gymnasialen Oberstufe: B.2 Formen linearer Organisation von Daten, Soest 1989)

Vorgegeben ist ein Güterbahnhof mit folgendem Gleisbild. Auf Gleis A stehen nummerierte Waggons, die so rangiert werden sollen, dass sie anschließend sortiert auf Gleis C stehen. Folgende Vorgaben müssen beachtet werden:

Die Lok kann immer nur einen Wagen ziehen.
Man hat zwei Helfer: einen an der Spitze der Waggons in A (H1) und einen in C (H2).
Gleis B kann als Abstellgleis benutzt werden.

Lösung von Hand:

Für die oben abgebildete Situation kann die folgende Strategie verwendet werden:

Hole Waggon (14) aus A und bringe ihn nach C .
Hole Waggon (15) aus A und bringe ihn nach C .
Hole Waggon (15) aus C und bringe ihn nach B .
Hole Waggon (14) aus C und bringe ihn nach B .
Hole Waggon (11) aus A und bringe ihn nach C .
Hole Waggon (16) aus A und bringe ihn nach C .

Zugbeobachter aus A nach B .

Hole Waggon (16) aus C und bringe ihn nach A.
Hole Waggon (14) aus B und bringe ihn nach C .
Hole Waggon (15) aus B und bringe ihn nach C .

Zugbeobachter aus B nach A .

Hole Waggon (16) aus A und bringe ihn nach C .

Allgemeine Strategie:

Waggons werden so lange von A nach C gebracht, wie dies die gewünschte Ordnung zulässt. Wenn C noch leer ist, passt der erste Waggon aus A immer.
Wenn der nächste Waggon in A eine kleinere Nummer hat als der vorderste in C , müssen die "falschen" Waggons aus C in B abgestellt werden.
Wenn Gleis A leer ist, werden die Funktionen der Gleise A und B getauscht.

Benötigte Klassen und Methoden:

Die einzelnen Gleise stellen wir durch Listen dar, die die einzelnen Waggons als Integer-Zahlen enthalten. Es werden also 3 Listen-Objekte benötigt.
Das "Verschieben" eines Waggons (z.B. von Gleis A nach Gleis B) wird durch Löschen des ersten Listenelements von A und Einfügen dieses Elements an den Anfang der Liste B realisiert.
Verschoben wird solange, bis eine Liste leer ist, oder bis ein Objekt (Waggonnummer) am Anfang der Ausgangsliste größer ist als das Objekt der Zielliste.
Benötigte Operationen (außer Konstruktor):

Erstes Listenelement löschen

Listenelement vorne einfügen

Auswerten des ersten Listen-Elements

Test, ob Liste leer