ich sitz gerade an ner Uni-Aufgabe und weiß zum ersten mal nicht, was ich zutun hab :|.
Quote:
Wir betrachten das Problem SecondLargest:
Input: eine Folge a von n ganzen Zahlen
Output: das zweitgrote Element der Folge
(a) Entwickeln Sie einen Algorithmus in Python- oder Java-Code, der das Problem lost.
(b) Wieviele Elementarschritte (Vergleiche, Zuweisungen, arithmetische Operationen,
boolesche Operationen, . . . ) benotigt Ihr Algorithmus in Abhangigkeit von n?
ich hab mich zur Lösung für nen BubbleSort entschieden, bei dem er dann einfach das 2. Glied ausgibt (bzw solang nach hinten rutscht bis n != n-1)
Allerdings komme ich auf die Elementarschrittfrage nicht klar..
Vergleiche gibt es ja maximal soviele, wie viele Zahlen verglichen werden..
also zB bei
1,8,3,4
gibt es 4 durchläufe, bis sicher das größte vorne ist..innerhalb dieser durchläufe gibt es maximal 3 Vertauschungen..4x3 = 12..
etc..aber ich weiß nicht was mit dem Rest sein soll..außerdem ist dies ja die maximale Anzahl an Vertauschungen..und variable, je nach eingabe.
Wäre Klasse, wenn jemand Rat weiß.
Code:
# coding=latin-1
def bubblesort(glieder):
maxdurchlaeufe = len(glieder) #Bestimmung der maximalen Anzahl an Tauschvorgängen
n = len(glieder) - 1 #Da die 2.größte ausgegeben werden soll
while maxdurchlaeufe >= 1: #durchlaufcounter
for k in range(len(glieder) - 1): #beginn forschleife
if glieder[k] > glieder[k+1]: #falls Position k+1 kleiner als k tausche
temp = glieder[k] #zwischenspeichern von zahl k in temp
glieder[k] = glieder[k+1] #k+1 nach k
glieder[k+1] = temp #k in k+1 (Ende Tausch)
maxdurchlaeufe = maxdurchlaeufe - 1 #durchlaufcounter--
while glieder[n] == glieder[n-1]: #falls letzte beiden Zahlen gleich solang zurückgehen bis seq[n] != seq[n-1]
n -= 1
return glieder[n-1] #Ausgabe 2. größte Zahl
Es gibt immer n * (n - 1) Durchläufe. Deine While-Schleife läuft immer n-Mal und deine innere For-Schleife (n-1)-Mal.
Dein Algorithmus bricht nicht ab wenn es bei einem Durchlauf keine Vertauschungen gab, deswegen ist die Anzahl immer gleich.
außerdem ist bei der aufgabenstellung (wenn es denn die originale ist) der bubblesort wie mit kanonen auf spatzen zu schießen.
musst ja nicht das gesamte array sortieren, sondern nur das 2. größte element FINDEN!
d.h. gehst linear durch, speicherst immer die beiden größten ab:
pseudocode:
Code:
int max1 = 0; // größtes element
int max2 = 0; // 2. größtes element
for (int i = 0; i < n; i++)
{
if (array[i] > max1)
{
max2 = max1;
max1 = array[i];
}
else if (array[i] > max2)
{
max2 = array[i];
}
}
printf("2. Grösstes Element: %d\n", max2);
vorgabe ist dabei, dass alle elemente in der liste > 0 sind, ansonsten musst du die initialisierungen von max1/2 bei nem int auf -2,147,483,648 setzen, o.ä. tricks.
ist vielleicht nicht die sauberste lösung, aber die schnellste, da maximal n*2 vergleiche durchgeführt werden und maximal n kopiervorgänge.
ist ungetestet und hat vllt nen paar kleinere häkelchen, z.b. dass in dem array mindestens 2 elemente drin sein müssen, die initwerte von max1/2 kleiner als mindestens 2 der arrayelemente sein müssen, ???...
mehr fällt mir so jetzt nicht ein...
kann auch gut sein, dass man da noch was optimieren kann, war jetzt 20 second brainstorm
vorgabe ist dabei, dass alle elemente in der liste > 0 sind, ansonsten musst du die initialisierungen von max1/2 bei nem int auf -2,147,483,648 setzen, o.ä. tricks.
Es wäre auch viel zu einfach, max1 auf den wert des 1.Elementes zu setzen :<
jaja, wie schrecklich, nen kleinen copy vergessen, habs korrigiert...
Code:
int max1 = 0; // größtes element
int max2 = 0; // 2. größtes element
for (int i = 0; i < n; i++)
{
if (array[i] > max1)
{
max2 = max1;
max1 = array[i];
}
else if (array[i] > max2)
{
max2 = array[i];
}
}
printf("2. Grösstes Element: %d\n", max2);
das was nopex erwähnt hat mit 2x maximum hab ich auch schon gedacht, aber so dürfte es ein wenig schneller sein, vorteil ist natürlich, dass das mit ner rekursion auch eine n-te lösung einfach finden lassen sollte, während man bei meiner im worst case das ganze array doppelt hat...
Und wo ist die Überprüfung ob das Array überhaupt 2 Elemente hat?
die erwähne ich in meiner ersten antwort:
Quote:
ist ungetestet und hat vllt nen paar kleinere häkelchen, z.b. dass in dem array mindestens 2 elemente drin sein müssen,
genauso, wie das min initialisierungsproblem, das hätte der te ja auch selbst hinkriegen können, habs ja erwähnt...
das mit dem fehlenden copy war natürlich my fault, war aber auch nur in 1 min so hingerotzt
Es gibt immer n * (n - 1) Durchläufe. Deine While-Schleife läuft immer n-Mal und deine innere For-Schleife (n-1)-Mal.
Dein Algorithmus bricht nicht ab wenn es bei einem Durchlauf keine Vertauschungen gab, deswegen ist die Anzahl immer gleich.
Nein, das gilt für das O-Kalkül, aber da werden Elementarschritte wie Vergleiche etc. vernachlässigt und nur Schleifendurchläufe betrachtet.
