C/C++培训
达内IT学院
400-111-8989
C/C++培训
C语言中蓄水池抽样
- 发布：达内
- 来源：达内
- 时间：2015-01-14 10:43
- 分享到：
问题起源于编程珠玑Column 12中的题目10，其描述如下：
How could you select one of n objects at random, where you see the objects sequentially but you do not know the value of n beforehand? For concreteness, how would you read a text file, and select and print one random line, when you don’t know the number of lines in advance?
(1)在不知道文件总行数n的情况下，如何从文件中随机的抽取一行?
解：先选择第一个行，并使用1/2的概率选择第二个行，使用1/3的概率选择第三行，使用1/i的概率选择第i行，以此类推。在过程结束时，每个对像被选中的概率都是1/n。
用P(i)表示处于第i行时第i行被选中的概率。
P(1)=1
P(2)=1/2
P(3)=1/3
则选择第3行的时候，对于第1行来讲选中的概率=第一行被选中概率*第二行没被选中*第3行没被选中概率。
p(1)all=P(1)*(1-P(2))(1-P(3))=1/3
p(2)all=P(2)*(1-P(3))=1/3
p(3)all=P(3)=1/3
证明：
1最终被选中的概率：1被选中的概率*2没有被选中的概率*3没有被选中的概率*…*n没有被选中的概率
p(1)all=1*(1-1/2)(1-1/3)*…*(1-1/n)=1/n
m最终被选中的概率：m被选中的概率*m+1没有被选中的概率*m+2没有被选中的概率*…*n没有被选中的概率(1<=m
p(m)all=1/m*[1-1/(m+1)][1-1/(m+2)]*…*[1-1/n]=1/n
(2)对其进行扩展，即如何从未知或者很大样本空间随机地取k个数?
给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的(出现概率均等)。
解：先选中前k个， 从第k+1个元素到最后一个元素为止， 以k/i (i=k+1, k+2,...,N) 的概率选中第i个元素，并且随机替换掉一个原先选中的元素， 这样遍历一次得到k个元素， 可以保证完全随机选取。
证明：
n最终被选中的概率： n被选中的概率*[(n+1)没有被选中的概率+(n+1)被选中概率*n没被替换的概率]
p(n)all=k/n*[(1-k/(n+1))+k/(n+1)*(1-1/k)]=k/(n+1)
预约申请免费试听课
填写下面表单即可预约申请免费试听！怕钱不够？可就业挣钱后再付学费！ 怕学不会？助教全程陪读，随时解惑！担心就业？一地学习，可全国推荐就业！
下一篇：C＋＋实例海明距离
-
扫码领取资料
回复关键字：视频资料
免费领取 达内课程视频学习资料
-
搜索抖音号搜索抖音号：1821685962
免费领取达内课程视频学习资料
Copyright © Tedu.cn All Rights Reserved 京ICP备08000853号-56 
京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有
选择城市和中心
北京
黑龙江省
吉林省
内蒙古
河北省
陕西省
江苏省
湖北省
四川省
重庆
湖南省
江西省
贵州省
云南省
广西省
海南省
台湾