|
Q：一个很长的数据流，这个数据流中有R个逗号，那么要等概率的获取一个逗号的偏移量，即获取一个逗号偏移量的概率为1/R。该如何做？ A：遇到第一个逗号，以概率1取其偏移量；遇到第二个逗号，以概率1/2替换已选择的偏移量；遇到第三个逗号时，以概率1/3替换已选择的偏移量。。。依次类推到R个逗号时，以概率1/R替换已选择的偏移量。 简单证明： 设遇到第n个逗号时，替换已选择偏移量的概率为1/n，那么当数据流全部读取结束之后，仍然选择第n个逗号的概率的算法是： 不管前n-1个逗号的选择情况，第n个逗号一定替换，n+1到R一定不替换，即 1/n * (1 - 1/(n+1)) * (1 - 1/(n+2)) * (1 - 1/(n+3)) * (1 - 1/(n+R)) ，化简后为1/R。因此，每个逗号是等概率被选择的。 |
|
|
