学习luogu日报有感暨随笔。
众所周知啊,怎么生成随机数呢? \(srand(time(0))\) ,然后 \(rand\)。但这个有局限,生成的数并不会很大,并且有时候会很集中,不利于对拍。
于是,C++中有另一种随机数生成函数:mt19937
。
具体使用方法:
#include<bits/stdc++.h> using namespace std; std::mt19937 engine(30); int cnt[2000]; int main() { std::uniform_int_distribution<int> dist(3, 9);//dist(x,y) 在 x 到 y 之间产生随机数 for(int i=0;i<100000;i++) { cnt[dist(engine)]++; } for(int i=3;i<10;i++) cout << i << ": " << cnt[i] << endl; }
真得很均匀,可以尝试。
洗牌问题。
如何将一个长度为 \(n\) 的 \(1-n\) 的排列纯随机打乱呢。
for (int i = n - 1; i; --i) std::swap(arr[i], arr[rand(0, i)]);
为什么呢?
考虑数学归纳法证明,当 \(i=1\) 时显然成立。然后上面的实现可以写成以下形式
void shuffle(int len) { if (len == 1) return; std::swap(arr[len - 1], arr[rand(0, len - 1)]); shuffle(len - 1); }
因为然后我们现在假设这个算法能对长度为 \(n\) 的数组均匀随机打乱,我们要证明它能对长度为 \(n+1\) 的数组均匀随机打乱。首先我们注意到数组被均匀随机打乱,当且仅当每个数出现在每个位置的概率均为 \(\frac 1 n\),这很显然。然后我们注意到 \(n+1\)号元素有 \(\frac 1 {n+1}\)的概率会留在原地,有 \(\frac n {n+1}\)的概率会跑到前面的数组去。因为我们已知前面的数组被均匀随机打乱,所以它跑到前面 \(n\)个元素的概率均为 \(\frac n {n+1} \frac 1 n =\frac 1 {n+1}\) 。由此我们得证。