Lösungsstrategien für Foo #2 [Update]

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

Lösungsstrategien für Foo #2 [Update]

Beitrag von ek65baze »

Ich möchte hier einmal meine Lösungsstrategien aufzeigen, vielleicht hilft es ja jemand.

Bucketsort:

Vorher:
In den Index werden alle String ID's die nicht in S' stehen eingetragen. Der Index entspricht der Stringlänge - 1.

In S' werden alle String ID's eingetragen die einen Buchstaben rechts neben dem Rot markierten Buchstaben besitzen.
Die Reihenfolge ergibt sich alphabetisch aus dem Buchstaben rechts des rot Markierten. Bei gleichen Buchstaben wird der kürzere zuerst eingetragen.

Beispiel:
0 - abcd[e]fd 7 //Als 2. diesen, da er nach dem Alphabet mit String 4 als 1. kommt.
1 - bcde[f]g 6 //Als 3. diesen, da g nach f kommt.
2 - xyz 3 //Besitzt keine rote Markierung.
3 - cdef[g] 5 //Besitzt keinen Buchstaben neben der roten Markierung.
4 - xyzc[d]f 6 //Kürzer wie 0, deswegen diesen hier zuerst.

Index:
...
2 - 2
3 -
4 - 3
...

S' = 4,0,1

Nachher
S' könnt ihr direkt von oben nach unten aus dem Bucket abschreiben.
Den Index könnt ihr von Vorher übernehmen, achtet darauf das keine ID die in S' von Nachher vorkommt im Index steht.
(Danke an Nullmann)

Bucket
Es werden die String ID's in die Buchstabenfelder des Buckets einsortiert die dem rot markierten Buchstaben des Strings entsprechen.
Es werden ebenfalls kürzere Strings zuerst notiert.

Mergesort

Hier hat es mir sehr geholfen beide Listen auf Papier abzuschreiben und diese mit Pfeilen in der richtigen Reihenfolge zu verbinden (Bei doppelten Zahlen wird die untere Liste bevorzugt).
Die Anzahl Pfeile die ihr machen müsst, sind die Anzahl an Iterationen die angegeben werden. Dann könnt ihr den Pfeilen folgen und die
Liste bis zur letzten verbunden Zahl abschreiben. Am Ende zählt ihr in den beiden Reihen jeweils separat die Anzahl der mit Pfeilen verbundenen Zahlen und habt somit die Zeigerposition der beiden Listen.

(Schlechtes) ASCII Beispiel:

[-11] -> [-10]
^
|
------------

[-15] ->[ -13]

Bei Fehlern bitte melden.
Zuletzt geändert von ek65baze am 3. Jun 2015 13:23, insgesamt 1-mal geändert.

ntba
Neuling
Neuling
Beiträge: 4
Registriert: 22. Sep 2014 21:04

Re: Lösungsstrategien für Foo #2

Beitrag von ntba »

Sehr übersichtlich gemacht. Danke!

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Lösungsstrategien für Foo #2

Beitrag von Nullmann »

Bucketsort: S' Nachher entspricht genau den Buckets, von oben nach unten. Dafür sind die ja auch da ;) (Wer das nicht versteht, sollte sich den Algo nochmal genau anschauen!)

Generell empfinde ich es als gut, wenn man später auch nochmal eine Kontrollstrategie fährt.
Bei Bucketsort: S' + Indexliste = Anzahl Strings (Sowohl vorher als auch nachher)
Bei Merge: Zeiger 1 + Zeiger 2 = Iteration

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

Re: Lösungsstrategien für Foo #2

Beitrag von h_ar »

Habe ich etwas falsch gemacht oder zeigt foo es mir falsch an?

Gegeben seien nun folgende Liste l1:

-14 -13 -6 -6 1 3 3 4 4 4 8 14
Sowie die Liste l2:

-12 -8 -7 -7 -5 -4 -1 0 1 3 4

Geben Sie den Stand der Ergebnisliste sowie die Zeigerposition von l1 und l2 zum Zeitpunkt i=19 an.




Da Zeiger 1 + Zeiger 2 19 sein muss wäre 11 + 8 ja richtig, aber foo sagt mir Zeiger 1 ist bei 7?



Ergebnissliste: -14 -13 -12 -8 -7 -7 -6 -6 -5 -4 -1 0 1 1 3 3 3 4 4 4 4 8 14
Zeiger l1: 8
Zeiger l2: 11
Ihre Lösung ist nicht korrekt.

Die korrekte Lösung lautet wie folgt:

Ergebnissliste: -14 -13 -12 -8 -7 -7 -6 -6 -5 -4 -1 0 1 1 3 3 3 4 4 4 4 8 14
Zeiger l1: 7
Zeiger l2: 11
Zurück zur Aufgabenliste

ntba
Neuling
Neuling
Beiträge: 4
Registriert: 22. Sep 2014 21:04

Re: Lösungsstrategien für Foo #2

Beitrag von ntba »


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

Re: Lösungsstrategien für Foo #2

Beitrag von h_ar »

Ok, scheint nicht nur mich zu betreffen.

f8f2394347595ff31db6d61e584dc346

Das ist der Seed zu einem weiteren Bug gerade, wo Iteration 22 abgefragt wird aber das Ergbenis falsch ist.

Ich habe morgen Testat. Was wenn das im Testat passiert?

hololol2
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 27. Apr 2015 14:13

Re: Lösungsstrategien für Foo #2

Beitrag von hololol2 »

Man kann die Aufgaben im Nachhinein ansehen und wenn dein Ergebnis richtig ist kriegst du das Testat als bestanden

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Lösungsstrategien für Foo #2

Beitrag von Nullmann »

Dies müsste ein Sonderfall von Merge sein: Wenn eine Liste durch gegangen ist, wird die andere komplett dran gehängt. Ohne weiter die Pointer zu erhöhen.

Antworten

Zurück zu „Archiv“