Aufgabe 3.5 ZP Frühj. 2006

[Barti20]

Hallo Leute ich schreibe am Mittwoch Prüfung bin auch ganz fleißig am üben und habe jetzt eine Aufgabe gefunden die mich total überfordert:(

Wäre nett wenn mir jemand versständlich erklären kann was man da machen muss. Bzw. den Lösungsweg aufzeigt.

Lg

barti20

Bearbeitet 1. März 2010 von Barti20

[MidnightRun]

Oki Doki,

das Ding wird auch QuickSort Algorithmus genannt. Wobei es ja in der Aufgabe bereits sortiert wird. Aber du kannst das im Netz nachlesen.

Du hast also deine Daten, die sortiert sind. Nun zähl mal die Elemente. Es sind genau 15. Da man immer schön bei "0" anfängt sind es 14. Das Teilst du durch 2, sprich 7.

nun zählst du von Links nach rechts bis 7. WICHTIG! Beginn mit 0. Sprich 0, 1, 2, 3 .... 7 Das ist dein erstes Element was du untersuchst. Ist es größer oder kleiner als die gesuchte Zahl ? Beim ersten ist es kleiner deswegen sagst du die aktuelle Position des Elements + 1 um in die höhere Fläche zukommen und zählst ab hier die Elemente ... usw.

[akhead]

also ganz einfach:)

du hast ja die liste von zahlen das sind 15 stück. Jetzt suchst du die 8 Zahl. Diese ist stelle eins also das wäre die 3. von den neun Zahlen. Jetzt suchst du in der oberen hälfte die mitte das wäre die 7.Stelle von den neun zahlen, jetzt wieder die hälte das wäre die 5.Stelle von den neun zahlen und dann kommt schon die 144

also immer halbieren sozusagen:)

[Barti20]

ähmm rall ich net kann man das vlt. detailierter machen ? also das man 14 elemente hat konnte ich nachvollziehen (ab 0 gezählt) aber was ich net ralle warum durch 2 und was hat es mit den zählen auf sich ?

[akhead]

weil er immer mit der Zahl in der Mitte überprüft also ob die ausgewählte Zahl größer oder kleiner als die Zahl in der Mitte der Zahlenfolge is.... und dies tut er solang bis er die gewünste Zahl gefunden hat.

[Barti20]

Hmm also ich Schlüssel das jetzt mal auf korregiert mich wenn ich was falsch mache ..

unte=0[pos0]

oben=n-1[pos1]

gefunden=false[pos2]

mitte =|(unten+oben)(2| [pos3/4/5]

feld[mitte]=element? [pos6/7]

gefunden=true [pos8]

feld[mitte]>element? [pos9]

oben=mitte-1 [pos10/11]

unten=mitte+1[12/13]

mitte=-1 [pos14]

Rückgabe von mitte [pos15]

so und wie geths nun weiter ?

hier an der stele : feld[mitte] > element?

wird jetzt eingetrage die 8 ziffer also 34 heisst :

feld[34]>144

so nein also wird mitteum eins ehöht dann sind wir bei

feld[35]>144

und das macht er solange wie feld[x] nicht 144 is richtig ?

aber warum muss ich durch 2 teilen also die 14 positionen durch 2 ?

und vorallem warum zähl ich 15 (16) statt 14 wo leigt mein fehler ?

[Barti20]

*push*

[h3llraid3r]

Ganz einfach ;-)

1. unten=0, oben=n-1 << Setzt die Anfangswerte 0 und 14 (15 Elemente-1)

2. mitte= |(unten + oben) << Setzt die 1. Mitte auf 7 (14/2=7)

3. feld[mitte] = element? << Nein (Element ist ja 144 und feld[mitte] ist 21)

4. feld[mitte] > element? << Nein (Da 21 nicht größer als 144 ist)

5. unten = mitte+1 << unten wird auf 8 gesetzt (wegen mitte+1)

6. sieht wieder wie 1. aus, nur ist hier unten=8 und oben 14

...

Und so machst du das weiter bis du irgendwann an dem Punkt

feld[mitte]= element? <<Ja

ankommst.

[Barti20]

hmm jetzt verwirrst du mich oben wurde gesagt das die erste mitte 34 (8) und nun meinst es is 21(7) aber deins kann ich logischer nach vollziehen.

was is nun richtig?

[h3llraid3r]

Sry hatte einen kleinen Flüchtigkeitsfehler drin, so ist es richtig:

1. unten=0, oben=n-1 << Setzt die Anfangswerte 0 und 14 (15 Elemente-1)

2. mitte= |(unten + oben) << Setzt die 1. Mitte auf 7 (14/2=7)

3. feld[mitte] = element? << Nein (Element ist ja 144 und feld[mitte] ist 34)

4. feld[mitte] > element? << Nein (Da 34 nicht größer als 144 ist)

5. unten = mitte+1 << unten wird auf 8 gesetzt (wegen mitte+1)

6. sieht wieder wie 1. aus, nur ist hier unten=8 und oben 14

Das 7. Feld ist natürlich 34 und nicht 21 (Man fängt ja bei 0 an zu zählen)

[derpumper87]

die gleiche aufgabe verstehe ich auch nicht.

BITTE brauche eure Hilfe,

morgen habe ich Prüfung.