引言

C++11 在 g++5.0 的时候就已经被 GNU 官方设定为默认选项，这个标准也有着“20 年来 C++语言标准最剧烈的一次修订”${}^{[1]}$的称谓。而 CCF 公开的 NOI Linux2.0 中的 g++更是到了 9.3 版${}^{[2]}$，支持到 C++14 标准。这就意味着，使用 C++11 中的随机数生成方式是更加现代的选择。

传统的数据生成方式

使用标准 C 库

在原来，数据生成一般会使用标准 C 的rand()函数，而rand()函数的原理是较为简单的：使用线性映射+取模运算生成${}^{[3]}$。

大概实现的方法（线性同余法）：

我有一个变量next，代表了用来生成下一个随机数的一个系数

定义一个函数srand()，这个srand()只实现一件事：将next置为种子的值。

然后我现在要生成一个随机数，怎么办呢？就是将当前的next乘上一个很大的素数，然后和另外一个比较大的素数取模，从而得到一个随机数。然后把这个随机数赋值给next，让它参与下一次生成。

举个比较小的例子，我现在的种子如果是$30$，用来乘的素数是$7$，用来模的素数是$11$，那么第一个随机数就按照$30\times 7=210\equiv 1(mod11)$的方式生成，然后输出这个随机数$1$，将next置为 1，然后每一次生成随机数的时候都重复这个操作。（当然，实际生成时用的素数和种子都比这大的多的多）

仔细的人就会发现，这不就是教练讲的hash函数吗？对，事实上hash函数和这个的实现是差不多的，区别在于hash函数是将输入的值作为种子，而这里是将前一次生成的随机数作为种子。

优缺点

优点

这种方法有没有好处呢？是有好处的，我们从完全剩余系${}^{[4]}$的角度来看，这样模的方式可以使得每个数生成的概率是几乎一样的，或者说，在一定范围内，每个数都能正好生成一次。

缺点${}^{[5]}$

那么接下来就讲讲这种方式的坏处：

1、我们调用srand()的时候，惯用的做法是srand(time(0))，如果多组数据生成是在同一个程序当中的，那么这样没问题，但是如果是单个程序多次调用的，那么会出现一个问题：数据生成是极快的，可能多组数据生成所需时间不超过 1s，那就意味着每次调用中time(0)(这个函数是从标准年的 1 月 1 日开始到现在经过的秒数)，如果在同一秒内就会是相同值。而为此，我们教练以及大多数人采取的做法都是跑很多很多次循环消耗时间或者使用系统的延时函数延时 1 秒，这种办法不是说不行，但是是一种非常没有远见的做法。

2、写过 Python 的都知道，Python 里面有一个生成随机数的函数是randint()，可以生成一个范围内的一个值。而rand()函数每次生成的都是一个大整数，要能够实现这种功能需要取模再加，一不小心就会写错，不方便。

3、无法直接指定每个数生成的概率：如果我生成时，希望某些数生成概率大，某些数生成概率小，那么使用rand()函数就是十分复杂的，你必须要先取模将随机数收缩到一个比较小的区间，然后把这个区间按照概率划分成若干个小区间，考虑随机数落在不同小区间时采取不同的操作，这样十分复杂。

4、无法生成浮点数：遇到浮点数生成时，使用这种方式就需要将整数部分和小数部分剖分，分别输出整数部分和小数部分，在中间生成小数点，很难实现很多比较高级的操作。

使用系统硬件

什么叫使用系统硬件

所谓使用系统硬件，是一个比较玄乎的操作。由于 Unix 设计哲学里面有一条：一切皆文件。所以在 Unix 系的 Linux 下，/dev 文件夹下就有两个生成随机数的设备文件：/dev/random，/dev/urandom。这里简述以下两者的区别${}^{[6]}$：/dev/random 生成的是真随机数，会读取系统的随机数池，生成速度较慢，是依赖 CPU 内部实现的。而/dev/urandom 生成的是伪随机数，是读取/dev/random 中的数作为种子后根据一定算法生成的。（具体真随机数伪随机数的区别请详见下文）

怎么使用系统硬件？

我放一段代码你就知道了。

...
freopen("/dev/urandom","r",stdin);  //这一步是将操作系统的随机数硬件定向到输入输出流
char a;
a=getchar(); //从输入输出流中读取一个数
srand(getchar()*getchar()*getchar()*time(0)) //你也可以将随机数硬件生成的数相乘后作为rand()的一个种子
...

优缺点

优点

这种随机数的种子是由操作系统提供的，可以避免前文所说数据在同 1s 内生成时相同的问题，随机度也相对较高。

缺点

和使用 C 标准库一样，不太便捷，不能生成实数，概率无法指定等毛病它也有，而且平台依赖性太强，换到不是类 Unix 系统上就是不可行的（虽然我感觉那些非 Linux 的类 Unix 系统，比如 Mac OS，FreeBSD 等也不行）

现代化的数据生成方式

传统数据生成方式有那么多缺陷，我们应该何去何从呢？幸好，C++11 引入了<random>库，内置了很多十分有用的类和函数。

怎么样使用这个库呢？

很简单，和正常库的引用一样，直接一句#include<random>即可。

这些库实现了那些功能呢${}^{[7]}$？

随机数引擎

什么是随机数引擎？随机数引擎是一个类，将其实例化后就是一个对象（通俗的讲，就是个变量），这个对象可以生成不同的随机数，你可以把它当一个每一次输出随机数的变量使用，也可以使用库中给出的随机数生成方法（就是那些末尾是distribution的方法）。

