用Random(0, 1)来实现Random(a, b)

通过Random(0, 1)生成Random(a, b),实际上我们生成random(0, b-a) + a 就可以了,然后问题就转换为了Random(0, 1)生成Random(0, n), 这里n = b - a。
由于Random(0, 1)我们认为产生的 0 跟 1 这两个数是随机的并且相互独立的。所以,我们可以求得最小的 bit 位数,使其恰好大于等于n,通过random(0, 1)来置位二进制位,然后加上a,如果该值落在[a, b]之间,满足条件,否则丢掉改值,继续寻找其他值!

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
#include <iostream>
#include <stdlib.h>
#include <ctime>

using namespace std;

int random_0_1()
{
return rand() % 2;
}

int getBit(int a, int b)
{
int n = b - a + 1;
int bit = 0;
int value = 1;

while (value < n)
{
bit++;
value = value << 1;
}

return bit;
}

int random_a_b(int a, int b)
{
int bit = getBit(a, b);
int flag;
int result = 0;
while (true)
{
for (int i = 0; i < bit; i++)
{
flag = random_0_1();
flag = flag << i;
result |= flag;
}

if (result + a > b)
{
result = 0; // 不符合要求,重新计算。
}
else
{
break;
}
}
return result + a;
}

int main()
{
srand(unsigned(time(NULL)));
int a[10] = {0};

for (int i = 0; i < 1000000; i++)
{
int result = random_a_b(1, 10);
a[result-1]++;
}
for (int i = 0; i < 10; i++)
{
cout << (i+1) << ":" << a[i] << endl;
}
return 0;
}

上面的代码运行100万次,在我机器里面随机产生的数据大概[1, 10]是这样:

1
2
3
4
5
6
7
8
9
10
1:100175
2:99906
3:99781
4:100109
5:99816
6:100119
7:100126
8:99920
9:99895
10:100153

您的支持将鼓励我继续创作!
0%