Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


35. Zufallszahlen



Übungen

  1. Erstellen Sie ein Programm zur Erzeugung von zufälligen, aus vier Buchstaben bestehenden Wörtern (Reihen von Buchstaben). Schätzen Sie, wie viele Wörter Ihr Programm erzeugt, bevor es ein Wort wiederholt.
  2. Wie würden Sie die Erzeugung von Zufallszahlen durch das Werfen von zwei Würfeln und die Bildung ihrer Summe simulieren, mit der zusätzlichen Schwierigkeit, daß es keine standardmäßigen Würfel sind (sie seien zum Beispiel mit den Zahlen 1, 2, 3, 5, 8 und 13 beschriftet)?
  3. Geben Sie die Musterfolge an, die durch ein Schieberegister mit linearer Rückführung von der in Abbildung 35.1 dargestellten Art erzeugt wird, wobei sich jedoch die Abgriffs-Positionen beim ersten und beim letzten Bit befinden sollen. Es werde angenommen, daß das Anfangsmuster 1111 ist.
  4. Warum wären die Funktionen OR oder AND (anstelle der XOR-Funktion) für Schieberegister mit linearer Rückführung ungeeignet?
  5. Erstellen Sie ein Programm zur Erzeugung eines zufälligen zweidimensionalen Bildes. (Beispiel: Man erzeuge zufällige Bits und schreibe »*«, wenn 1 erzeugt wird, und » «, wenn 0 erzeugt wird. Anderes Beispiel: Man benutze Zufallszahlen als Koordinaten in einem zweidimensionalen kartesischen Koordinatensystem und schreibe in den angegebenen Punkten »*«.)
  6. Verwenden Sie einen Zufallszahlengenerator der additiven Kongruenz zur Erzeugung von 1000 positiven ganzen Zahlen, die kleiner als 1000 sind. Entwickeln Sie einen Test, um zu bestimmen, ob sie zufällig sind oder nicht, und wenden Sie ihn an.
  7. Verwenden Sie einen Generator der linearen Kongruenz mit Parametern Ihrer Wahl zur Erzeugung von 1000 positiven ganzen Zahlen, die kleiner als 1000 sind. Entwickeln Sie einen Test, um zu bestimmen, ob sie zufällig sind oder nicht, und wenden Sie ihn an.
  8. Warum wäre es unklug, für den Generator der additiven Kongruenz zum Beispiel b = 3 und c = 6 zu verwenden?
  9. Welchen Wert hat die Chi2 - Statistik für einen entarteten Generator, der immer die gleiche Zahl zurückgibt?
  10. Beschreiben Sie, wie Sie Zufallszahlen erzeugen würden, wenn m größer ist als die Größe eines Computerwortes.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]