MS 面试题 随机取值

一个不知道有多少条目的文件 每个条目一行 类似下面的结构
sdfgdfsgdfsgf
ertyrteyrtye
ytuityuityuityui
etrwtwetewtwt
.....
要求从头到尾只遍历一遍，等概率取其中100个条目，可以用rand()等系统函数时侯
和不能用任何系统调用时都怎么做？

 

 

 

假设文件的行数n大于100行（其实是废话，小于100行就没意义了）
预先申请一个string str[100],将前100行的记录都存取进去。
然后从第101行开始，假设当前是第K行，令m=rand() % k,如果m<100,就将str[m]的值修改为当前行内容，否则继续。最后str里面的内容就是取出的100个条目。
 
现在需要证明这种算法下，第k行被选中的概率为100/n。
A k>100的情况，第一次被选入到str中的概率为100/k,第2次没有被剔除来的概率为k/k+1,第三次为k+1/k+2,最后一次为n-1/n，则最后的概率为
(100/k) * (k/k+1) * (k+1/k+2) *.....*(n-2/n-1) * (n-1/n) = 100/n
 
B k<100,则从第101行开始，第一次不被剔除的概率是100/101,第二次101/102,最后一次n-1/n,则最后被选中的概率为
(100/101) * (101/102) * .........* (n-2/n-1) * (n-1/n) = 100/n
 
感觉这样是可以保证每一行被选中的概率是100/n，这个结论可以推广为n行选择m个条目