随机化吼啊!
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-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?