随机化算法 实现

文章目录

数x1,x2…的生成满足

xi+1 = Aximod M

需要给出x0作为种子,比如x0 = 1, M = 11, A = 7时生成的数为

1
7, 5, 2, 3, 10, 4, 6, 9, 8, 1, 7, 5...

经验总结,建议M取231 - 1 = 2147483647, A取48271

实现

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
static const int M = 2147483647;
static const int A = 48271;
static const int Q = M / A;
static const int R = M % A;
class
{
public:
explicit (int initialValue = 1);
int randomInt();
double random0_1();
int randomInt(int low, int high);
private:
int state_;
};
Random::Random(int initialValue)
{
if(initialValue < 0)
initialValue += M;
state_ = initialValue;
if(state_ == 0)
state_ = 1;
}
int Random::randomInt()
{
int tempState = A * (state_ % Q) - R*(state_ / Q);
if(tempState >= 0)
state_ = tempState;
else
state_ = tempState + M;
return state_;
}
double Random::random0_1()
{
return (double)randomInt() / M;
}
int Random::randomInt(int low, int high)
{
if(low > high)
return -1;
return randomInt() % (high - low + 1) + low;
}
int main()
{
Random r;
printf("%dn", r.randomInt());
printf("%fn", r.random0_1());
printf("%dn", r.randomInt(3, 10));
return 0;
}