Datenstrukturen und Algorithmen

[torwart1990]

hallo,
ich habe hier einige Wiederholungen vergangener Semester vormir liegen, die ich eigentlich lösen kann. eigentlich aber auch nur. hat irgendjemand einen Tipp oder kann mir vielleicht ganz sagen wie man zur Lösung kommt:


Der folgende Algorithmus arbeitet auf einer Sequence S.

1. Aufgabe:
algo1 rithm doit1(Sequence S) : Sequence :
2 Sequence S2 new Sequence();
3 while not S.isEmpty() do
4 Obj e S.remove(S.last());
5 S2 .insertLast(e);
6 return S2 .


a) Der Algorithmus wird mit dem Parameter
< 'c', 't', 'f', 'a' > aufgerufen.
Geben Sie S, e und S2 nach jeder Veränderung
sowie den Rückgabewert an.
b) Was leistet der Algorithmus generell?

2. Aufgabe
Implementieren Sie in Pseudocode den ADT Queue für Queues mit maximaler Länge N.
Nutzen Sie dafür ein Array ringförmig (modulo N), so dass das letzte Element des Arrays der
Vorgänger des ersten Elements ist.
Der Konstruktor hat die Signatur new RingQueue(int N), wobei N die Größe des Arrays ist.
Alle Methoden sollen eine Laufzeit O(1) haben. Welche Informationen müssen {zusätzlich
zum Array{ gehalten werden? Begründen Sie Ihre Antworten nachvollziehbar!



Zum Rangieren von Eisenbahnwagen steht ein
Rangiergleis mit Prellbock zur Verfügung. Die
Wagen können nur durch die Einfahrt zum
Rangiergleis gelangen; sie werden (in der Reihenfolge
des Einfahrens) von 1 bis n nummeriert.
Die Nummern der Wagen (in der Reihenfolge
des Ausfahrens) bilden eine Permutation
(p1; : : : ; pn) der Zahlen (1; : : : ; n).


a) Kann man auf diese Art die Permutationen (3; 2; 5; 4; 1; 6) oder (3; 5; 4; 1; 2; 6) erzeugen?
Falls ja, geben Sie die erforderlichen Operationen auf dem Rangiergleis an (Reihenfolge!).

Lösung ist meiner meinung da, das man die erste Permutation erzeugen kann durch rein und raus fahren der Waagons. die zweite Permutation lässt sich nicht erzeugen da mitten in der Permutation 1 aufgerufen werden soll.


b) Entwickeln Sie einen Algorithmus in Pseudocode, der zu einer als Queue übergebenen
Permutation (p1; : : : ; pn) von (1; : : : ; n) entscheidet, ob diese mit Hilfe des Rangiergleises
erzeugbar ist. Falls ja, sollen die erforderlichen Operationen (in der richtigen Reihenfolge!)
auch ausgegeben werden. Bitte erläutern Sie Ihre Lösung aussagekräftig.

c) Wie heißt die kürzeste Permutation, die man durch Rangieren nicht erzeugen kann? Ist sie eindeutig?
Meiner Meinung nach ist die Permutation { 3,1,2}. Eindeutig sollte sie auch sein


Hoffe mir kann jemand helfen

[thekilla1]

Welche Informationen müssen {zusätzlich
zum Array{ gehalten werden? Begründen Sie Ihre Antworten nachvollziehbar!

Neben dem Array müssen Item_first und Item_last gespeichert werden, damit du in O(1) auf die (nächste) Einfügestelle zugreifen kannst...



Zu Aufgabe 1 b)
Wird die übergebene Sequenz Element für Element umgekehrt in S2 geschrieben, oder irre ich mich da?

[torwart1990]

das hab ich mir auch schon gedacht. danke schön