本文共 876 字，大约阅读时间需要 2 分钟。

遍历n个元素取出等概率随机取出其中之一元素

问题描述

1．一个文件中含有n个元素，只能遍历一遍，要求等概率随机取出其中之一。

选取策略：

•  顺序遍历，当前遍历的元素为第L个元素，变量e表示之前选取了的某一个元素，此时生成一个随机数r，如果r%L == 0(当然0也可以是0~L-1中的任何一个，概率都是一样的), 我们将e的值替换为当前值，否则扫描下一个元素直到文件结束。

证明

•      在遍历到第1个元素的时候，即L为1，那么r%L必然为0，所以e为第一个元素，p=100%，
•     遍历到第2个元素时，L为2，r%L==0的概率为1/2, 这个时候，第1个元素不被替换的概率为1X(1-1/2)=1/2,
•      第1个元素被替换，也就是第2个元素被选中的概率为1/2 = 1/2,你可以看到，只有2时，这两个元素是等概率的机会被选中的。
•     继续，遍历到第3个元素的时候，r%L==0的概率为1/3，前面被选中的元素不被替换的概率为1/2 X (1-1/3)=1/3,前面被选中的元素被替换的概率，即第3个元素被选中的概率为1/3
•     归纳法证明，这样走到第L个元素时，这L个元素中任一被选中的概率都是1/L，那么走到L+1时，第L+1个元素选中的概率为1/(L+1), 之前选中的元素不被替换，即继续被选中的概率为1/L X ( 1-1/(L+1) ) = 1/(L+1)。证毕。

//一个文件中含有n个元素，只能遍历一遍，要求等概率随机取出其中之一。#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;    #define N 1000void main()   {  	srand((unsigned)time(NULL));	int file[N];	iota(file,file+N,1);	int picked=file[0];	for(int length=1;length
       
      
     
    
   

转载地址：http://vbvvi.baihongyu.com/