Schrift
Wiki:Tipp zum Debugging: use Data::Dumper; local $Data::Dumper::Useqq = 1; print Dumper \@var;
[thread]1720[/thread]

Kleine Aufgabe

Leser: 3


<< |< 1 2 >| >> 14 Einträge, 2 Seiten
esskar
 2005-06-16 18:42
#17143 #17143
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
Gegeben seien 2 aufsteigende Arrays X[a..b] und Y[c..d], wobei alle Arrayelemente paarweise verschieden sind. Weiter ist eine Zahl k <= (b - a) + (d - c) gegeben.

Entwickel einen Algorithmus, der die k-größte Zahl in X und Y in Zeit O(log((b - a) + (d - c))) findet.

Viel Spass! :)
kabel
 2005-06-16 19:56
#17144 #17144
User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]
da musste aber noch nen preis ausschreiben ;)
-- stefan
Taulmarill
 2005-06-16 20:03
#17145 #17145
User since
2004-02-19
1750 Artikel
BenutzerIn

user image
wenn du das jetzt noch so formulierst, dass die von uns, die nicht studiert haben, das auch verstehen, dann überleg ich mir evtl. 'ne lösung
$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78
0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0
F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B
esskar
 2005-06-16 20:16
#17146 #17146
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
also
man hat zwei arrays, z.B.
X = [1,2,3,4] (oder X=[1,9,20,999])
Y = [2,3,4,5] (oder Y=[12,43,97,98])

nun hat man folgenedes:
a = 1, b = 4 (bzw. a=1, b=999)
c = 2, d = 5 (bzw. c=12, d=98 )

k lässt sich berechnen wie folgt:

k <= (b - a) + (d - c)
k <= (4 - 1) + (5 - 2) (oder (999-1) + (98 - 12))
k <= 6 (oder 1084)

k <= heißt, dass wenn das Array nicht k Einträge hat, man k soverkleinern muss, dass k = Größe des Arrays wird...

die k-größte Zahl mit k = 3 aus X = [1,2,3,4] ist dann 2\n\n

<!--EDIT|esskar|1118938618-->
kabel
 2005-06-16 22:55
#17147 #17147
User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]
ei verbibsch etzertla funktioniert mein ausgedachter algo nicht :(
-- stefan
esskar
 2005-06-16 23:13
#17148 #17148
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
[quote=kabel,16.06.2005, 20:55]ei verbibsch etzertla funktioniert mein ausgedachter algo nicht :([/quote]
ich versteh dich zwar nicht, aber ich kam auch nicht drauf!
Crian
 2005-06-20 14:07
#17149 #17149
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
Nur so ein paar Gedanken: Da die Arrays streng monoton steigend angeordnet sind, muss man zum finden des k-größten Elements nur beide Arrays von hinten durchgehen und sich dabei die Reihenfolge merken. Das macht man, bis man auf das k-größte Element gestoßen ist.

Ob das dann der Komplexitätsanforderung genügt, weiß ich nicht, aber es scheint mir recht "schnell" zu sein :-D\n\n

<!--EDIT|Crian|1119262071-->
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
esskar
 2005-06-20 14:43
#17150 #17150
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
hmm...
nicht wirklich...
wenn k == size ist, dann nicht.
es geht über einen baum...
lösung kommt demnächst!
Crian
 2005-06-20 15:19
#17151 #17151
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
Alternative: Man kann ein drittes Array aus den beiden zusammenbauen, das die Elemente beider Arrays monoton steigend enthält. Dann erfolgt die Ermittlung des k.-größten Elements in konstanter Zeit mittels $array[-$k]. Und das Array lässt sich für weitere Anfragen dieser Art wiederverwenden.\n\n

<!--EDIT|Crian|1119266472-->
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
esskar
 2005-06-20 15:27
#17152 #17152
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
[quote=Crian,20.06.2005, 13:19]$array[-$k][/quote]
wir sind zwar in einem perl forum, aber es war keine perl frage! :)
<< |< 1 2 >| >> 14 Einträge, 2 Seiten



View all threads created 2005-06-16 18:42.