学习一下如何在 C++ 中合理、现代地生成一些高质量随机数。

rand 函数

生成一个在 [0, RAND_MAX] 范围内的随机数。使用 srand 设置种子。

在 Windows 下, RAND_MAX 的值一般为 32767，而在 linux 环境下，RAND_MAX 的值一般为 2147483647。因此，千万不要在交上去的代码中写出 rand()<<15|rand() 这样的代码（在 Windows 环境下工作正常，但是在 linux 环境下会有符号整数溢出）。

如果要生成一个在 [l, r] 范围内的随机数，可以使用 rand()%(r-l+1)+l （注意：[l, r] 内每个数的概率是不同的，但是一般来说，这样也够用了）。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;


int rand_int(int l,int r){
    return rand()%(r-l+1)+l;
}

int main(){
    srand(time(0));
    for(int i=1;i<=100;i++)
        printf("%d\n",rand_int(2,6));
    return 0;
}

random 库

上面的算法看起来很好用，但是在程序跑的很快的时候（比如对拍），一秒内生成的随机数都是一样的（那你拍了个寂寞）。

C++11 引入了一套全新的 random 算法。我们来分别介绍几个概念。

random_device

通过硬件生成真正的不确定随机数（如果硬件不支持，标准也允许使用伪随机生成方法实现此函数），返回一个 unsigned int。

实现了仿函数。调用后返回一个在 unsigned int 范围内的随机数。无需设置种子，得到的就是随机数。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;

int main(){
    random_device rd;
    for(int i=0;i<5;i++){
        printf("%u\n",rd());
    }
    return 0;
}

一般来说，我们将其的输出用作其他随机数生成器的种子。

为什么不直接把这个作为随机数生成器？以下摘录自 cppreference。

note: demo only: the performance of many implementations of random_device degrades sharply once the entropy pool is exhausted. For practical use random_device is generally only used to seed a PRNG such as mt19937

大意：当熵池耗尽后，random_device 的性能急剧下降。（因为这是一个真正的不确定随机数生成器）
总之，在代码中只调用一次，把它作为其他随机数生成器的种子就可以了。

mt19937

是一个梅森旋转法的预定义特化。构造函数接受一个种子。仿函数生成一个随机数。

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;

int main(){
    random_device rd; // 用 random_device 设置种子
    mt19937 gen(rd()); // 创建 mt19937

    for(int i=1;i<=100;i++){
        printf("%lu\n",gen()); // 用仿函数生成一个随机数
    }
    return 0;
}

distribution

你可能觉得有 mt19937 之后，我再取取模，除一除就够了。但是不要忘了，我们之前说过，用取模生成的随机数的每一个数的概率是不均匀的。

为此，C++ 给我们提供了一些预定义的分布，让我们将生成器 (就是可以随机生成一个 unsigned int 的随机数生成器) 生成的随机数以某种概率映射到一个范围中。

我们需要记住两个分布：uniform_int_distribution 和 uniform_real_distribution 分别用来生成区间内的整数和浮点数。（uniform_int_distribution 两端闭，uniform_real_distribution 左闭右开）

使用方法：模板的参数为生成随机数的类型（uniform_int_distribution 默认 int，uniform_real_distribution 默认 double）可以省略。构造函数指定上下限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main(){
    random_device rd; // 用 random_device 设置种子
    mt19937 gen(rd()); // 创建 mt19937
    uniform_int_distribution<> dist(2,6); // 创建好分布

    for(int i=1;i<=100;i++){
        // 使用分布的仿函数将随机数引擎传入
        printf("%d\n",dist(gen)); // 分布会帮我们将随机数引擎生成的随机数映射到这一个范围中
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;

int main(){
    random_device rd;
    mt19937 gen(rd());
    uniform_real_distribution<> dist(0.,1.); // 浮点数

    for(int i=1;i<=100;i++){
        printf("%f\n",dist(gen)); // [0.0,1.0)
    }
    return 0;
}

总结

画一张图。