Algorithmus entwerfen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:06 Fr 15.05.2015 | | Autor: | Geraldd |
| Aufgabe | Algorithmus entwerfen, der aus einem gegebenen Stack S die erste Hälfte der Character mit der zweiten Hälfte vergleicht. Dabei wird die erste Hälfte des Stack-Inhalts durch das Zeichen "#" von der zweiten Hälfte getrennt.
Es wird somit überprüft, ob der Inhalt von S folgende Form besitzt:
[mm] v_1 [/mm] ... [mm] v_n [/mm] # [mm] v_n [/mm] ... [mm] v_1, [/mm] n [mm] \in\ IN_0 [/mm] und [mm] v_1 [/mm] != # 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
[mm] while(S_1[Top.S1] [/mm] != #)
do [mm] Push(S_2 [/mm] , [mm] S_1[Top.S1]);
[/mm]
[mm] Pop(S_1);
[/mm]
[mm] while(S_1[Top.S1 [/mm] - 1] == [mm] S_2[Top.S2])
[/mm]
do [mm] Pop(S_1);
[/mm]
[mm] Pop(S_2);
[/mm]
if(Top.S2 == NIL)
RETURN 1;
else RETURN 0;
end;
Muss T(A) = O(n) sein?
Vielen Dank!
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.coding-board.de/threads/algorithmus-soll-inhalt-aus-stack-lesen-und-mit-rest-vergleichen-hilfe.35185/
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:21 Di 19.05.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
