【基础】伪随机数生成器mt19937

使用方法

使用下列代码定义一个以seed为伪随机数种子的uint32范围内的伪随机数生成器：

mt19937 rnd(seed);

定义完成后，使用下列代码生成若干个uint32范围内的伪随机数，并将其赋值给uint32类型变量r0, r1, r2, r3，它们极大概率互不相同：

mt19937 rnd(time(nullptr));

void randTest() {
    uint32_t r0 = rnd();
    uint32_t r1 = rnd();
    uint32_t r2 = rnd();
    uint32_t r3 = rnd();
    D1(r0);     //r0 = 1890107454
    D1(r1);     //r1 = 1903163696
    D1(r2);     //r2 = 1307137696
    D1(r3);     //r3 = 1016102494
}

同理，使用下列代码测试64位版本的伪随机数生成器：

mt19937_64 rnd(time(nullptr));

void randTest() {
    uint64_t r0 = rnd();
    uint64_t r1 = rnd();
    uint64_t r2 = rnd();
    uint64_t r3 = rnd();
    D1(r0);     //r0 = 16757819831475078962
    D1(r1);     //r1 = 10644585941176734154
    D1(r2);     //r2 = 14550312371103145914
    D1(r3);     //r3 = 16538001574918540854
}

更强的伪随机数种子

有些很无聊的人会喜欢uphack使用time(nullptr)的代码，所以可以使用chrono::system_clock::now().time_since_epoch().count()来代替time(nullptr)。

在本地调试时，常常希望复现某个出错的情形，所以使用下面的条件编译进行控制：

#define TIME chrono::system_clock::now().time_since_epoch().count()

#ifdef LOCAL
int rnd_seed = 19937;
#else
int rnd_seed = TIME;
#endif // LOCAL

mt19937 rnd(rnd_seed);

生成 ([L,R]) 范围内的随机整数

转换成double类型后舍入到最近的整数。

#define TIME chrono::system_clock::now().time_since_epoch().count()

#ifdef LOCAL
int rnd_seed = 19937;
#else
int rnd_seed = TIME;
#endif // LOCAL

mt19937 rnd(rnd_seed);

int rangeRand(int L, int R) {
    int res = (int)((1.0 * rnd() / UINT_MAX) * (R - L + 1)) + L;
    return res;
}

void rangeRandTest() {
    map<int, int> M;
    int n = 2000000, L = 1, R = 10;
    for(int i = 1; i <= n; ++i) {
        int t = rangeRand(L, R);
        M[t] += 1;
    }
    int minnum = INF, maxnum = -INF;
    int mincnt = INF, maxcnt = -INF;
    for(auto i : M) {
        printf("%d:%.6f%
", i.first, 100.0 * i.second / n);
        cmin(minnum, i.first);
        cmax(maxnum, i.first);
        cmin(mincnt, i.second);
        cmax(maxcnt, i.second);
    }
    D2(minnum, maxnum);
    D2(mincnt, maxcnt);
}

输出结果如下：

1:9.978100%
2:10.036300%
3:10.015950%
4:9.996550%
5:9.984650%
6:9.980050%
7:9.985200%
8:10.000350%
9:10.012050%
10:10.010800%
minnum = 1, maxnum = 10
mincnt = 199562, maxcnt = 20072

分布非常均匀。注意，每个数字的出现次数是均匀分布，但出现次数的出现次数是正态分布。

洗牌算法 shuffle

使用方法如下：

#define TIME chrono::system_clock::now().time_since_epoch().count()

#ifdef LOCAL
int rnd_seed = 19937;
#else
int rnd_seed = TIME;
#endif // LOCAL

mt19937 rnd(rnd_seed);

void shuffleTest() {
    int n = 100, a[n + 1];
    for(int i = 1; i <= n; ++i) a[i] = i;
    shuffle(a + 1, a + 1 + n, rnd);
    for(int i = 1; i <= n; ++i) {
        printf("%d ", a[i]);
        if(i % 10 == 0)
            putchar('
');
    }
}

//61 13 98 64 5 79 30 65 83 11
//85 9 88 74 14 19 68 56 70 59
//29 90 82 7 48 36 75 6 50 26
//97 28 92 24 1 35 62 77 89 2
//3 39 71 53 91 52 80 55 58 100
//38 4 23 32 95 47 86 20 45 43
//81 60 99 57 33 8 15 37 78 93
//40 96 17 12 76 27 31 41 51 42
//84 66 21 87 25 67 10 63 69 94
//16 46 49 18 54 22 44 73 34 72

注意默认的random_shuffle()不够随机，在严格的题目中容易翻车。