Zufallszahlen

Schere, Stein, Papier

Quelle: Wikimedia

Bestimmt kennst Du das Spiel Schere, Stein, Papier, das auch unter dem Namen Schnick, Schnack, Schnuck bekannt ist. Unser Ziel ist es hier eine Version des Spiels zu programmieren, bei der man gegen den Computer spielt. Dazu soll dieser zufällig eines der drei Symbole auswählen.

Wir könnten dazu die existierenden Module und Pakete der gängigen Programmiersprachen benutzen. Da es uns aber hier darum geht, zu verstehen, ob und wie ein Computer zufällige Zahlen berechnen kann, werden wir den Generator für die Zufallszahlen selbst implementieren.

Modulo

Um Zufallszahlen zu "berechnen", benutzt man den Modulo-Operator %. Dieser berechnet den Rest einer ganzzahligen Division.

Berechne folgende Beispiele. Was fällt Dir auf? Was bedeutet wohl der Ausdruck 9 ≡ 1 (mod 8), gesprochen als: 9 ist kongruent 1 modulo 8 ?

3 % 8
5 % 8
11 % 8
13 % 8
19 % 8
21 % 8

Man kann sich das Rechnen mit dem Modulo-Operator auch anhand einer Uhr verdeutlichen:

Quelle: Algorithmus der Woche

Erkläre was die Uhr und der Modulo-Operator miteinander zu tun haben.

Berechnung von Zufallszahlen

Wenn Du möchtest, kannst Du selbst versuchen den Modulo-Operator zu benutzen, um eine Folge zufällig wirkender Zahlen zu erzeugen. Du kannst dazu z.B. eine Tabellenkalkulation benutzen. Tipp: Um die n-te Zufallszahl zu erzeugen, solltest Du die (n-1)-te Zufallszahl verwenden.

Wenn Du keine Experimente machen möchtest, oder Deine Lösung nun mit einer möglichen, üblichen Methode vergleichen möchtest, kannst Du jetzt die Seite weiterscrollen...

Ein übliches Verfahren zur Berechnung von Zufallszahlen lässt sich folgendermaßen beschreiben:

x1 := (a*x0 + c) % m
x2 := (a*x1 + c) % m
x3 := (a*x2 + c) % m
x4 := (a*x3 + c) % m
... usw ...

Erstelle eine entsprechende Zahlenfolge für die Beispiele x0=1, a=5, c=7, m=8. Benutze dazu eine Tabellenkalkulation und stelle den Graphen der Funktion dar. Experimentiere auch mit anderen Werten für x0, a und c und beschreibe Deine Beobachtungen.

Programmiere eine Klasse "Zufallszahlgenerator" mit Hilfe der oben berechneten Zahlenfolge. Sollten die Methoden zum erzeugen der Zufallszahlen Klassenmethoden oder gewöhnliche Methoden sein? Vergleiche auch mit der Klasse Random und mit der Zufallszahlerzeugung im Paket math in Java.

Ändere Dein Programm so ab, dass z.B. die Werte a=5, c=1, m=16 oder a=81, c=1, m=100 benutzt werden. Inwiefern ändert das die Zufallszahlen? Was kann man tun, um Zufallszahlen zwischen 0 und 2 - so wie wir es für Schnick, Schnack, Schnuck benötigen - zu erzeugen.

Bewerte den Begriff "Zufallszahl", wenn es um Zufallszahlen im Computer geht. Berücksichtige dabei, dass z.B. für den Zufallszahlengenerator in Java die Werte a=252149003917, c=11 und m=248 benutzt werden.

Implementierung des Spiels

Du kannst nun das Spiel implementieren. Benutze dazu den selbst programmierten Zufallszahlengenerator.

Quellen

Ein Teil der Ideen dieser Seite stammt von der Seite Algorithmus der Woche, die sich auch gut zum Nachlesen eignet (pdf-Version).