zufallszahlen

hellihjb

Die Zahlen sollen gleich wahrscheinlich sein

Sorry, hab ich ueberlesen
Gleichverteilung ist natuerlich nicht gegeben.
Das Konzept "Ergebnisse" zu verwerfen ist zwar algorithmisch fragwuerdig (vgl hier) entspricht aber der Aufgabenstellung.

marge

Danke euch, ich lass es einfach mal durchlaufen

pointercrash**

Korhil schrieb:

Ich halte diese Lösung auch ehr für kritisch, da im Mittel dadurch Zufallszahlen erzeugt werden, für die gilt:
z1>z2>z3

Ja und? Wenn Du einen gleichmäßig verteilten Ereignisraum mit einer Einzelwahrscheinlichkeit von 1/n hast, ist es doch schnurz, ob Du zulässige Ergebnisse wegwirfst, die Dir nicht passen oder Ergebnisse erzeugst, die wieder 1/n - Verteilung unterliegen.
Nicht klar?
Also Du ziehst die erste Zahl, dann die zweite. Meinetwegen 20 und 14, dann kannst Du ziehen, was Du willst, Du mußt nach der dritten Zahl quasi zurücklegen und neu ziehen, denn die Regel besagt ja, daß Du nicht über 33 kommen darfst. Du weißt es nur noch nicht, daß der Wurf ungültig ist.
Bei hellihjb's Lösung wird das aber schon bei der Ziehung berücksichtigt, an der 1/n- Verteilung ändert er aber nichts.

Denk' mal an Lotto, die erste Kugel fällt und weil ohne Zurücklegen gespielt wird, bleibt sie in der Schippe. Wenn Du eine zurücklegst und und zum Schluß nachschaust, ob keine Kugel doppelt gezogen wurde, ändert das nur was an der Wahrscheinlichkeit, daß Du nochmal spielen mußt, aber nichts an der Verteilung.

Also 1/n ist und bleibt 1/n.

Die intensive Nutzung des Zufallszahlengenerators hat sogar den Nachteil, daß durch den Algorithmus erzeugte Häufelungen früher erkennbar werden, die "Zufälligkeit" als Qualität schwindet.
Ein Prof. hat das mal vorgeführt, indem er x und y - Koordinaten per Zufall generiert und auf dem Screen da je einen Pixel eingeschaltet hat. Dann konnte noch eingegeben werden, der wievielte Wurf gewertet wird und wieviele Pixel erwürfelt werden sollen. Was bei "jedem" Wurf noch wie Zufall aussah, hat bei jedem dreißigsten Wurf schon wie ein Tapetenmuster ausgesehen.

Natürlich sind die Zufallsgeneratoren besser geworden seitdem, aber an der grundsätzlichen Crux ändert das nichts, daß man die Dinger möglichst wenig hernehmen soll. Davon mal abgesehen ist hellihjb's Lösung viel performanter.

D-U-D-E

Hier von Performanz zu sprechen, find ich übertrieben Hab vorhin das Programm bei mir getestet, und alle Durchläufe waren nach <1sec fertig.

SG1

pointercrash() schrieb:

Korhil schrieb:

Ich halte diese Lösung auch ehr für kritisch, da im Mittel dadurch Zufallszahlen erzeugt werden, für die gilt:
z1>z2>z3

Ja und? Wenn Du einen gleichmäßig verteilten Ereignisraum mit einer Einzelwahrscheinlichkeit von 1/n hast, ist es doch schnurz, ob Du zulässige Ergebnisse wegwirfst, die Dir nicht passen oder Ergebnisse erzeugst, die wieder 1/n - Verteilung unterliegen.
Nicht klar?
Also Du ziehst die erste Zahl, dann die zweite. Meinetwegen 20 und 14, dann kannst Du ziehen, was Du willst, Du mußt nach der dritten Zahl quasi zurücklegen und neu ziehen, denn die Regel besagt ja, daß Du nicht über 33 kommen darfst. Du weißt es nur noch nicht, daß der Wurf ungültig ist.
Bei hellihjb's Lösung wird das aber schon bei der Ziehung berücksichtigt, an der 1/n- Verteilung ändert er aber nichts.

hellijhb's Lösung würde in dem Fall nur die zweite Zahl verwerfen, marge's Lösung würde BEIDE Zahlen verwerfen. Und das wirkt sich selbstverständlich auf die Gesamtverteilung aus, wie Korhil schon ausgeführt hat.

pointercrash**

SG1 schrieb:

hellijhb's Lösung würde in dem Fall nur die zweite Zahl verwerfen, marge's Lösung würde BEIDE Zahlen verwerfen. Und das wirkt sich selbstverständlich auf die Gesamtverteilung aus, wie Korhil schon ausgeführt hat.

