zufallszahlen

marge

Hey,
ich weiß, hier steht schon ganz viel über Zufallszahlen, aber die Lösung zu meinem Problem hab ich noch nicht gefunden...

Ich möchte drei Zufallszahlen erzeugen, deren Summe nicht größer als 33 ist. Die Zahlen sollen gleich wahrscheinlich sein.
Ich hab nen Code geschrieben, weiß aber nicht, ob man das so machen kann...

zahl1=34;
zahl2=0;
zahl3=0;
while (zahl1+zahl2+zahl3>33)
{
  zahl1=rand()%33;
  zahl2=rand()%33;
  zahl3=rand()%33;
}

Vorher hab ich natürlich die Variablen zahl1, 2 und 3 als Integer deklariert und srand(time(0)) gesetzt. Ist der Code so ok oder kann es sein, dass ich eine endlos-Schleife erzeuge? Kann man das irgendwie eleganter implementieren?

hellihjb

damit z1+z2+z3<=33 darf z1=0..33 sein:

z1=rand()%34;

nachdem z1 bekannt ist, muss z2=0..33-z1 sein:

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

z3 darf nun noch zwischen 0 und 33-z1-z2 liegen:

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

(grenzen sind jeweils einschliesslich daher modulo +1)

D-U-D-E

So dürften die Zahlen aber nicht mehr gleichwahrscheinlich auftreten.

pointercrash**

Nee, D-U-D-E, ist egal, eher sogar besser. Je häufiger Du ziehst, desto mehr neigt der Pseudozufall zur Wiederholung der Muster.
Wenn Du jede Ziehung nimmst und durch Modulo auf die Grenze stutzt, passiert das später, als wenn Du Würfe verwirfst.

Korhil

hellihjb schrieb:

damit z1+z2+z3<=33 darf z1=0..33 sein:
z1=rand()%34;
nachdem z1 bekannt ist, muss z2=0..33-z1 sein:
z2=rand()%(34-z1);
z3 darf nun noch zwischen 0 und 33-z1-z2 liegen:
z3=rand()%(34-z1-z2);
(grenzen sind jeweils einschliesslich daher modulo +1)

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

z1>z2>z3

@marge Dein Code dürfte okay sein, kann halt sein, das die while-schleife ein paar mal durchlaufen wird, aber eine endlosschleife ist es nicht.

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 ...