随机函数
概述
要想使用随机化技巧，前提条件是能够快速生成随机数．本文将介绍生成随机数的常见方法．
随机数与伪随机数
说一个单独的数是「随机数」是无意义的，所以以下我们都默认讨论「随机数列」，即使提到「随机数」，指的也是「随机数列中的一个元素」．
现有的计算机的运算过程都是确定性的，因此，仅凭借算法来生成真正 不可预测 、不可重复 的随机数列是不可能的．
然而在绝大部分情况下，我们都不需要如此强的随机性，而只需要所生成的数列在统计学上具有随机数列的种种特征（比如均匀分布、互相独立等等）．这样的数列即称为 伪随机数 序列．
随机数与伪随机数在实际生活和算法中的应用举例：
- 抽样调查时往往只需使用伪随机数．这是因为我们本就只关心统计特征．
- 网络安全中往往要用到（比刚刚提到的伪随机数）更强的随机数．这是因为攻击者可能会利用可预测性做文章．
- OI/ICPC 中用到的随机算法，基本都只需要伪随机数．这是因为，这些算法往往是 通过引入随机数 来把概率引入复杂度分析，从而降低复杂度．这本质上依然只利用了随机数的统计特征．
- 某些随机算法（例如 Moser 算法）用到了随机数的熵相关的性质，因此必须使用真正的随机数．
实现
rand
用于生成伪随机数，缺点是比较慢，使用时需要 #include<cstdlib>．
调用 rand() 函数会返回一个 [0,RAND_MAX] 中的随机非负整数，其中 RAND_MAX 是标准库中的一个宏，在 Linux 系统下 RAND_MAX 等于 231 −1231−1
．可以用取模来限制所生成的数的大小．
使用 rand() 需要一个随机数种子，可以使用 srand(seed) 函数来将随机种子更改为 seed，当然不初始化也是可以的．
同一程序使用相同的 seed 两次运行，在同一机器、同一编译器下，随机出的结果将会是相同的．
有一个选择是使用当前系统时间来作为随机种子：srand(time(nullptr))．
Warning
在 Windows 系统下 rand() 返回值的取值范围为 [0,215)[0,215)（即 RAND_MAX 等于 215 −1215−1），当需要生成的数不小于 215215 时建议使用 (rand() << 15 | rand()) 来生成更大的随机数．
关于 rand() 和 rand()%n 的随机性：
- C/C++ 标准并未关于
rand()所生成随机数的任何方面的质量做任何规定． - GCC 编译器对
rand()所采用的实现方式，保证了分布的均匀性等基本性质，但具有 低位周期长度短 等明显缺陷．（例如在笔者的机器上，rand()%2所生成的序列的周期长约 2 ⋅1062⋅106） - 即使假设
rand()是均匀随机的，rand()%n也不能保证均匀性，因为[0,n)中的每个数在0%n,1%n,...,RAND_MAX%n中的出现次数可能不相同．
预定义随机数生成器
定义了数个特别的流行算法．如没有特别说明，均定义于头文件 <random>．
Warning
预定义随机数生成器仅在于 C++11 标准3中开始使用．
mt19937
是一个随机数生成器类，效用同 rand()，随机数的范围同 unsigned int 类型的取值范围．
其优点是随机数质量高（一个表现为，出现循环的周期更长；其他方面也都至少不逊于 rand()），且速度比 rand() 快很多．使用时需要 #include<random>．
mt19937 基于 32 位梅森缠绕器，由松本与西村设计于 1998 年1，使用时用其定义一个随机数生成器即可：std::mt19937 myrand(seed)，seed 可不填，不填 seed 则会使用默认随机种子．
mt19937 重载了 operator ()，需要生成随机数时调用 myrand() 即可返回一个随机数．
另一个类似的生成器是 mt19937_64，基于 64 位梅森缠绕器，由松本与西村设计于 2000 年，使用方式同 mt19937，但随机数范围扩大到了 unsigned long long 类型的取值范围．
代码示例
---|---
#### `minstd_rand0`
线性同余算法由 Lewis、Goodman 及 Miller 发现于 1969，由 Park 与 Miller 于 1988 采纳为「最小标准」．
计算公式如下，其中 𝐴,𝐶,𝑀A,C,M 为预定义常数．
𝑠𝑖≡𝑠𝑖−1×𝐴+𝐶mod𝑀si≡si−1×A+CmodM
`minstd_rand()` 是较新的「最小标准」，为 Park、Miller 和 Stockmeyer 于 1993 推荐．
对于 `minstd_rand0()`，𝑠s 的类型取 32 位无符号整数，𝐴A 取 16807，𝐶C 取 0，𝑀M 取 2147483647．
对于 `minstd_rand()`，𝑠s 的类型取 32 位无符号整数，𝐴A 取 48271，𝐶C 取 0，𝑀M 取 2147483647．
### `random_shuffle`
用于随机打乱指定序列．使用时需要 `#include<algorithm>`．
使用时传入指定区间的首尾指针或迭代器（左闭右开）即可：`std::random_shuffle(first, last)` 或 `std::random_shuffle(first, last, myrand)`
内部使用的随机数生成器默认为 `rand()`．当然也可以传入自定义的随机数生成器．
关于 `random_shuffle` 的随机性：
* C++ 标准中要求 `random_shuffle` 在所有可能的排列中 **等概率** 随机选取，但 GCC2编译器 **并未** 严格执行．
* GCC 中 `random_shuffle` 随机性上的缺陷的原因之一，是因为它使用了 `rand()%n` 这样的写法．如先前所述，这样生成的不是均匀随机的整数．
* 原因之二，是因为 `rand()` 的值域有限．如果所传入的区间长度超过 `RAND_MAX`，将存在某些排列 **不可能** 被产生4．
Warning
`random_shuffle` 已于 C++14 标准中被弃用，于 C++17 标准中被移除．
### `shuffle`
效用同 `random_shuffle`．使用时需要 `#include<algorithm>`．
区别在于必须使用自定义的随机数生成器：`std::shuffle(first, last, myrand)`．
GCC2实现的 `shuffle` 符合 C++ 标准的要求，即在所有可能的排列中等概率随机选取．
下面是用 `rand()` 及 `random_shuffle()` 编写的一个数据生成器．生成数据为 [「ZJOI2012」灾难](https://www.luogu.com.cn/problem/P2597) 的随机小数据．
---|---
下面是用 mt19937 及 shuffle() 编写的同一个数据生成器．
---|---
下面是随机排列前十个正整数的一个实现．
---|---
非确定随机数的均匀分布整数随机数生成器
random_device 是一个基于硬件的均匀分布随机数生成器，在熵池耗尽 前可以高速生成随机数．该类在 C++11 定义，需要 random 头文件．由于熵池耗尽后性能急剧下降，所以建议用此方法生成 mt19937 等伪随机数的种子，而不是直接生成．
random_device 是非确定的均匀随机位生成器，尽管若不支持非确定随机数生成，则允许实现用伪随机数引擎实现．目前笔者尚未接到报告称 NOIP 评测机不支持基于硬件的均匀分布随机数生成．但出于保守考虑，建议使用该算法生成随机数种子．
参考代码如下．
---|---
可能的输出如下．
---|---
随机数分布
这里介绍的是要求生成的随机数按照一定的概率出现，如等概率，伯努利分布，二项分布，几何分布，标准正态（高斯）分布．
具体类名请参见 伪随机数生成——随机数分布 的列表．
实现
下面的程序模拟了一个六面体骰子．
---|---
### 其他实现方法
有的时候我们需要实现自己的随机数生成器．下面是一些常用的随机数生成方法．
#### 线性同余随机数生成器
利用下式来生成随机数序列 {𝑅𝑖}{Ri}：
𝑅𝑖+1=(𝐴×𝑅𝑖+𝐵)mod𝑃Ri+1=(A×Ri+B)modP
其中 𝐴,𝐵,𝑃A,B,P 均为常数．
该方法实现难度低，但生成的随机序列周期长度较短（周期最大为 𝑃P，但大多数情况下都会比 𝑃P 短）．
参考实现
---|---
时滞斐波那契随机数生成器
利用下式来生成随机数序列 {𝑅𝑖}{Ri}（其中 0 <𝑗 <𝑘0<j<k）：
𝑅𝑖≡𝑅𝑖−𝑗⋆𝑅𝑖−𝑘mod𝑃Ri≡Ri−j⋆Ri−kmodP
这里的 𝑃P 通常取 22 的幂（常用 232232 或 264264），⋆⋆ 表示二元运算符，可以使用加法，减法，乘法，异或．
该方法较传统的线性同余随机数生成器而言，拥有更长的周期，但随机性受初始条件影响较大．
参考实现
---|---
## 参考资料与注释
* * *
1. [Mersenne Twister algorithm](https://en.wikipedia.org/wiki/Mersenne_Twister) ↩
2. 版本号为 GCC 9.2.0 ↩↩
3. [伪随机数生成 - cppreference.com](https://zh.cppreference.com/w/cpp/numeric/random#%E9%A2%84%E5%AE%9A%E4%B9%89%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8) ↩
4. [Don't use rand(): a guide to random number generators in C++](https://codeforces.com/blog/entry/61587) ↩
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/misc/random.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/misc/random.md "edit.link.title")
> __本页面贡献者：[Ir1d](https://github.com/Ir1d), [TianyiQ](https://github.com/TianyiQ), [StudyingFather](https://github.com/StudyingFather), [partychicken](https://github.com/partychicken), [Tiphereth-A](https://github.com/Tiphereth-A), [Henry-ZHR](https://github.com/Henry-ZHR), [Marcythm](https://github.com/Marcythm), [ouuan](https://github.com/ouuan), [Xeonacid](https://github.com/Xeonacid), [Arielfoever](https://github.com/Arielfoever), [c-forrest](https://github.com/c-forrest), [CCXXXI](https://github.com/CCXXXI), [Enter-tainer](https://github.com/Enter-tainer), [ksyx](https://github.com/ksyx), [R-G-Mocoratioen](https://github.com/R-G-Mocoratioen), [Vivian Heleneto](mailto:xiongjiahui2004@foxmail.com), [woruo27](https://github.com/woruo27)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用