Rangierbahnhof < Datenstrukturen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:21 Di 14.04.2009 | | Autor: | lisa11 |
| Aufgabe | Aufgabe siehe
[Dateianhang nicht öffentlich] |
Mein Ansatz
algorithm bahnhof (L;G;H:list):list
if isEmpty(L) then return G
else if isEmpty(L) then return G
else if isempty(G) then return H
while(n<2n) do
if top(G) = A goto next(G)
if next(G) = B then
push(next(G),top(H)) goto next(H)
while (n<2n) do
if next(H) = A
push(next(H),top(G))
else goto next(H)
kann der Algorithmus stimmen?
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:40 Mi 15.04.2009 | | Autor: | lisa11 |
gibt es jemanden der sich das ansehen könnte?
|
|
|
| |
|
Hallo Lisa,
vielleicht durchschaue ich ja nur die Struktur Deines Pseudocodes nicht, aber so scheint mir der Algorithmus nicht zu funktionieren:
> algorithm bahnhof (L;G;H:list):list
>
> if isEmpty(L) then return G
> else if isEmpty(L) then return G was will diese Zeile?
> else if isempty(G) then return H
> while(n<2n) do Schleifenbedingung?
> if top(G) = A goto next(G)
> if next(G) = B then
> push(next(G),top(H)) goto next(H)
> while (n<2n) do Schleifenbedingung?
> if next(H) = A
> push(next(H),top(G))
> else goto next(H)
Ich würde das ganz anders stricken. Allerdings fragt sich noch, ob die gleichzeitige Bewegung von n gleichen Waggons als eine Bewegung zählt (was bei Zügen sicher so wäre) oder aber als n Bewegungen (was bei Stackoperationen eher wahrscheinlich ist).
1) die auf G stehenden Wagen nacheinander sortieren - alle A nach H, alle B nach I.
2) die auf H stehenden Wagen sortieren - alle A nach G, alle B nach I.
3) die auf I stehenden Wagen nach H verschieben.
Wenn [mm] g_A [/mm] die für A bestimmten Waggons auf G sind und [mm] g_B, h_A, h_B [/mm] entsprechend die für B bzw. A bestimmten Waggons auf G bzw. H, dann gilt:
[mm] n=g_A+g_B+h_A+h_B
[/mm]
Der Algorithmus braucht genau [mm] 2n-h_A [/mm] Züge, wenn die Waggons einzeln bewegt werden, und höchstens n+2 Züge, wenn mehrere Waggons zusammen bewegt werden dürfen.
Grüße
reverend
|
|
|
|
