000
12.12.2002, 12:45 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Zufallzahlen
Kurze Vorbemerkung
Da der Computer im Wesentlichen rechnen soll, und das auch noch richtig, ist da recht wenig Platz für Zufall. Wenn also im Zusammenhang mit Programmieren von "Zufall" die Rede ist, sollte man sich stets vor Augen halten, daß der Computer immer nur so tun kann, als würde er etwas Zufälliges errechnen.
Auch wenn im folgenden eigentlich nur von "Zufallszahlen" die Rede ist, so wäre der richtige Fachbegriff wohl eher "Pseudo-Zufallszahl" (="So-Tun-Als-Ob-Zufällig-Zahl").
Zufallszahlen verwenden
Um an eine Zufallszahl zu gelangen, muß man die Funktion rand aufrufen. rand gibt eine Zahl zwischen 0 und RAND_MAX zurück. Sowohl rand alsauch RAND_MAX sind im Header <stdlib.h> definiert; RAND_MAX ist eine Konstante, die je nach System unterschiedliche Werte haben kann. Auf meinem sind es zB 2147483647 (=0x7fffffff), andere System verwenden 32767 (=0x7fff).
Meist ist man nicht an Zufallszahlen im Bereich zwischen 0 und RAND_MAX interessiert, sondern zB zwischen 1 und 6 (wenn man eine Würfel simulieren möchte). Daher muß man den von rand gelieferten Wert auf den gewünschten Wertebereich mappen. Dies kann man zB so machen:
| C++: |
int min = 1; /* Minimale Zufallszahl */
int max = 6; /* Maximale Zufallszahl */
int wurf;
wurf = min + rand()%(max-min+1);
|
Mit diesem Wissen bewaffnet kann man nun das erste Programm schreiben, was hier einfach ein Würfel-Simluator ist, der das zehnmalige Werfen eines Würfels simuliert und die jeweils geworfenen Augenzahlen ausgibt. Wir werden schnell sehen, daß dieses Programm nicht der Weisheit letzter Schluß ist:
| C++: |
/* 1. Naiver Versuch */
#include <stdio.h> /* für printf */
#include <stdlib.h> /* für rand */
int
main()
{
int i;
int wurf;
for (i=1; i<=10; ++i)
{
printf("Wurf %d: ", i);
wurf = 1 + rand()%6; /* Zufallszahl zwischen 1 und 6 */
printf("%d\n", wurf);
}
}
|
In den meisten Fällen (das hängt vom Zufall ab  ) sollte das Programm zehn Zahlen zwischen 1 und 6 ausgeben, wobei es schwer fallen sollte, eine Regelmäßigkeit zu entdecken, wie die Zahlen entstehen.
Auf den ersten Blick wirkt dieses Programm also ganz okay, ist es aber leider nicht: Wenn man es erneut startet, kommen exakt die gleichen "Zufallszahlen" heraus, wie beim ersten Start. Man sollte eigentlich etwas anderes erwarten dürfen.
Daß bei jedem Aufruf immer die gleichen Zahlen herauskommen, liegt am Algorithmus des Zufallszahlengenerators, also jener Routine, die die Zufallszahlen generiert. Dieser ist ein rekursiver Algorithmus, bei dem zur Berechnung einer neuen Zufallszahl die vorherige Zahl irgendiw verwurschtelt wird.
Wenn nun das Programm startet, es also keine erste Zufallszahl gibt, geht der Zufallsgenerator von immer dem gleichen Anfangswert aus. Wenn man also diesen Anfangswert verändert, wird auch die erzeugt Reihe der Zufallszahlen eine andere sein. Genau für diesen Zweck gibt es die Funktion srand, welche den "Random seed", also diese erste Zahl setzt:
Mit
| C++: |
/* 2. Weniger naiver Versuch */
#include <stdio.h> /* für printf */
#include <stdlib.h> /* für rand */
int
main()
{
int i;
int wurf;
[b]srand(time(NULL));[/b]
for (i=1; i<=10; ++i)
{
printf("Wurf %d: ", i);
wurf = 1 + rand()%6; /* Zufallszahl zwischen 1 und 6 */
printf("%d\n", wurf);
}
}
|
Wird nun diese erste Zahl auf einen Wert gesetzt, der von der aktuellen Urzeit abhängt. Damit wird jedesmal ein anderer Startwert und ergo eine andere Sequenz von zufallszahlen generiert.
Problematisch wird dieser Ansatz jedoch dann, wenn das Programm mehrmals pro Sekunde gestart werden soll, weil dann das time jeweils den gleichen Wert zurück gibt. In diesen (seltenen Fällen) sollte man sich einer Zeitabrage höherer Auflösung (zB gettimeofday) behelfen, aber das ist ein anderes Thema.
Zu beachten ist, daß srand wirklich nur einmal aufgerufen wird, denn sowas hier führt zu unschönen Resultaten:
| C++: |
/* 3. Sehr naiver Versuch */
#include <stdio.h> /* für printf */
#include <stdlib.h> /* für rand */
int
main()
{
int i;
int wurf;
for (i=1; i<=10; ++i)
{
printf("Wurf %d: ", i);
srand(time(NULL));
wurf = 1 + rand()%6; /* Zufallszahl zwischen 1 und 6 */
printf("%d\n", wurf);
}
}
|
Eine Ready-To-Use Funktion zur Generierung von Zufallszahlen könnte zB folgende Funktion darstellen, die einem das lästige Aufrufen von srand und das Mappen der Zufallszahlen in den gewünschten Bereich abnimmt:
| C++: |
/*
* Berechne Zufallszahl im Bereich [von, bis]
*/
int zufall(int von, int bis)
{
static int srand_bereits_aufgerufen = 0;
if (!srand_bereits_aufgerufen)
{
srand(time(NULL));
srand_bereits_aufgerufen = 1;
}
return von + rand()%(bis-von+1);
}
|
Verteilung der Zufallzahlen
Ein wichtiges Qualitätsmerkmal von Zufallsgeneratoren ist ihre Gleichverteilung. Dh bei hinreichend vielen Durchläufen sollte der Zufallsgenerator in etwa gleich oft jede Zahl auswählen. Folgendes Programm kann dazu eingesetzt werden, sich die Verteilung anzuschauen, die der Zufallsgenerator erzeugt:
| C++: |
#include <stdio.h>
#include <stdlib.h>
/*
* Es werden DURCHLAEUFE Mal Zufallszahlen zwischen VON und BIS
* (einschliesslich) gezogen. Bei Bedarf sind die Macros
* anzupassen.
*/
#define VON 1
#define BIS 10
#define DURCHLAEUFE 10000
/*
* Gibt eine Statistik zu der akt. Verteilung der Zahlen aus
*/
static void
zeigeHaeufigkeiten(
int durchlauf,
int* hfgk)
{
int i;
/*
* Sollte auf den meisten System bewirken, daß der
* Cursor links oben steht.
*/
printf("\x1b[H");
/*
* Ausgabe der Haeufigkeiten
*/
puts("Wert abs. Hfgk. rel. Hfgk.");
puts("---------- ---------- ----------");
for(i=0; i<BIS-VON+1; ++i)
{
printf("%10d %10d %9.5f%%\n", VON+i, hfgk[ i ], (double)hfgk[ i ]/(double)durchlauf);
}
}
/*
* Berechne Zufallszahl im Bereich [von, bis]
*/
static int
zufall(int von, int bis)
{
static int srand_bereits_aufgerufen = 0;
if (!srand_bereits_aufgerufen)
{
srand(time(NULL));
srand_bereits_aufgerufen = 1;
}
return von + rand()%(bis-von+1);
}
int
main()
{
int hfgk[BIS-VON+1]; /* Array zu Abspeichern der Haeufigkeiten */
int i;
/*
* Lösche den bildschirm
*/
printf("\x1b[2J");
/*
* Initialisiere die Haeufigkeiten
*/
for(i=0; i<BIS-VON+1; ++i)
{
hfgk[ i ] = 0;
}
/*
* Mache einige Durchlaeufe
*/
for(i=1; i<=DURCHLAEUFE; ++i)
{
hfgk[zufall(VON, BIS)-VON]++;
zeigeHaeufigkeiten(i, hfgk);
}
}
|
Modifizieren der Zufallsverteilung
Die Frage ist, wie man die Gelichverteilung modifizieren kann. Ein Ansatz soll mit dem nächsten Programm gezeigt werden: Es simuliert einen gezinkten Würfel, bei dem die 6 mit einer 5 Mal höheren Wahrscheinlichkeit gewürfelt wird. Weite Teile des Programms stimmen mit dem vorherigen Programm überein; die Routinen zufall und zeigeHaeufigkeiten habe ich mal weggelassen, sie werden aber benötigt. Die Hinzugekommen/geänderten Stellen sind fett gedruckt:
| C++: |
#include <stdio.h>
#include <stdlib.h>
#define VON 1
[b]#define BIS 6[/b]
#define DURCHLAEUFE 10000
[b]
static int
gezinkterWuerfel()
{
/*
* Unser gezinkter Wuerfel soll in 50% der Faelle eine 6
* würfeln, alle anderem Zahlen sollen mit 10%iger Wahrscheinlichkeit
* fallen. Wir bauen dazu ein mapping array mit 10 Elementen auf,
* welches die Zufallszahlen 0-9 auf die Würfel zahlen 1-6 mappt.
* Die Zahlen 1 - 5 kommen immer nur einmal vor; 6 jedoch 5 mal.
* Damit ist die Wahrscheinlchketi für eine 6 5 Mal höher
*/
static int zinker[10] = { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6 };
return zinker[zufall(0,9)];
}
[/b]
int main()
{
...
for(i=1; i<=DURCHLAEUFE; ++i)
{
[b]hfgk[gezinkterWuerfel()-1]++;[/b]
zeigeHaeufigkeiten(i, hfgk);
}
}
|
Diese Art der Modifizierung der Verteilung hat zwar den Vorteil relativ schnell zu sein, jedoch taugt sie nicht für alle Fälle: Will man etwa ein gezinkten Würfel schreiben, bei dem die 6 mit 50%, die 5 mit 23% und die übrigen gleichverteilt sind, dann braucht man bereits eine Tabelle mit 100 Einträgen.
Um eine feinere Granularität der Gewichtungen zu zulassen, muß man etwas mehr aufwand beitreiben. Eine Idee besteht in folgender Vorgehensweise:
Man kummuliert die gewünschten Häufigkeiten in einer Tabelle; Bei unserem Würfel könnte die so aussehen:
| C++: |
static int gezinkterWuerfel()
{
static int gew_hfgk[7] = {
0, /* Diese Zahl gibt es nicht */
370, /* 1 mit 3.7% Wahrscheinlichkeit (3.7=370/100 */
1800, /* 2 mit 14.3% Wahrscheinlichkeit (14.3=(1800-370)/100 */
2200, /* 3 mit 4.0% Wahrscheinlichkeit (4.0=(2200-1800)/100 */
3012, /* 4 mit 8.12% Wahrscheinlichkeit (8.12=(3012-2200)/100 */
5000, /* 5 mit 19.88% Wahrscheinlichkeit (19.88=(5000-3012)/100 */
10000 /* 6 mit 50% Wahrscheinlichkeit (50=(10000-5000)/100 */
};
int i;
int wurf = zufall(1, 10000);
for(i=2; i<7; ++i) if (wurf<gwe_hfgk[ i ]) return i-1;
return 6;
}
|
Wird eine höhere Genauigkeit der gewünschten Wahrscheinlichekten gewünscht, ist der statt 10000 eine entsprechend höhere Zahl zu verwenden.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
Dieser Post wurde am 17.03.2007 um 18:42 Uhr von FloSoft editiert. |
