Zufallszahlen - Institut für Pervasive Computing

Institut für Pervasive Computing
Johannes Kepler Universität Linz
Übung 8
Übungen zu Algorithmen und Datenstrukturen 1
Übungen zu Praktische Informatik 1
SS 2012
Letzter Abgabetermin: Mi. 20.06.2012, 23:59 Uhr
Abgabe via Internet: www.pervasive.jku.at/Teaching/
Zufallszahlen
1. Käselaib
14 Punkte
Ein großer Käselaib wird einmal horizontal durchgeschnitten und
vertikal halbiert (siehe Abbildung 1). Betrachtet man nun einen
Teil des Käselaibs an seiner horizontalen Schnittfläche, erkennt
man eine halbkreisförmige Fläche, die in Abbildung 2 ersichtlich
ist.
Man sieht, dass der Käse mehrere Löcher an verschiedenen
Stellen hat, die sowohl überlappen, als auch an der anderen
Schnittkante durchgeschnitten worden sein können.
Abbildung 1: Schnittlinien
Gesucht ist nun ein Algorithmus in Jana, der den
Flächeninhalt der Schnittfläche (abzüglich) der Löcher
näherungsweise berechnet.
Es stehen Ihnen folgende Daten zur Verfügung:
• float rCheese
// Radius des Käselaibs
• float holesX[n]
// x-Koordinaten der Löcher
• float holesY[n]
// y-Koordinaten der Löcher
• float holesR[n]
// Radien der Löcher
• int n
// Anzahl der Löcher
• int numPoints
// Anzahl der Zufallspunkte
Der Mittelpunkt der halbkreisförmigen Schnittfläche hat die
Koordinaten (0, rCheese), die linke untere Ecke befindet
sich im Ursprung des Koordinatensystems.
Sie dürfen die Funktion float fRand() verwenden, die eine
Zufallszahl im Intervall [0, 1[ generiert.
Abbildung 2: Schnittfläche
Verwenden Sie für die Flächenberechnung den Monte-Carlo-Algorithmus: es werden zufällig
Punkte erzeugt, die sich entweder außerhalb, im Käse oder in einem der Löcher befinden. Aus
dem Verhältnis der Zufallspunkte die „im Käse“ beziehungsweise außerhalb (oder in einem
Loch) gelandet sind, lässt sich die gesuchte Querschnittsfläche näherungsweise berechnen.
Der Algorithmus soll folgendermaßen aufgerufen werden können:
float approxCheeseArea(↓rCheese ↓holesX ↓holesY ↓holesR ↓n ↓numPoints)
Hinweise:
• Überlegen Sie, in welchem Intervall Sie Zufallszahlen erzeugen müssen.
• Sie dürfen zur Lösung der Aufgabe keine Kreisfläche mathematisch berechnen!
2. Lotto 6 aus 45
4+6 Punkte
Ein Programmieranfänger schreibt einen Algorithmus für das zufällige Generieren eines LottoQuicktipps, bei dem aus den Zahlen 1-45 sechs verschiedene Zahlen gezogen werden. Dieser
sieht folgendermaßen aus:
int[] generateNumbers() {
int numbers[1:6]
for (int i = 1..6) {
boolean newNumber = false
int random = smallRand(↓45) + 1
while (!newNumber) {
newNumber = true
for (int j = 1..i-1) {
if (numbers[j] == random) {
newNumber = false
random = random + 1
if (random == 46) {
random = 1
}
}
}
}
numbers[i] = random
}
return numbers
}
a) Beurteilung des vorliegenden Algorithmus
Was sagen Sie zu diesem Ansatz? Analysieren Sie den Algorithmus, identifizieren Sie
mögliche Fehlerstellen und beschreiben Sie, warum er für eine „statistisch korrekte“
Generierung eines Lotto-Quicktipps ungeeignet ist.
b) Entwurf eines Algorithmus
Entwerfen Sie anschließend einen etwas allgemeineren Algorithmus, der eine obere und
eine untere Grenze von möglichen Lotteriezahlen entgegennimmt und eine gegebene
Anzahl von unterschiedlichen Zufallszahlen zurückliefert:
int[] generateNumbers(↓int low ↓int high ↓int num)
// low ist die Untergrenze der Zufallszahlen im Intervall [low, high]
// high ist die Obergrenze der Zufallszahlen im Intervall [low, high]
// num ist die Anzahl der zu generierenden Zufallszahlen aus [low, high]
Sie können dazu die Funktion int smallRand(↓int n) voraussetzen, die gleichverteilte
ganze Zufallszahlen aus dem Intervall [0, n-1] liefert. Der Rückgabewert der Funktion
soll ein Integer-Array sein, das mit den entsprechend erzeugten Zufallszahlen gefüllt
ist.
Achten Sie insbesondere darauf, dass alle möglichen Zahlenkombinationen mit gleicher
Wahrscheinlichkeit erzeugt werden.