Modulo-Faktor einer Menge
-
Hi
Wir hatten heute bei unserem verrückten (Algo-)Professor Hash- und Indizierungsfunktionen.
Irgendwann hat er am Rand mal was gebrabellt was sich ungefähr so angehört hat:1. Gegeben sei die Menge M = { x | x e N } wobei jedes x nur einmal in der Menge vorkommt.
2. Für eine Zahl k soll gelten:
(xi modulo k) != (xj modulo k) für alle i!=j3. k <= 2*|M|
Finden sie einen schnellen Algorithmus zur Bestimmung von k.
Hab mir jetzt schon ein Weilchen den Kopf darüber zerbrochen aber ich komm auf keine Lösung.
Hat vielleicht jemand eine Idee?
mfg
rean
-
ausprobieren: for k=|M| to 2*|M| //O(n) mal bool test[k]={false,false,...} //O(n) for i=1 to |M| //O(n) mal r=M[i] mod k if test[r]=true goto warwohlnix test[r]=true next i exit "juhu" k "gefunden" :warwohlnix next k exit "nee so ein k ist nicht da"
macht O(n^2) zusammen.
vielleicht ist ja das das, was der prof haben will? von mit dem test-array von O(n^3) runterkommen auf O(n^2).bin auf den trick gespannt, der das noch deutlich unterbietet. irgendwie glaub ich nicht dran.
schau mal http://www.onjava.com/pub/a/onjava/2001/01/25/hash_functions.html an. dem entnehme ich, daß es selten ist, daß k<=2*|M| ausreicht. im durchschnitt braucht er k=12*|M|.