forked from algorithmzuo/algorithm-primary
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode02_RandToRand.java
More file actions
231 lines (197 loc) · 4.72 KB
/
Code02_RandToRand.java
File metadata and controls
231 lines (197 loc) · 4.72 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
package class02;
public class Code02_RandToRand {
// 此函数只能用，不能修改
// 等概率返回1~5
public static int f() {
return (int) (Math.random() * 5) + 1;
}
// 等概率得到0和1
public static int a() {
int ans = 0;
do {
ans = f();
} while (ans == 3);
return ans < 3 ? 0 : 1;
}
// 等概率返回0~6
public static int b() {
int ans = 0;
do {
ans = (a() << 2) + (a() << 1) + a();
} while (ans == 7);
return ans;
}
// 等概率返回1~7
public static int c() {
return b() + 1;
}
// 这个结构是唯一的随机机制
// 你只能初始化并使用，不可修改
public static class RandomBox {
private final int min;
private final int max;
// 初始化时请一定不要让mi==ma
public RandomBox(int mi, int ma) {
min = mi;
max = ma;
}
// 13 ~ 17
// 13 + [0,4]
public int random() {
return min + (int) (Math.random() * (max - min + 1));
}
public int min() {
return min;
}
public int max() {
return max;
}
}
// 利用条件RandomBox，如何等概率返回0和1
public static int rand01(RandomBox randomBox) {
int min = randomBox.min();
int max = randomBox.max();
// min ~ max
int size = max - min + 1;
// size是不是奇数，odd 奇数
boolean odd = (size & 1) != 0;
int mid = size / 2;
int ans = 0;
do {
ans = randomBox.random() - min;
} while (odd && ans == mid);
return ans < mid ? 0 : 1;
}
// 给你一个RandomBox，这是唯一能借助的随机机制
// 等概率返回from~to范围上任何一个数
// 要求from<=to
public static int random(RandomBox randomBox, int from, int to) {
if (from == to) {
return from;
}
// 3 ~ 9
// 0 ~ 6
// 0 ~ range
int range = to - from;
int num = 1;
// 求0～range需要几个2进制位
while ((1 << num) - 1 < range) {
num++;
}
// 我们一共需要num位
// 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
int ans = 0;
do {
ans = 0;
for (int i = 0; i < num; i++) {
ans |= (rand01(randomBox) << i);
}
} while (ans > range);
return ans + from;
}
public static void main(String[] args) {
System.out.println("测试开始");
// Math.random() -> double -> [0,1)
//
int testTimes = 10000000;
int count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() < 0.75) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
System.out.println("=========");
// [0,1) -> [0,8)
count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() * 8 < 5) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
System.out.println((double) 5 / (double) 8);
int K = 9;
// [0,K) -> [0,8]
int[] counts = new int[9];
for (int i = 0; i < testTimes; i++) {
int ans = (int) (Math.random() * K); // [0,K-1]
counts[ans]++;
}
for (int i = 0; i < K; i++) {
System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
}
System.out.println("=========");
count = 0;
double x = 0.17;
for (int i = 0; i < testTimes; i++) {
if (xToXPower2() < x) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
System.out.println((double) 1 - Math.pow((double) 1 - x, 2));
System.out.println("==========");
count = 0;
for (int i = 0; i < testTimes; i++) {
if (f2() == 0) {
count++;
}
}
System.out.println((double) count / (double) testTimes);
System.out.println("==========");
counts = new int[8];
for (int i = 0; i < testTimes; i++) {
int num = g();
counts[num]++;
}
for (int i = 0; i < 8; i++) {
System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
}
}
// 返回[0,1)的一个小数
// 任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x平方
public static double xToXPower2() {
return Math.min(Math.random(), Math.random());
}
// lib里的，不能改！
public static int f1() {
return (int) (Math.random() * 5) + 1;
}
// 随机机制，只能用f1，
// 等概率返回0和1
public static int f2() {
int ans = 0;
do {
ans = f1();
} while (ans == 3);
return ans < 3 ? 0 : 1;
}
// 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个
public static int f3() {
return (f2() << 2) + (f2() << 1) + f2();
}
// 0 ~ 6等概率返回一个
public static int f4() {
int ans = 0;
do {
ans = f3();
} while (ans == 7);
return ans;
}
public static int g() {
return f4() + 1;
}
// 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！
public static int x() {
return Math.random() < 0.84 ? 0 : 1;
}
// 等概率返回0和1
public static int y() {
int ans = 0;
do {
ans = x();
} while (ans == x());
return ans;
}
}