 Algorithmus erstellen - Stack-Inhalt |
e-fb
Grünschnabel
Dabei seit: 15.05.2015
Beiträge: 1
 |
|
| Algorithmus erstellen - Stack-Inhalt |
     |
Hallo
und zwar habe ich nun als Aufgabe erteilt bekommen, einen Algorithmus zu entwerfen, der aus einem gegebenen Stack S die erste Hälfte der Character mit der zweiten Hälfte zu vergleichen. Dabei wird die erste Hälfte des Stacks durch das Zeichen "#" von der zweiten Hälfte getrennt.
Es wird somit überprüft, ob der Inhalt von S folgende Form besitzt:
v_1 ... v_n # v_n ... v_1, n (element) N und v_1 != # für 1 <= i <= n.
Liegt diese Form vor, dann soll der Wert 1 zurückgegeben werden. Andernfalls 0.
Die Laufzeit des Algorithmus sollte dabei proportional zur Größe des Stack-Inhalts ansteigen. Als Hilfsstruktur soll ein zweites Stack verwendet werden.
Wichtig ist zudem, dass lediglich die (in den Vorlesungen behandelten) Basisoperatoren verwendet werden sollen.
Basisoperatoren: Pop(S) und Push(S,x) sowie S.Top.
Ich habe mir nun folgendes zurechtgelegt und möchte zusammen mit euch die richtige Lösung ermitteln:
begin
while(S_1[Top.S1] != #)
do Push(S_2 , S_1[Top.S1]);
Pop(S_1);
while(S_1[Top.S1 - 1] == S_2[Top.S2])
do Pop(S_1);
Pop(S_2);
if(Top.S2 == NIL)
RETURN 1;
else RETURN 0;
end;
Vielen Dank!
PS: "Die Laufzeit des Algorithmus sollte dabei proportional zur Größe des Stack-Inhalts ansteigen." Wie soll das verstanden werden? Algorithmus hat die LKaufzeit O(k*n), wenn k die Anzahl an Schritten der Anweisungen ist?
|
|
15.05.2015 23:05 |
|
|
|
|
Sieht im Wesentlichen OK aus. Aber wenn nach der Aufteilung in 2 Stacks S1 mehr Einträge hat und die restlichen gleich sind, liegst du falsch (Also z.B. bei 1 2 3 # 3 2). Du musst auch S1 auf NIL prüfen.
Ich weiß nicht, wie ihr die Operatoren definiert habe, aber ich nehme an, ihr gebt bei Pop den Inhalt zurück? Dann kannst du dir das Top sparen und direkt das Ergebnis von Pop auswerten
do Push(S_2 , Pop(S_1));
In der Beschreibung ist von S.Top die Rede, du schreibst immer Top.S
Bei der Laufzeit würde man von O(n) sprechen, konstante Faktoren (k) sind da eher uninteressant.
Ist das eigentlich eine bestimmte Sprache? Sieht ein bisschen aus wie Delphi.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
16.05.2015 06:50 |
|
|
|
