随机化吼啊!
2021/5/17 18:25:25
本文主要是介绍随机化吼啊!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
学习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}\) 。由此我们得证。
这篇关于随机化吼啊!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求