请教一道题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道题目

请教一道题目# JobHunting - 待字闺中

c*o2010-01-05 08:01

1 楼

在glassdoor上看到一道题目：
Given a file of unknown size, devise an algorithm to give equal probability
randomization to choosing a single line given a one line buffer space.
请教思路？

r*u2010-01-05 08:01

2 楼

这个刚有人总结过，我copy&paste。
要求从N个元素中随机的抽取1个元素, 其中N无法确定(数据流)。
int Num;
int i = 0;
int choose = 0;
while(scanf("%d", &Num)&& Num != 0){
if (((double)rand()/(double)RANDOM_MAX) < (1.0 / (double)++i))
choose = Num;
}
cout << choose <总是选择第一行，二分之一几率选择第二行，以此类推， K分之一机率选择第K行，
当while 执行完毕，假设N个数字，则每个数字被选择的机率均为1/N
第一行被选择的机率为:
1 * 1/2 * 2/3 * 3/4 *.... (N-1)/N = 1/N
第K行被选择的机率为：
1/K * K/(K+1) * .... (N-1)/N = 1/N

probability

【在 c*****o 的大作中提到】

: 在glassdoor上看到一道题目：
: Given a file of unknown size, devise an algorithm to give equal probability
: randomization to choosing a single line given a one line buffer space.
: 请教思路？