 |
KnuthV2EX 第 488565 号会员，加入于 2020-05-09 16:20:14 +08:00今日活跃度排名 15439 |
Knuth 最近回复了
3 天前 回复了 shenzhuoyan 创建的主题 › MacBook Air › MacBook Air M2 16+256G 现在 6500 多 |
我手机都 256g 了
5 天前 回复了 GeekGuru 创建的主题 › iPhone › 纠结 16 Pro 还是 16 Pro Max |
13 打算换 pro 了，max 太大了，还是喜欢小点的
6 天前 回复了 revival83 创建的主题 › iPhone › 求个 iPhone 上好用的计算器，最好可以买断，不要订阅的 |
solves/kalkyl
17 天前 回复了 sleepybear1113 创建的主题 › macOS › 来说说 Mac 比起 Windows 笔记本好在哪里 |
续航
27 天前 回复了 sevenyangcc 创建的主题 › Apple › 你用得最久的 apple 设备是什么，用了多久？ |
ipad air3 快 5 年了
28 天前 回复了 abc0def 创建的主题 › 程序员 › 从 n 个数里面随机取 m 个数 |
@leonshaw 概率分布和次序无关，只是用数学归纳法证明等概率，至于 m 你看原贴内容
28 天前 回复了 abc0def 创建的主题 › 程序员 › 从 n 个数里面随机取 m 个数 |
@Knuth 这个算法是 knuth 大佬提出的（
28 天前 回复了 abc0def 创建的主题 › 程序员 › 从 n 个数里面随机取 m 个数 |
很经典的面试题，很经典的算法
附上代码
#include <cstddef>
#include <cstdlib>
#include <iostream>
// 等概率无重复的从 N 个数挑出 M 个数, 输出范围是 0~N-1 ，M < N
using namespace std;
// 1. 无重复 m 个值：i 不同保证无重复，m--控制个数
// 2. 等概率：
// i = 0 时，输出 i 只需 rand() % (n - i) < m,概率=m/n
// i = 1 时，输出 i 有两种情况，0 输出还是没输出，0 输出：m-1/n-1, 0 没输出：m/n-1,综合两者可得(m/n)*(m-1/n-1) + (1-m/n)*(m/n-1)=m/n
void genknuth(int m, int n) {
for (int i = 0; i < n; i++) {
if (rand() % (n - i) < m) {
cout << i << endl;
m--;
}
}
}
int main() {
int m = 8, n = 100;
genknuth(m, n);
return 0;
}
附上代码
#include <cstddef>
#include <cstdlib>
#include <iostream>
// 等概率无重复的从 N 个数挑出 M 个数, 输出范围是 0~N-1 ，M < N
using namespace std;
// 1. 无重复 m 个值：i 不同保证无重复，m--控制个数
// 2. 等概率：
// i = 0 时，输出 i 只需 rand() % (n - i) < m,概率=m/n
// i = 1 时，输出 i 有两种情况，0 输出还是没输出，0 输出：m-1/n-1, 0 没输出：m/n-1,综合两者可得(m/n)*(m-1/n-1) + (1-m/n)*(m/n-1)=m/n
void genknuth(int m, int n) {
for (int i = 0; i < n; i++) {
if (rand() % (n - i) < m) {
cout << i << endl;
m--;
}
}
}
int main() {
int m = 8, n = 100;
genknuth(m, n);
return 0;
}
28 天前 回复了 Knuth 创建的主题 › iPhone › iPhone 16 全系列 8g 内存 |
最恶心的还是 pro 的电池是全系列最差，又不想买 max ，cook sb
31 天前 回复了 SetoKaiba 创建的主题 › Apple › 苹果外区账号登录不了了，会提示验证码无法发送至该电话号码，请稍后再试。你们有遇到吗？ |
我也遇到这个问题，有个台湾的 Apple ID 之前为了下载去雀魂申请注册的、绑定的 Google voice 、现在收不到验证码
Select Language