Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
27.05.2005, 17:14 Uhr
virtual
Sexiest Bit alive
(Operator)

Hi.

Gegeben ist ein Array a[0], ..., a[n-1] von Ganzen Zahlen.
Zu schreiben ist eine Funktion, die das k-kleinste Element (1<=k<=n darf vorausgesetzt werden) aus diesem Array findet, zum einen

a) nach Golgregeln
b) mit einem möglichst effizienten Algorithmus

Dabei gilt:
1. Das Array ist unsortiert
2. Das Array darf durch den Funktionaaufruf nicht verändert werden.

Signatur der Funktion ist:

C++:

int kmin(const int*a, size_t n, size_t k)

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
27.05.2005, 17:21 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

ist der aufruf von qsort erlaubt?

--
...fleißig wie zwei Weißbrote

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
27.05.2005, 17:51 Uhr
virtual
Sexiest Bit alive
(Operator)

Ja, aber du darfst das Array nicht verändern. Und da du für qsort eine Callbackroutine brauchst, wird die ganze Sache eng, wenn es um Golfen geht. Ansonsten hast Du bei qsort noch immer ein worstcase O(n*n). Da Du ohnehin eine Arraykopie anlegen musst, gibt es hier noch Algorithmen, die zwar nicht in situ aber besser als qsort sind (Mergesort, Heapsort) Will sagen:

1. Mit den angegeben Beschränkungen ist qsort nicht der effizienteste Ansatz, da nicht stabil
2. Das qsort an dieser Stelle besser für golfen ist, weiß ich nicht, werde mich bemühen es zu widerlegen.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
27.05.2005, 19:00 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

Zitat:

2. Das qsort an dieser Stelle besser für golfen ist, weiß ich nicht, werde mich bemühen es zu widerlegen.

Ich hab ja noch nicht mal angefangen. Bin aber zugegebener Weise sehr an der effizienten Lösung interessiert (auch wenn ich wenn nur mitgolfen werde, was effizientes finde überlass ich anderen das hört sich so mehr nach arbeit denn nach spass an und wenn ich arbeit haben will geh ich nichts ins forum

)
--
...fleißig wie zwei Weißbrote

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
28.05.2005, 07:05 Uhr
Spacelord
Hoffnungsloser Fall

Was ist mit dem Fall das k=n ist,das Array aber eine oder mehrere Zahlen doppelt enthält?
Dann gibt es kein k-kleinstes Element!?
Sofern angenommen werden kann dass es keine doppelten Arrayelemente gibt werf ich mal dass hier ins Rennen(wobei ich keine Ahnung hab wie die Golfregeln aussehen

).
Möglichst kurz und chaotisch?

C++:

int kmin(const int*a, size_t n, size_t k)
{set<int>s(a,a+n);set<int>::iterator i=s.begin();
advance(i,k-1);return *i;}

MfG Spacelord
--
.....Ich mach jetzt nämlich mein Jodeldiplom.Dann hab ich endlich was Eigenes.

Dieser Post wurde am 28.05.2005 um 07:32 Uhr von Spacelord editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
28.05.2005, 10:45 Uhr
0xdeadbeef
Gott
(Operator)

Wie ist es damit?

C++:

int kmin(int const*a,size_t n,size_t k){vector<int>v(a,a+n);sort(v.begin(),v.end());return v[k-1];}

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
03.06.2005, 13:07 Uhr
Th

Verbesserung, statt "sort", gleich "nth_element" nehmen, d.h. bessere Effizienz:

C++:

int kmin(int const*a,size_t n,size_t k){vector<int>v(a,a+n);nth_element(v.begin(),v.begin()+(k-1),v.end());return v[k-1];}

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
08.06.2005, 21:28 Uhr
~kronos
Gast

@beefy:
Also, nach Golfregeln ist ja wenn ich mich recht erinnere kein C++ erlaubt. Glück für dich, dass wie nach den noch weitgehend undefinierten Golgregeln spielen.
Hier trotzdem noch 'ne C-Lösung:

C++:

{int j,c=0,*p=a;for(;c-k;++p)for(c=j=n;--j;c-=a[j]>*p);return *--p;}

@all:
Was ist los, keiner mehr Lust zu rätseln? :-(

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
09.06.2005, 16:49 Uhr
Guybrush Threepwood
Gefürchteter Pirat
(Operator)

Zitat von ~kronos:

@all:
Was ist los, keiner mehr Lust zu rätseln? :-(

Ich habs nicht mal verstanden

Was ist denn das k-kleinste Element?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
09.06.2005, 17:03 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

Zitat:

Was ist denn das k-kleinste Element?

Ok machen wir ein Beispiel für kleine Piraten

Du hast ein Array mit den Zahlen 1 2 3 4 5 (nur das es nicht automatisch sortiert sein muss)... Jetzt willst du die k-kleinste Zahl/Element darin finden... Die einfachste möglichkeit wäre das Array zu sortieren und dann das element an der Stelle k-1 (k-1 und nicht k weil ein array bei 0 loszählt) anzugeben.

wenn du also das 3.-kleinste Element in unserem Beispiel suchst ist da die 3... in dem Beispiel hat virtual gemeiner Weise verboten das array direkt zu manipulieren...
--
...fleißig wie zwei Weißbrote

Dieser Post wurde am 09.06.2005 um 17:03 Uhr von Windalf editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: