Algorithmus erstellen - Stack-Inhalt |
| 15.05.2015, 23:05 | Auf diesen Beitrag antworten » |
| e-fb | 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? |
|
|
|
| 16.05.2015, 06:50 | Auf diesen Beitrag antworten » |
| eulerscheZahl | 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. |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