Himmelherrgot, gebt Verstand herab vom Himmel!
Lernt ihr denn gar nix mehr in der Schule?
Es ist doch kackegal, ob eine oder zwei oder alle Zahlen verworfen werden. Closed is closed.
Bitte nehmt mal einen Bronstein zur Hand, ich hab' versucht, das trivial zu erklären, vielleicht war das einfach nicht trivial genug. Viel besser krieg' ich das aber nicht hin:
Du hast eine gleichmäßige Verteilung der Ereignisse mit 1/n. Unterereignisse haben nur Einfluß, wenn Du Zurücklegen berücksichtigst. Ist aber bei der Aufgabenstellung nicht der Fall.
Vor dem Antworten BITTE Nachdenken.

SG1

pointercrash() schrieb:

SG1 schrieb:

hellijhb's Lösung würde in dem Fall nur die zweite Zahl verwerfen, marge's Lösung würde BEIDE Zahlen verwerfen. Und das wirkt sich selbstverständlich auf die Gesamtverteilung aus, wie Korhil schon ausgeführt hat.

Himmelherrgot, gebt Verstand herab vom Himmel!

Gut, Du hast also nichts sinnvolles zur Diskussion beizutragen.

Ich weiss nicht was ihr hier ständig mit "verwerfen" bei hellihjbs nicht-Lösung (sorry ;)) meint. Da werden doch gar keine Ergebnisse verworfen? Nur ihr Bereich begrenzt, was ja eben zum Fehler führt.

Und das Modulo-Gedöns lässt sich auch leicht vermeiden:

double random (void) {
    return rand() * (1.0 / (RAND_MAX + 1.0)); // [0... 1)
}

int x = 34 * random(); // [0... 34)

SG1

Tim schrieb:

Ich weiss nicht was ihr hier ständig mit "verwerfen" bei hellihjbs nicht-Lösung (sorry ;)) meint. Da werden doch gar keine Ergebnisse verworfen?

Das war nur der Vergleichbarkeit wegen.

z2=rand()%(34-z1);

ist ja vom Ergebnis her äquivalent zu

while (zahl1+zahl2>33) zahl2=rand()%33;

. (Von den Terminationseigenschaften, Laufzeit etc. natürlich nicht).

hellihjb

Damit mal wieder Ruhe einkehrt, hier die Werteverteilung von z1 (rot), z2 (gelb), z3 (blau) der "nicht-Loesung" nach 10^6 Ziehungen.

Tim schrieb:

Und das Modulo-Gedöns lässt sich auch leicht vermeiden:
double random (void) {
    return rand() * (1.0 / (RAND_MAX + 1.0)); // [0... 1)
}

int x = 34 * random(); // [0... 34)

aber nur, wenn man der meinung ist, das die verwendung von 'doubles' so viel besser zur fragestellung passt, als einfache integer-arithmetik.

Ich konnte bei der Fragestellung nichts erkennen was gegen Fließkommaarithmetik spricht. Aber wer sich so sehr an Fließkomma stört, kann das mit ein wenig Denkleistung auch auf Integerarithmetik umbauen...

// Annahme RAND_MAX = 2^31-1
int random_int (int max) {
    return (rand() * (long long)max) >> 31;
}

Ist halt nicht mehr so allgemeingültig (portabel) wie die Fließkommavariante, da es von sizeof(int), RAND_MAX usw abhängt.

Wichtig ist das Konzept.

Tim schrieb:

Wichtig ist das Konzept.

deshalb frage ich mich ja, was du gegen modulo hast. wenn mich nicht alles täuscht, ist rand() umso 'zufälliger', je mehr der unteren bits man behält, und nicht wegdividiert und -shiftet, so wie bei deinen zweifelhaften beispielen.

~fricky schrieb:

Tim schrieb:

Wichtig ist das Konzept.

deshalb frage ich mich ja, was du gegen modulo hast. wenn mich nicht alles täuscht, ist rand() umso 'zufälliger', je mehr der unteren bits man behält, und nicht wegdividiert und -shiftet, so wie bei deinen zweifelhaften beispielen.

a) Modulo (wenn nicht gerade mit 2^x verwendet) erzeugt eine Ungleichverteilung (siehe z.B. Marcus Artikel zum Zufall)
b) Nein, gerade die unteren Bits sind/waren typischerweise die "schlechten" Bits.

Korhil

pointercrash() schrieb:

SG1 schrieb:

hellijhb's Lösung würde in dem Fall nur die zweite Zahl verwerfen, marge's Lösung würde BEIDE Zahlen verwerfen. Und das wirkt sich selbstverständlich auf die Gesamtverteilung aus, wie Korhil schon ausgeführt hat.

