Übungsblatt 1 BSP'S Gruppe4

[dog]

Hi
hab mir schon mal zu dem 1. Übungsblatt ein paar gedanken gemacht:

Ich fang mal von hinten an:

1.10:

Wenn ich das richtig verstanden habe gebe ich zu beginn folgende werte in den Algorithmus
z.B.:
A= 10,0,1,3
l = 0 (Anfangsposition)
r = 4

Führe ich nun den Algorithmus aus. so habe ich gleich am Anfang ein Problem :

1. Schritt:
r-l = 4-0 --> trifft zu
min = 1
max = 0

2.Schritt
Vertausche A[0] = 10 mit A[1]
--> 0,10,1,3

Und hier passiert meiner Ansicht nach der Fehler:

Schritt 3:
Vertausche A[4] mit A[0]
da aber an position 0 mitlerweile ein anderer Wert steht passt das nicht mehr
--> 3,10,1,0 da sich die indizes der Folge dur den ertsen schritt geändert haben

richtig wäre, glaube ich:


falls r-l>1 dann{ min = position minimales Element in A[l...r]

Vertausche A[l] mit A[min]

max = position maximales Element in A[l...r]

Vertausche A[r] mit A[max]

...Sollte eigentlich so pasen oder?


1.6:

Vielleicht hab ich da einen Denkfehler aber ist hier nicht nur dieser Teik zu ändern:



für i=j+1..n{falls A[i].key > A[maxpos].key dann{maxpos=i}}1.4: haben wir im eingangstest und in der Vorlseung schon gehabt

1.8, 1.9 bin ich grade am bearbeiten.

Und bei 1.1 und 1.2 hab ich irdgendwie noch keine allgemeinen Regeln ableiten können wie das zu lösen ist, hat da jemand eine Ahnung

mfg dog

[IRBaboon]

!!! ACHTUNG ACHTUNG ACHTUNG !!!


Das erste Uebungsblatt ist erst seit rund 14:30 online, ausserdem hat sich die Nummerierung geaendert (um konsistent mit TUWEL zu sein), entsprechend gehe ich davon aus, dass du irgendwo ein altes Uebungsblatt ausgegraben hast!

Die aktuellen Uebungsblaetter sind ab sofort ueber die LVA-Webseite bzw. ueber TUWEL abrufbar (und zwar bereits alle 4).

http://www.ads.tuwien.ac.at/w/WS07/186172_Algorithmen_und_Datenstrukturen_1_VL_4.0#.C 3.9Cbungsstunden

I.R.Baboon

[dog]

Das ist verdammt ärgerlich, hab das am 10.10 heruntergeladen (TUWEL gleiche Position wo jetzt die neuen verfügbar sind) und zu Arbeiten angefangen.
Tja, pech gehab, hab halt nicht auf das Datum am Zettel geschaut.
Danke für den Tipp
... na dann alles noch mal von vorne.

[IRBaboon]

Ja, sorry, vielleicht als kurze "Erklaerung":

Ueber die Semesterferien wurde TUWEL auf eine neue Moodle-Version hochgehoben (Moodle ist das zugrundeliegende E-Learning System), und da haben sich einige Dinge bei den Einstellungen geaendert. Wir haben den Kurs einfach vom letzten Semester "importiert", was ja auch schon bei den Graphiken des Eingangstests nicht so wirklich geklappt hat.

Bei den Uebungsgruppen hatten wir eingestellt "Verfuegbar ab 19.10.2007" und waren der Meinung, dass dieser Punkt daher erst ab diesem Datum fuer euch sichtbar wird ... ein Fehler, wie sich herausgestellt hat. Daher waren bis Donnerstag ~15:00 (da haben wir eine entsprechende Email erhalten, die uns auf das Problem hingewiesen hat) die UE-Blatter des letztes Semesters verlinkt.

Also nochmals sorry, ich hoffe aber, die investierte Arbeit war nicht ganz umsonst.

I.R.Baboon

[dog]

Macht nichts hab mich gleich von neuem an die Arbeit gemacht:

Ähnlich wie beim letzten mal hab ich bei Aufgabe 1 und 2 noch nicht so wirklich ein System wie man das angehen kann.
Die BSP' s die ich aus der VO und dem alten Skriptum habe sind mir irgedwie zu sehr "erahnt" Villeicht hat da jemand eine Idde für ein "System".

Aufgabe drei sollte 5 sollte eigentlich nicht so schwer sein.
Hoffe bah mich nicht verzählt, aner ich komme auf 23 Vergleiche und 15 Bewegungen bei der BSp Folge

Schon sortiert wäre (n-1) Vergleiche und Null Bewegungen (weiss nicht ob das kopiern über sich selbst [zeile10] als Bewegung zählt.

Wenn Verkehrt sortiert dann summe(n=1:n) i+1Vergleiche und Summe(i=o:n) i+1 Bewegungen.

Aufgabe 7:

Hier wird eigentlich nur das Teilprogramm "partition" verändert hab da mal meinen code:


i= l;
j=r+1;
wiederhole
wiederhole
i=i+1;
bis A[i].key <= x; //oder i>r;
wiederhole
j=j-1;
bis A[j].key >= x; //oder j<1;
falls i<j dann
{
Vertausche A[i] und A[j];
}
Bis i>=j;
Vertausche A[i] und A[l];
Retourniere j;

Könnte das so stimmen