Algo zum Finden der kleinsten nichtverwendeten Zahl
-
frosty schrieb:
Das einzige Problem kann das sein das man min_int hat und somit ein Unterlauf vorkommt.
davon rede ich doch die ganze zeit, du nase. nur, daß ich von unsigned int ausgehe. ist aber egal. gleiches problem. dein algo ist nicht zuverlässig.
in dem Fall kann man aber kein kleineres Element als das kleinste im Array finden.
und deswegen ist die suche nach einem unbelegten element nicht fein auf die suche nach dem kleinsten element zurückzuführen.
Und man sollte schon in ersten Schuljahr gelernt haben, das eine Zahl kleiner wird wenn ich eins abziehe!
und dann studiert man informatik und lernt, daß das nur ausnahmen sind, wo das immer gilt. selbst mein taschenrechner hört nach ca 10^14 mal "ein-abziehen" damit auf, dran zu glauben. also 1014-1-1014==0. komisch, gell?
-
Tja, dann hättest Du aber mal besser im Studium aufpassen sollen. Dann hättest Du jetzt Ahnung von dem Du da schreibst.
-
frosty schrieb:
Tja, dann hättest Du aber mal besser im Studium aufpassen sollen. Dann hättest Du jetzt Ahnung von dem Du da schreibst.
sei x ein int.
dann ist (x-1)<x nicht immer wahr. hast du was anderes gelernt?
-
Tja, das ist mir eigentlich viel zu doof dir jetzt ne Nachhilfe in Mathe und technischer Informatik zu geben. Und auch darüber in den Ursprungspost was rein zu interpretieren was da nicht steht.
SeppSchrot schrieb:
Hallöle,
ich möchte aus einer ungeordneten Liste, deren Elemente aus jeweils einer ganzen Zahl bestehen, die kleinste Zahl finden, die nicht vorkommt.
Da steht nichts über den Wertebereich. Nur das er ganzzahllich ist. Die Sonderfälle müßen natürlich wie immer berücksichtigt werden. Das ist selbstverständlich.
-
TGGC schrieb:
Jester schrieb:
Alternativ kannst Du auch ein Array von Bits nehmen, alle auf 0 setzen und dann die Liste durchgehen und wenn Du die Zahl k findest, dann kippst Du das Bit an Stelle k von 0 auf 1. Kostet O(n). Danach einfach noch ein Bit suchen, daß noch 0 ist. Dann haste auch ne Zahl gefunden, kostet ebenfalls nochmal O(n). Kann aber dafür, wenn auch sehr große Zahlen vorkommen viel Speicher brauchen.
Nein, du brauchst nur soviel Bits, wie Einträge in der Liste sind. Größere Zahlen als n sind uninteressant.
Jo, das ist ein geiler Trick! Dadurch braucht man viel weniger Speicher. Man findet schön kleine Ids und wenn doch voll ist, dann gibt's keine Lücken. => Neue Zahl: Einfach n nehmen.
@frosty: Wo ist genau Dein Problem? Durch den beschränkten Wertebereich von Zahlentypen ist x-1 < x nicht immer wahr, egal ob signed, oder unsigned. Außerdem hat Deine Methode den Nachteil, daß sie keine Lücken ausfüllt. Insgesamt ist das also nicht gerade ein Grund vor lauter Zufriedenheit mit sich selbst auch noch beleidigend zu werden, oder?
MfG Jester
-
@Jester: ich habe damit nicht angefangen und laß mich nicht beleidigen.
-
@frosty: Du hast angefangen und im Gegensatz zu volkard wurdest du nicht beleidigt!
Edit: Außerdem wurde beiläufig von der kleinsten Zahl geredet, und da es (mathematisch) keine kleinste ganze Zahl gibt, ist es wahrscheinlich, dass es um unsigned geht, aber auch andernfalls besteht das Problem mit dem Unterlauf, wie volkard es dir schon wiederholt zu erklären versucht hat.
-
Jester schrieb:
Jo, das ist ein geiler Trick!
Typisch ich.
frosty geh heulen.
Bye, TGGC
-
-
frosty schrieb:
Tja, das ist mir eigentlich viel zu doof dir jetzt ne Nachhilfe in Mathe und technischer Informatik zu geben.
kein bedarf, fürchte ich.
((außer, du hast es drinend nötig, dann erkläre mir, warum man vom minimum über alle zahlen noch eins abziehen muß, um zum infimum zu kommen. laut üblicher definitionen ist das gar nicht nötig. mit welcher meet-verknüpfung kannste das verhalten widerspruchsfrei auf natürlichen zahlen erzeugen?))Und auch darüber in den Ursprungspost was rein zu interpretieren was da nicht steht.
ok. wir zählen mal nicht, daß kurze zeit später gegeben wird "Die Elementanzahl liegt wohl zumeist bei 5000-100000 und die Werte sind ULONGs wobei die ersten Lücken enstehen, wenn ca. die Zahl 1000 vergeben wurde und dann schätz ich gibt es so alle 500-1000 eine neue Lücke." und damit dein verfahren sehr, sehr schnell doppelzahlen ausspuckt.
wir schauen einfach mal, was du in deinem ersten posting geschrieben hast. "Da würde ich nur alle Elemente durchgehen und den kleinsten Wert im Array speichern. Und nach durchlaufen des Array einfach ne 1 abziehen. Brauch insgesamt nur O(n).".
aha! du wolltest durch ein array laufen. nicht zufällig ein array of int? also lassen wir doch erstmal gelten, daß du an ein computerprogramm dachtest und daß es extrem wahrscheinlich ist, dort bei gegebener aufgabenstellung richtig zu liegen, wenn man unsigned int (oder wenigstens int) annimmt. nehmen wir mal nicht int an, sondern einen ganzzahltyp, der keine untere grenze hat. huge numbers, also innendrin arrays, die können *sehr* groß und klein werden. fast wie natürliche zahlen. wie schafft dein verfahren dann O(n)? du hast also selber angenommen, einen üblichen maschinentypen zu benutzen und die im array zu halten. und dann machste haarspaltereien, dein verfahren könne unter umständen funktionieren, wen man von diesen und jeden annahmen ausginge (die ebenfalls nicht im ursprungsposting standen), vertrittst komische thesen, längst nachdem die aufgabe präzisiert wurde. er klappte natürlich nicht, mich mit dem gewichtigen wort "Infimum" umzuwerfen. ich kenne den begriff natürlich. meine mathe-scheine liefen auf die begriffliche wissenverarbeitung hinaus, da sind verbände grundlage zu. hab den bergiff nicht benutzt, weil er hier nicht angemessen wäre (minimum reicht). die lustige behauptung, das infimum sei nicht element des arrays, ist grausam. nachzulesen als "Das Verfahren liefert eine gültige Zahl. Nämlich das Infimum der Array-Elemente." oft liegt das infimum drin in der menge der argumente. nehmen wir für das infimum die innere verknüpfung meet als min(a,b), wobei min(a,b) immer definiert sein soll und das kleinere element ausgibt, dann ist das infimum(a,b,...,x) schlicht min(a,b,...,x). eigentlich ein wichtiger anwendungsfall des infimums, so daß du den kennen müßtest. deshalb sah ich auch sofort, daß du "infimum" nur als blendwort verwendet hast, um intellektuell zu tun. würdes du wie jester manchmal aus versehen hochmathematisch werden, würden das ganz anders klingen.
also sei lieb, und sag, daß es dir leid tut, so auf's falsche pferd gesetzt zu haben.