Himmelherrgot, gebt Verstand herab vom Himmel!
Lernt ihr denn gar nix mehr in der Schule?
Es ist doch kackegal, ob eine oder zwei oder alle Zahlen verworfen werden. Closed is closed.
Bitte nehmt mal einen Bronstein zur Hand, ich hab' versucht, das trivial zu erklären, vielleicht war das einfach nicht trivial genug. Viel besser krieg' ich das aber nicht hin:
Du hast eine gleichmäßige Verteilung der Ereignisse mit 1/n. Unterereignisse haben nur Einfluß, wenn Du Zurücklegen berücksichtigst. Ist aber bei der Aufgabenstellung nicht der Fall.
Vor dem Antworten BITTE Nachdenken.

Entschuldige, das ich wohl so schwer von Begriff bin, aber wenn ich das mal durchspiele mit 100.000 Durchläufen erhalte ich folgende Durchschnittswerte:

Lösung marge:
z1 = 8,26
z2 = 8,23
z3 = 8,25

andere Lösung:
z1 = 16,47
z2 = 8,28
z3 = 4,13

Ich glaub, ich hab in der Schule gelernt, das das nicht mal annähernd das gleiche (oder zumindest ähnliche) ist. Mit Zufall kann man sich da wohl auch nicht rausreden, oder ?

pointercrash**

Korhil schrieb:

Ich glaub, ich hab in der Schule gelernt, das das nicht mal annähernd das gleiche (oder zumindest ähnliche) ist. Mit Zufall kann man sich da wohl auch nicht rausreden, oder ?

"Auch große Geister haben nur ihre fünf Finger breite Erfahrung, - gleich daneben hört ihr Nachdenken auf: und es beginnt ihr unendlicher leerer Raum und ihre Dummheit." - Friedrich Nietzsche

OK, ich gieße das jetzt auch in Code, als Nachdenkhilfe ... gebt mir ein paar Minuten Zeit ...

Tim schrieb:

b) Nein, gerade die unteren Bits sind/waren typischerweise die "schlechten" Bits.

ach, so rum war das. ok, das erklärt ein wenig deine zahlen-trickserei.
http://en.wikipedia.org/wiki/RANDU

pointercrash**

Korhil schrieb:

Ich glaub, ich hab in der Schule gelernt, das das nicht mal annähernd das gleiche (oder zumindest ähnliche) ist. Mit Zufall kann man sich da wohl auch nicht rausreden, oder ?

Wenn jeder deine Dummheit kennt, dann bist du endlich prominent. - Erhard H. Bellermann

OK, dann habe ich in der Bekanntheitsskala noch zugelegt, ihr habt recht und ich nicht, ich kriege die Mathe nur noch nicht auf die Reihe, d.h. mir ist es noch nicht ganz klar, den Abschnitt im Bronstein kapier' ich nicht und ich werde wohl ein paar alte Uni- Scripten mit aufs Klo nehmen müssen.

Also tatsächlich führt die Einengung des Ereignisraums zu einer Verzerrung Richtung niedriger Zahlen. Morgen dann mehr für alle, die's genau wissen wollen.

Aber erstmal Abbitte Richtung Korhil&Co

meine meinung zu dem ergebnis von hellihjbs lösung:

die erste zahl z1 ist gleichverteilt auf den gesamten zahlenraum. im durchschnitt wird z1 somit den wert ~16 haben. somit bleibt für z2 + z3 im schnitt ein wertebereich von ~16 übrig, den sie sich teilen müssen.

nun kommt z2 an die reihe, nachdem z1 ermittelt wurde. z2 wird im schnitt somit mit 0 - 16 auskommen müssen - was wiederum im mittel den wert 8 ergibt.

dann bleibt noch z3 übrig. für z3 bleibt im schnitt der wertebereich von 0 bis 8 - was wiederum im mittel 4 ergibt.

somit hat die lösung im mittel z1 > z2 > z3

das ganze tritt bei der ursprünglichen lösung des OPs nicht auf, da in dem fall z1, z2 und z3 nicht abhängig voneinander sind.

pwr schrieb:

das ganze tritt bei der ursprünglichen lösung des OPs nicht auf, da in dem fall z1, z2 und z3 nicht abhängig voneinander sind.

aber er hat 'ne schleife drin, die unvorhersehbar oft rumeiert.
wie wär's mit sowas?

int a = rand();
  int b = rand();
  int c = rand();
  int div = (a+b+c)/34;
  a = a / div;
  b = b / div;
  c = c / div;

dürfte doch die anforderung erfüllen, dass die summe nicht grösser als 33 sein darf, oder?