真随机数引擎：random_device，这是一个类，如果使用它需要把它实例化。实例化的方式就是利用这个类声明一个变量，比如random_device rand_dev，这个rand_dev就是一个能够生成随机数的变量（事实上，是个 Functor），可以像rand()一样直接用。但是事实上，我们平时很少直接用真随机数，因为很多真随机数在我们眼中可能并不怎么随机，而且反复取出真随机数会将系统的真随机数池消耗尽，从而导致之后生成随机数的性能下降。所以真随机数一般情况下是作为伪随机数的种子，这相比传统的使用time(0)作为种子的好处是在同 1s 内生成的数仍然是不相同的，可以快速生成数据。

真随机数大致原理是根据分子在不断进行无规则的热运动这一科学原理，然后使用 CPU 内特制的传感器进行生成的，CPU 会源源不断的生成真随机数，并且放到一个叫做随机数池的地方，之后调用时基本上是从池子里取的。但是如果池子里消耗完了，那么就需要等待随机数生成了。

伪随机数引擎：伪随机数引擎有很多，下面大概写一下几个伪随机数引擎，预定义，还有使用的算法。

什么是伪随机数？前面 C 库中实现的就是伪随机数，伪随机数是将种子进行一系列数学变换后得到的，像前面的线性同余法就是一种数学方法。伪随机数是可以复现的，就是你如果指定相同的种子会输出相同的随机数（因为本质上伪随机数就是个数学函数，但是它能够保证在一定范围内生成数的概率是较为均匀的）

（以下是引擎的模板类，这里写一下，但是平时从来不会直接使用，因为要指定很多特殊的值，这些值在不了解的情况下不应该随便指定）

1、线性同余引擎linear_congruential_engine<class UIntType, UIntType a, UIntType c, UIntType m>（类似于标准 C 库中的rand()，使用线性同余法）

2、梅森引擎mersenne_twister_engine<class UIntType,std::size_t w, std::size_t n, std::size_t m,std::size_t r, UIntType a, std::size_t u, UIntType d, std::size_t s,UIntType b, std::size_t t, UIntType c, std::size_t l, UIntType f>（比较常用的方法，不过更常用的是底下的封装，这个算法叫梅森旋转算法，随机性大，重复性较低（就是可能生成几千亿的数据才有可能生成重复的串，相比线性同余法在next构成一个完全剩余系后就会出现重复串））

3、带进位减法引擎subtrack_with_carry_engine<class UIntType std::size_t w, std::size_t s, std::size_t r>（好像是这么翻译的，用一个很古怪的算法，我也没弄明白）

（以下是上面这些基础引擎的封装，是一个类）

一、线性同余引擎的封装

1、minstd_rand0是将标准引擎中的UIntType设为std::uint_fast32_t，a设为 16807，c设为 0，m设为 2147483647 得到的

2、minstd_rand和上面的minstd_rand0的差别是这里的a是 48271

二、梅森旋转算法的封装

1、mt19937是 32 位的随机数生成算法，由两位日本计算机科学家在 1998 年提出

2、mt19937_64是 64 位的随机数生成算法，仍然由这两位日本科学家在 2000 年提出

一般情况下，比较常用后者，因为后者能够生成long long范围内的随机数。

三、其他封装

1、default_random_engine是默认随机数引擎。

更多封装详见cppreference中 Predefined generators 一栏

随机数生成

1、uniform_int_distribution<Type> object(Type from,Type to)作用：生成一个 Functor（仿函数，就是一个实现了小括号运算符的类），能够生成一个类型为Type的，在$[from,to]$范围内的一个随机整数。

2、uniform_real_distribution<Type> object(Type from,Type to)作用：生成一个 Functor，能够生成类型为Type，在$[from,to]$范围内的一个随机实数。当 Type 不指定的时候，默认是double

3、normal_distribution<Type> object(Type arrange, Type std)作用：生成一个均值为arrange，标准差为std,类型为Type的一个 Functor。生成的随机数基本符合正态分布

4、bernoulli_distribution object(double possibility)作用：返回一个 Functor，这个 Functor 返回true的概率是possibility，返回false的概率是1-possibility

5、其他随机数生成方式请见cppreference中 Bernoulli distributions，Poisson distributions，Normal distributions，Sampling distributions 中我没有写过的部分，此处明确写出的是从 C++ Primer 中写到的算法

说了这么多，怎么用这些东西呢？

这里我简单的放几个模板，并且讲述以下这些模板的大体意思。这些模板都是我开发cdg 库时真实用到的，之后我将在 cdg 源码剖析这一专栏中仔细讲述我开发 cdg 库时琢磨出来的技巧等。

1、生成一个在$[from,to]$范围内的一个整数

std::random_device rand_dev; //实例化一个真随机数引擎
std::mt19937_64 rand_eng(rand_dev()); //使用梅森旋转算法实例化一个随机数引擎，并且用真随机数作为种子
long long randll(long long start, long long end) //生成一个类型为long long的伪随机数
{
    std::uniform_int_distribution<signed long long> u(start, end);
    return u(rand_eng);  //使用之前的随机数引擎生成一个随机数
}

2、生成一个随机浮点数

std::random_device rand_dev; //实例化一个真随机数引擎
std::mt19937_64 rand_eng(rand_dev()); //使用梅森旋转算法实例化一个随机数引擎，并且用真随机数作为种子
double randouble(double start, double end)
{
    std::uniform_real_distribution<double> u(start, end);
    return u(rand_eng);//使用之前的随机数引擎生成一个随机数
}

引用和注释

^1：C++ Primer（第五版，电子工业出版社，王刚，杨巨峰 译，以下 C++ Primer 均指该书）推荐序 3

NOI Linux2.0 环境

具体实现可以看这篇博客，讲的还算清楚

不懂完全剩余系看这里

^5：更多缺点请详见 C++ Primer 第 659 页-第 660 页。

这篇文章概括的

cppreference