如何正确使用WebGrid# Programming - 葵花宝典
a*n
1 楼
面试考得随机算法
from我的blog, http://www.cnblogs.com/asuran/
1. 要求从N个元素中随机的抽取1个元素。
2. 要求从N个元素中随机的抽取K个元素。
int remain = N
int select = K
for (int i = 0; i < N; ++i){
if (rand()% remain < select){
cout<--select;
}
--remain;
}
第一个元素被选中的概率为 K/N
第二个元素被选中的概率为(K/N)*((K-1)/(N-1)) + ((N-K)/N) * (K/(N-1)) = K/N
.........
证明略（参看The Art of Computer Programming III）
3. 要求从N个元素中随机的抽取1个元素, 其中N无法确定(数据流)。
int Num;
int i = 0;
int choose = 0;
while(scanf("%d", &Num)&& Num != 0){
if (((double
from我的blog, http://www.cnblogs.com/asuran/
1. 要求从N个元素中随机的抽取1个元素。
2. 要求从N个元素中随机的抽取K个元素。
int remain = N
int select = K
for (int i = 0; i < N; ++i){
if (rand()% remain < select){
cout<--select;
}
--remain;
}
第一个元素被选中的概率为 K/N
第二个元素被选中的概率为(K/N)*((K-1)/(N-1)) + ((N-K)/N) * (K/(N-1)) = K/N
.........
证明略（参看The Art of Computer Programming III）
3. 要求从N个元素中随机的抽取1个元素, 其中N无法确定(数据流)。
int Num;
int i = 0;
int choose = 0;
while(scanf("%d", &Num)&& Num != 0){
if (((double
