Datenstrukturen und Algorithmen, Aufgabe 4

Neo

Erfahrener Schreiberling

Posts: 322

Date of registration: Jul 24th 2005

Location: Hannover

Occupation: Informatik

1

Tuesday, October 25th 2005, 7:10pm

Hallo,
hat einer vielleicht eine Idee, wie man Aufgabe 4 löst?

This post has been edited 2 times, last edit by "Neo" (Oct 25th 2005, 7:17pm)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

2

Tuesday, October 25th 2005, 7:25pm

Wenn du uns sagst, wie die Aufgabenstellung lautet?

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Neo

Erfahrener Schreiberling

Posts: 322

Date of registration: Jul 24th 2005

Location: Hannover

Occupation: Informatik

3

Tuesday, October 25th 2005, 7:27pm

Aufgabenstellung

(Aufgabe 4) MinMaxAlgorithmus

Geben Sie einen Algorithmus in PseudoCode
an, der für eine Sequenz von n Zahlen
sowohl deren Minimum als auch deren Maximum mit nicht mehr als (3/2)*n Vergleichen berechnet:
minMax(Sequence S): Sequence
Hinweis: Die Ergebnissequenz soll das Minimum und das Maximum (in dieser Reihenfolge) speichern.

This post has been edited 1 times, last edit by "Neo" (Oct 25th 2005, 7:28pm)

Go to the top of the page

oixio

Senior Schreiberling

Posts: 517

Date of registration: Oct 3rd 2004

4

Tuesday, October 25th 2005, 8:42pm

Nen Tipp: Versuche dich mal von der Vorstellung zu lösen, jedes Element zu testen. Versuch doch mal die Sequenz in 2erschritten zu durchlaufen.....

Wenn noch Fragen sind, frag. Ich wollte nicht zu viel verraten.

Gruß, oixio

Edit: Jaja, die Rechtschreibung

Dieser Post wurde aus 100 % chlorfrei gebleichten, handelsüblichen, freilaufenden, glücklichen Elektronen erzeugt!

This post has been edited 1 times, last edit by "oixio" (Oct 25th 2005, 8:43pm)

Go to the top of the page

Neo

Erfahrener Schreiberling

Posts: 322

Date of registration: Jul 24th 2005

Location: Hannover

Occupation: Informatik

5

Tuesday, October 25th 2005, 8:52pm

Danke, aber hab noch eine Frage;

Quoted

Original von oixio
Nen Tipp: Versuche dich mal von der Vorstellung zu lösen, jedes Element zu testen. Versuch doch mal die Sequenz in 2erschritten zu durchlaufen.....

Wenn noch Fragen sind, frag. Ich wollte nicht zu viel verraten.

Gruß, oixio

Edit: Jaja, die Rechtschreibung

2er Schritte klingt mir zu abstrakt. Wie funktioniert das mit den 2er Schritten?

This post has been edited 1 times, last edit by "Neo" (Oct 25th 2005, 9:20pm)

Go to the top of the page

6oeser6u6e

Junior Schreiberling

Posts: 217

Date of registration: Mar 10th 2004

Location: Wolfsburg; Wohnort: Hannover-Nordstadt

Occupation: um Abstand zu der dämlichen Masse zu gewinnen... naja und wegen Geld ;P

6

Thursday, October 27th 2005, 11:07am

naja bei ner Schleife könntest du z.b. i+2 benutzen statt dem üblichen i+1
hilft bestimmt nich groß oder?
wenn du jedes Element mit dem jeweils zur zeit niedrigstens was du hast und dem höchsten was du hast vergleichst kommst du auf 2n.
Du brauchst also quasi eine Art Filter mit dem du die Vergleiche reduzierst und der Ansatz ist die Schleife in 2er schritten zu durchlaufen

Unwissenheit ist ein Segen

Go to the top of the page

q_2

Junior Schreiberling

Posts: 134

Date of registration: Oct 25th 2004

7

Thursday, October 27th 2005, 11:26am

Nun verrate doch nicht zuviel! Schreibe statt dessen: Sortieren von zwei Elementen ist trivial.

1001 PHP-Klickibunti-made-by-Script-kiddies-Foren sind nicht nur Qual sondern auch Rückschritt!

Go to the top of the page

Neo

Erfahrener Schreiberling

Posts: 322

Date of registration: Jul 24th 2005

Location: Hannover

Occupation: Informatik

8

Thursday, October 27th 2005, 4:59pm

Quoted

Original von 6oeser6u6e
wenn du jedes Element mit dem jeweils zur zeit niedrigstens was du hast und dem höchsten was du hast vergleichst kommst du auf 2n.

ok, soweit habe ich auch schon gedacht

Quoted

Ansatz ist die Schleife in 2er schritten zu durchlaufen

Ich kann mir leider immer noch nichts konkret darunter vorstellen, wie man die Schleife in 2er Schritten durchlaufen kann. Wenn ich nur jedes 2. Element vergleiche mit meinem bisherigen Maximum, dann habe ich eine Dauer n/2. Aber dann ist noch nicht klar, ob eines der n/2 Elemente, die ich nicht verglichen habe größer ist.
????