forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathRand.java
More file actions
52 lines (49 loc) · 1.61 KB
/
Rand.java
File metadata and controls
52 lines (49 loc) · 1.61 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* Given a function which generates a random integer in the range 1 to 7,
* write a function which generates a random integer in the range 1 to 10 uniformly.
* <p/>
* 1 2 3 4 5 6 7
* 1 1 2 3 4 5 6 7
* 2 8 9 10 1 2 3 4
* 3 5 6 7 8 9 10 1
* 4 2 3 4 5 6 7 8
* 5 9 10 1 2 3 4 5
* 6 6 7 8 9 10 * *
* 7 * * * * * * *
* <p/>
* <p/>
* http://en.wikipedia.org/wiki/Rejection_sampling
* <p/>
* The main idea is when you generate a number in the desired range,
* output that number immediately. If the number is out of the desired range,
* reject it and re-sample again. As each number in the desired range has
* the same probability of being chosen, a uniform distribution is produced.
*/
public class Rand {
public static int rand7() {
// the higher of factor of random, the higher of precision of random 7
return (int) (Math.random() * 100) % 7;
}
public static int rand10() {
while (true) {
int row = rand7() * 7;
int col = rand7();
int index = col + row;
if (index < 40) {
return index % 10;
}
}
}
public static void main(String[] args) {
/* Test: call rand10 many times and inspect the results. */
int[] arr = new int[10];
int test_size = 1000000;
for (int k = 0; k < test_size; k++) {
arr[rand10()]++;
}
for (int i = 0; i < 10; i++) {
double percent = 100.0 * arr[i] / test_size;
System.out.println(i + " appeared " + percent + "% of the time.");
}
}
}