Forum: Knobelecke

Hey Leute,

oha, da hast Du Dir aber viel Mühe gemacht, Patrick. Wollte eigentlich nur die Idee ansich.

Zu den Vorschlägen: Vergleichsbasiertes Sortieren braucht mindestens n*log(n) Vergleiche; qsort() implementiert Quicksort, das können im schlechtesten Fall also bis zu n*n Vergleiche sein.

Durch die Schleife iterieren und dabei prüfen, ob die aktuelle Zahl die größte bzw. zweitgrößte Zahl ist, sind im schlechtesten Fall 2*n Vergleiche. Schon besser als vorher noch zu sortieren, aber auch nicht besser als das Maximum finden, Maximum entfernen und nochmal das neue Maximum finden.

scusi's Divide and Conquer (wie sieht das Verfahren denn konkret aus?) braucht angeblich 3n/2-2 Vergleiche, eine deutliche Verbesserung gegenüber den 2*n Vergleichen von oben.


Es lässt sich aber noch weiter optimieren, mit einer maximalen Anzahl an Vergleichen von n + log(n). Hier also die Lösung:

n sei o.B.d.A. eine Zweierpotenz. Wir veranstalten unter den n Zahlen ein Turnier, welche die größte ist: die erste tritt gegen die zweite an, die dritte gegen die vierte, usw., genau wie in einem Fussballturnier. Die Gewinner der ersten Runde treten nach dem gleichen Schema gegeneinander an. Es entsteht ein balancierter Binärbaum, dessen Wurzel der Gewinner G ist, also die größte der Zahlen.

Und jetzt kommt die entscheidende Überlegung: die zweitgrößte Zahl Z muss irgendwo auf dem Pfad liegen von G zur Wurzel, denn die zweitgrößte Zahl kann nur gegen die größte Zahl verloren haben (denn alle anderen sind kleiner oder gleich). Wir müssen also nur den Pfad von der Wurzel zu G wieder zurücklaufen und von allen Zahlen auf diesem Pfad das Maximum finden.

In einem balancierten Binärbaum mit n Knoten hat der längste Pfad von der Wurzel zu einem Blatt aber gerade die Länge log(n). Wir brauchen also n Vergleiche, um das Turnier durchzuführen und damit die größte Zahl zu ermitteln. Und wir brauchen nochmal log(n) Vergleiche, um auf dem Pfad von G zur Wurzel noch die zweitgrößte Zahl zu ermitteln.

Das lässt sich in ähnlicher Weise natürlich auch durchführen, wenn n keine Zweierpotenz ist.


Ich mag das Rätsel gerne, weil es dem gewohnten Denkmuster so sehr widerspricht.

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

7 6 4 3 9 8
 +   +   +
 7   4   9
   +   +
   7   9
     +
     9

n Vergleiche um die größte Zahl zu ermitteln (einfache for-Schleife braucht n-1).
Wie komme ich darüber nun an die zweitgrößte Zahl?
Vermutlich habe ich "Balancierten Binärbaum" nicht verstanden

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Hallo Patrick,

1   3 5   0 7   9 4   6    <-- Blätter
 \ /   \ /   \ /   \ / 
  3     5     9     6
   \   /       \   /
     5           9
      \____ ____/
           |
           9               <-- Wurzel

Hier ein Binärbaum mit n = 8 Blättern und Tiefe log(n) = 3. Um die 9 als größte Zahl zu ermitteln, brauchen wir n-1 Vergleiche.

Jetzt verfolgen wir den Weg der 9 von der Wurzel zurück zu ihrem Blatt und schauen, gegen welche Zahlen die 9 im Turnier angetreten ist. Da die zweitgrößte Zahl nur gegen die größte Zahl verlieren kann, muss sie irgendwann im Turnier auch gegen die größte angetreten sein.

In unserem Fall waren die Gegner des Turniersiegers die Zahlen 5, 6 und 7. Das sind gerade log(n) viele Zahlen, und es können auch nicht mehr sein (aber durchaus weniger), da log(n) die maximale Tiefe eines balancierten Binärbaums mit n Blättern ist. Das Maximum dieser drei Zahlen muss die zweitgrößte Zahl aller ursprünglichen Teilnehmer sein.


Wir haben also knapp n Vergleiche, um die größte Zahl zu finden, und nochmal knapp log(n) Vergleiche, um die zweitgrößte Zahl zu finden, also insgesamt ungefähr n + log(n) Vergleiche.

Ohje, das klingt auf einmal so kompliziert. Hoffe, ich habe mich verständlich ausgedrückt?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Danke sehr

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

würde es nicht auch mit selection sort gehen? und dann die letzten 2 elemente nehmen? das feld wäre sowohl sortiert wie auch die 2 größten zahlen wären gefunden =b

keine ahnung ob das effizient ist, falls nicht, hätte ja sein können und jetzt weiß ich es besser =b

--
Was nicht ist, kann noch werden =b
rock by vote or play by vote
<a href="http://www.selfmades.eu" target="blank"><img src="http://selfmades.eu/Clanwerbung/LinkUs/ITEDVO.jpg" alt="Clan Selfmades" title="Clan Selfmades"></a>