[Investor Relations]  |  官方微博

C/C++培训

美国上市公司 · 亿元级外企Java培训企业

  • 全国服务监督电话400-827-0010
C++培训 > 学习笔记 > C语言中蓄水池抽样
  • C语言中蓄水池抽样

    发布:达内  来源:达内  时间: 2015年01月14日

  • 问题起源于编程珠玑Column 12中的题目10,其描述如下:...

  • 问题起源于编程珠玑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++培训:利用C++对象确定性析构的原则来解析单例模式

    下一篇:C++实例海明距离

网站导航
2001-2016 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56