Lösungsstrategien für Foo #3

ek65baze
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 24. Apr 2015 18:46

Lösungsstrategien für Foo #3

Beitrag von ek65baze »

Pivot Partitioning

Zuerst zählt ihr die Anzahl aller Elemente die kleiner sind als der Pivot, dann sucht ihr nach Elementen die dem Pivot gleich sind.
Dann könnt ihr die Liste in 3 Subarrays aufteilen.

Beispiel:

Felder * Anzahl kleiner wie Pivot | Felder * Anzahl gleich Pivot | Felder * Anzahl größer Pivot

Sollte es keine Elemente geben die gleich dem Pivot sind so gibt es keinen mittleren Bereich und der Pointer von i2 kann auf
den Anfang der Felder * Anzahl größer Pivot gesetzt werden. (Dieser verändert sich nicht mehr)

Ansonsten werden die Pointer von i1,2,3 auf jeweils den Anfang jedes Subarrays gesetzt.
Also:

i1 = Feld 1 von Felder * Anzahl kleiner wie Pivot
i2 = Feld 1 von Felder * Anzahl gleich Pivot
i3 = Feld 1 von Felder * Anzahl größer Pivot

Nun wird in jedem Iterationsschritt für jeden Pointer geprüft ob der jeweilige Wert im richtigen Teilarray sitzt, sollte das stimmen bewegt sich der Pointer bis zum nächsten Element
das nicht in das Teilarray passt. Anschließend werden die Elemente 2er Pointer getauscht wenn diese in das gegenseitige Teilarray passen.

Binary Search Tree: Traverse

Die Schwierigkeit bei dieser Aufgabe ist sich zu merken in welchem Iterationsschritt man sich befindet, ich finde hier Stift und Papier sehr hilfreich.

Ihr beginnt mit dem 0. Iterationsschritt indem ihr das oberste Element in den Stack eintragt.
Die erste Zahl ist der Knoten, die zweite wie viele Zweige schon angesehen wurden.
Also:

(Zahl des Knotens, Zahl der angesehen Zweige)

Regeln:
1. Links vor Rechts.
2. Bei jedem IS den neuen Knoten mit einer 0 in den Stack eintragen (1 IS)
3. Bei (Knoten,1) wird dieser zu L hinzugefügt. (1 IS)
4. Bei (Knoten,2) wird dieser im nächsten IS entfernt. (1 IS)
5. Es wird immer nur der unterste Knoten im Stack verändert.
3. Gibt es keinen linken Zweig, wird der letzte Knoten zu (Knoten,1) geändert.
4. Nun nach Rechts gehen und wiederholen, gibt es keinen rechten Zweig wird der letzte
Knoten auf (Knoten,2) geändert.
5. Wenn ein Knoten gelöscht wird geht ihr einen Knoten nach oben und inkrementiert diesen um 1.

Wenn ihr diese Regeln befolgt solltet ihr das richtige Ergebnis herausbekommen.
*IS = Iterationsschritt

Wenn ihr Fehler bemerkt bitte unten drunter schreiben!

ttt3
Neuling
Neuling
Beiträge: 9
Registriert: 11. Mai 2015 22:14

Re: Lösungsstrategien für Foo #3

Beitrag von ttt3 »

Vielen Dank!

Nur eine kleine Anmerkung: Bei Pivot Partitioning werden ganz am Anfang (Iteration 0) die Zeiger nicht pauschal auf Feld 1 der einzelnen Subarrays gesetzt, sondern auf den ersten nicht passenden Wert. Also beispielsweise im Subarray x < Pivot auf das erste Feld mit dem Wert x >= Pivot. :)

prox
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 14. Apr 2015 19:38

Re: Lösungsstrategien für Foo #3

Beitrag von prox »

Hey Top !! Danke für deine Mühe :D

h_ar
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 16. Apr 2015 19:56

Re: Lösungsstrategien für Foo #3

Beitrag von h_ar »

Danke! :D

Antworten

Zurück zu „Archiv“