一、摘要
随机数可以应用在很多场景下如游戏抽卡、抽奖、场景生成、洗牌，歌曲app中的随机播放，社交app中的匹配等以及随机化算法。
以下是针对C中随机函数rand、C++random库使用的总结，以及一些随机应用例子
二、C/C++ 中的rand 函数
使用时需要引入头文件
该函数返回一个在[0, RAND_MAX]范围内的数字，RAND_MAX该宏定义值取决于实现，至少为32767
使用rand()需要一个随机种子，可以使用srand(seed)来设置随机种子(这里的seed一般选择当前系统时间time(0))，当程序没有调用srand，会默认使用srand(1)来作为随机种子
rand函数使用到的随机数生成算法--线性同余方法
\[N_{j+1} = (A \quad *\quad N_j + B) (mod \quad M)
\]
可以看到当前的随机数，是根据上次随机数进行计算得到。因此同一程序使用相同的seed俩次运行，同一机器和编译器下，随机结果会是相同的。这样可以在程序应用中获得可再现的随机过程。
rand和srand伪代码实现，glibc rand源码实现
unsigned long _Randseed = 1; //默认随机种子为1
int rand(void) {
_Randseed = _Randseed * 1103515245 + 12345;
return ((unsigned int)(_Randseed >> 16) & RAND_MAX);
}
void srand(unsigned int seed) {
_Randseed = seed;
}
需要注意的是rand函数不是线程安全的，多个线程同时调用rand可能获得同样的结果：多线程rand获得一样结果原因
使用比较简单
#include
#include
int main(int argc, char**argv)
{
srand(time(nullptr));
//如果在应用程序中需要一个可重复的随机过程
//使用固定的seed作为srand参数
std::cout << "randmax: " << RAND_MAX << std::endl;
for(int i = 0; i < 10; i++)
{
std::cout << " " << rand();
}
std::cout << std::endl;
return 0;
}
三、C++random库
random库主要由随机数引擎(Random number engines)和随机数分布(Random number distributions)组成，使用时需要引入头文件 #include
使用随机数引擎生成一定范围内随机数，使用随机分布可以得到满足一定规律的分布（均匀分布，伯努利分布、泊松分布、正太分布、抽样分布）的随机数
3.1 随机数引擎
3.1.1 模板类
模板
作用
linear_congruential_engine
实现线性同余算法 速度适中
mersenne_twister_engine
实现 Mersenne twister算法 速度较慢, 具有最长非重复序列
subtract_with_carry_engint
实现滞后斐波那契算法, 速度最快
3.1.2 非确定性随机数
std::random_device 是一个非确定性随机数生成器。通常被用作生成伪随机数器的种子。
3.1.3 一些预定义的随机数引擎
minstd_rand0 / minstd_rand（C++11）//线性同余法生成随机数
#include
#include
//std::minstd_rand0
//定义：std：：linear_congruential_engine
int main(int argc, char**argv)
{
std::random_device rd;
unsigned int seed = rd();
std::minstd_rand0 gen(seed);
for(int i = 0; i < 10; i++)
{
std::cout << " " << gen();
}
return 0;
}
mt19937 (32位)/ mt19937_64 （64 位）使用Mersenne twister算法生成随机数，随机效果最好
#include
#include
//std::mt19937
/*定义
std::mersenne_twister_engine 0x9908b0df,11, 0xffffffff,7, 0x9d2c5680,15, 0xefc60000,18,1812433253> */ int main(int argc, char**argv) { std::random_device rd; unsigned int seed = rd(); std::mt19937 mt_r(seed); for(int i = 0; i < 10; i++) { std::cout << " " << mt_r(); } return 0; } ranlux24_base/ranlux48_base 使用滞后斐波那契算法，与其他比较速度最快 #include #include //std::ranlux24_base //std::subtract_with_carry_engine int main(int argc, char**argv) { std::random_device rd; unsigned int seed = rd(); std::ranlux24_base r(seed); for(int i = 0; i < 10; i++) { std::cout << " " << r(); } return 0; } 3.2 随机数分布 3.2.1 均匀分布 在闭区间[a, b]中返回一个整数i，i的概率为 \[P(i|a,b) = \frac{1}{(b-a)+1} \] 使用方式 #include #include int main() { std::random_device rd;//非确定性随机数生成器 std::mt19937 gen(rd()); //使用Mersenne twister算法随机数生成器 std::uniform_int_distribution<> distrib(1, 6); //随机均匀分布[1,6]区间 //随机在闭区间[1,6]中返回一个数 for (int n = 0; n != 10; ++n) std::cout << distrib(gen) << ' '; std::cout << '\n'; } 3.2.1 伯努利分布(0-1分布) \[p(b/p)= \left\{\begin{matrix} p, if \quad b \quad is \quad true \\ 1-p, if \quad b \quad is \quad false \end{matrix}\right. \] 使用 #include #include #include #include #include int main() { std::random_device rd; std::mt19937 gen(rd()); std::bernoulli_distribution d(0.25); //默认参数为0.5，返回true的概率 std::map for (int n = 0; n < 10000; ++n) ++hist[d(gen)]; std::cout << std::boolalpha; for (auto const& [key, value] : hist) std::cout << std::setw(5) << key << ' ' << std::string(value / 500, '*') << '\n'; } 还有泊松、正太、抽样方式随机分布，更多查看 四、随机数相关 4.1 洗牌算法 Knuth_Durstenfeld_Shuffle，就地洗牌 打乱一个数组num[n]， 从后向前遍历，当前位置i，从[0, i-1]中随机选择一个元素与num[i]交换 -- To shuffle an array a of n elements (indices 0..n-1): for i from n−1 down to 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i] Knuth_Durstenfeld_Shuffle 算法是通过交换原数组的元素来达到打乱效果，当不能修改原数组，需要返回洗牌后新数组，可以使用"inside-out" 算法 4.2 "inside-out" 洗牌算法，不修改原数组 从原数组source[n]返回打乱后数组a，从前往后遍历原数组，当前位置i，从[0,i-1]随机选值j， 当 \(j != i \quad a[i] =a[j]\) 然后将source[i]赋值给a[j] To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based: for i from 0 to n − 1 do j ← random integer such that 0 ≤ j ≤ i if j ≠ i a[i] ← a[j] a[j] ← source[i] 4.3 线段分割（红包随机、固定长度随机切割） 例子：生成 10 个随机数 （0, 100） 且最终 10 个随机数之和为 100（或者固定100面值随机10个红包） 线段分割：在一根1到100的数轴上，选取9个点，拿到10个线段，计算每个线段的长度 C++代码实现 #include #include #include #include #include int main(int argc, char *argv[]) { std::random_device device; std::mt19937 mt(device()); std::uniform_int_distribution<> dis(1, 100); std::set //需要进行去重，防止有重复的点。 while(random_val.size() < 9) { random_val.insert(dis(mt)); } random_val.insert(0); random_val.insert(100); auto last = random_val.begin(); std::vector for(auto cur = std::next(last); cur != random_val.end(); ++cur) { ret.push_back((*cur) - (*last)); last = cur; } int total = 0; for(auto num : ret) { std::cout << " " << num; total += num; } std::cout << std::endl; std::cout << "totalnum: " << total << std::endl; return 0; } //结果输出 // 24 11 38 2 1 1 4 8 2 9 //totalnum: 100 4.4 二倍均值法（提到红包随机，网上还提及这个算法） 每次在区间\([0.01,M/N*2-0.01]\)随机选取一个数，M是剩余红包金额，N红包剩余数量。 六、参考 https://rgb-24bit.github.io/blog/2019/rand-misc.html https://en.cppreference.com/w/c/numeric/random/rand https://oi-wiki.org/misc/rand-technique/ https://en.cppreference.com/w/cpp/numeric/random https://www.cnblogs.com/Critical-Thinking/p/16845446.html https://www.zhihu.com/question/22625187