关于随机数

· · 算法·理论

参考资料：OI Wiki

一、随机数

现有的计算机的运算过程都是确定性的，因此，仅凭借算法 来生成真正 不可预测、不可重复 的随机数列是不可能的。

然而在绝大部分情况下，我们都不需要如此强的随机性，而只需要所生成的数列在统计学上具有随机数列的种种特征（比如均匀分布、互相独立等等）。这样的数列即称为 伪随机数 序列。

OI/ICPC 中用到的随机算法，基本都只需要伪随机数。这是因为，这些算法往往是 通过引入随机数来把 概率 引入复杂度分析，从而 降低复杂度。这本质上依然只利用了随机数的 统计 特征。

二、随机数的实现

1. rand()

生成伪随机数的算法，较慢。需要 #include <cstdlib>。

调用 rand() 函数会返回一个 [0, RAND_MAX] 中的随机 非负整数，其中 RAND_MAX 是标准库中的一个宏，在 Linux 系统下 RAND_MAX 等于 2^{31} - 1。可以用 取模 来限制所生成的数的大小。

使用 rand() 需要一个随机数 种子，可以使用 srand(seed) 函数来将随机种子更改为 seed，当然不初始化也是可以的。

同一程序使用 相同的 seed 两次运行，在同一机器、同一编译器下，随机出的结果将会是 相同 的。

有一个选择是使用 当前系统时间 来作为随机种子：srand(time(0))。

2. mt19937

是一个随机数生成器类，效用同 rand()，随机数的范围同 unsigned int 类型的取值范围。需要 #include<random>。

优点：

随机数 质量高（一个表现为，出现循环的周期更长；其他方面也都至少不逊于 rand()），且 速度比 rand() 快 很多。

使用方法：

std::mt19937 myrand(seed)，seed 可不填，不填 seed 则会使用默认随机种子。

mt19937 重载了 operator ()，需要生成随机数时调用 myrand() 即可返回一个随机数。

代码示例：

#include <ctime>
#include <iostream>
#include <random>

using namespace std;

int main() {
    mt19937 myrand(time(0));
    cout << myrand() << '\n';
    return 0;
}

3. random_device（生成真随机数）

random_device 是一个基于 硬件 的均匀分布随机数生成器，在熵池耗尽前 可以高速生成随机数。该类在 C++11 定义，需要 #include <random>。

由于熵池耗尽后性能急剧下降，所以建议用此方法生成 mt19937 等伪随机数的 种子，而不是直接生成。

4. 规定随机数分布的范围与概率

不明觉厉

类名 分布概率 数据类型
uniform_int_distribution 等概率分布 整数
uniform_real_distribution 等概率分布 实数
bernoulli_distribution 伯努利分布 布尔
binomial_distribution 二项分布 整数
negative_binomial_distribution 负二项分布 整数
geometric_distribution 几何分布 整数
poisson_distribution 泊松分布 整数
exponential_distribution 指数分布 实数
gamma_distribution \gamma 分布 实数
weibull_distribution 威布尔分布 实数
extreme_value_distribution 极值分布 实数
normal_distribution 标准正态（高斯）分布 实数
lognormal_distribution 对数正态分布 实数
chi_squared_distribution \chi^2 分布 实数
cauchy_distribution 柯西分布 实数
fisher_f_distribution 费舍尔 F 分布 实数
student_t_distribution 学生 t 分布 实数
discrete_distribution 离散分布 整数
piecewise_constant_distribution 分布在常子区间上 实数
piecewise_linear_distribution 分布在定义的子区间上 实数

5. 代码

生成 [l, r] 范围内的 n 个随机整 / 实数：

#include <cstdio>
#include <random>
using namespace std;
typedef double db;

random_device R; //定义生成种子的类
mt19937 gen(R()); //定义生成随机数的类

inline int dgrand(int l, int r) {
    uniform_int_distribution<> dis(l,r); //生成随机整数的范围
    return dis(gen);
}

inline db dbrand(db l, db r) {
    uniform_real_distribution<> dis(l,r); //生成随机实数的范围
    return dis(gen);
}

int main() {

    int n;
    db l, r;
    scanf("%d%lf%lf", &n, &l, &r);
    for (int i = 1; i <= n; i++) {
        printf("%d%c", dgrand(l, r), "\n "[(bool)(i % 10)]); //l和r自动向下取整了
    }
    putchar('\n');
    for (int i = 1; i <= n; i++) {
        printf("%.6lf%c", dbrand(l, r), "\n "[(bool)(i % 10)]);
    }

    return 0;
}