概率相关问题

vergilwang

浏览: 124798 次
性别:
来自: 北京

最近访客更多访客>>

iris19860111

u_lama

KEYS123456789

2644781824

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Probabilistic
Algorithm

1、一个随机数产生器以概率p生成0，以概率(1-p)生成1，怎样生成等概率的0和1？

如果用这个随机数产生器产生两个位，出现00的概率为，出现01的概率为 $p(1-p)$ ，出现10的概率为 $(1-p)p$ ，出现11的概率为。看到没有，出现01和10的概率相等。那么我们就可以用这个随机数生成器每次产生2位，直到产生的是01或者10，当为01时，输出0，当为10时输出1。

问题扩展：还是给这么一个随机数产生器，要求等概率地产生 $1,2,/cdots,n$ 。

解法1：每次产生n位，当为仅第一位是1，其他是0时输出1，当仅有第二位是1，其他位是0是输出2，……当仅有第n位是1，其他是0时输出n。（这个解法有点0疼，好多信息都浪费了，复杂度太高了）

解法2：从原问题的解答中，我们可以成功地得到等概率产生0和1的，求一下n-1二进制表示的位数，比如为k。那么我们每次等概率生成k位二进制数，将这k位二进制组装成一个数，如果这个数在0~n-1的范围内，输入这个数+1，否则重复产生。

2、不重复随机数的产生

我们可以把这题稍微细化一点，随机产生0~n-1中的k个不重复的随机数。

解法1：最容易想到的方法就是，用一个集合来装这些随机产生的数，当这个集合的大小不为k的时候，就没完没了的随机产生并add到集合中。真正这么干过的童鞋会发现这个办法是不行的，当k稍微大一点，这个程序就跑步出来了。

解法2：开辟一个长度为n的数组a，向其中装入0~n-1，然后随机产生一个0~n-1的数x，将a[x]与a[n-1]交换，并将a[n-1]输出，接下来随机产生一个0~n-2的数y，将a[y]与a[n-2]交换，并将a[n-2]输出，知道输出了k个数为止……代码实现参考这里。

3、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数

解法1：

产生K个数(k>1) 假定产生的数分别为n1,n2,n3,n4...那么定义产生的数为n1-1+（n2-2）*5+（n3-1）*5^2+（n4-1）*5^3........于是产生的数位于区间（0，5^k-1)。然后把5^k分成k等分，产生的数位于哪个等分就是那个产生的随机数（0~6），然后+1即可。如果位于k等分的余数范围，则重新执行一次上述过程。不用担心余数问题，当k取3时落到余数范围的概率就已经降低为6/125，而且余数不会导致概率的问题，只是会影响效率。（相当于5进制）

解法2：

通过rand5()*5+rand5()产生6 7 8 9 10 11......26 27 28 29 30这25个数，每个数出现的概率相等，去前面3*7个数，舍弃后面的4个数，将6 7 8转化成1， 9 10 11转化成2，……，公式：(a-3) / 3，其实跟解法1是一样的，包装一下而已。

4、如何随机选取1000个关键字

给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

定义长度为1000的数组。对于数据流中的前1000个关键字，显然都要放到数组中。对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

PS：关于1000/n的概率问题，可以这样来，随机生成1~n的数，如果是在1~1000内那么就替换相应位置

5、在半径为1的圆中随机选取一点

解法1：

假设圆心在(0,0)。在x轴[-1, 1]，y轴[-1, 1]的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。正方形的面积为4，圆的面积为pi，所以正方形内的随机点在圆内的概率是 pi / 4。

解法2：

从[0, 2*pi)中随机选一个角度，对应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的长度成正比，这样才能保证随机点在圆内是均匀分布的。

关于不均匀选取问题：在一个直角三角形（斜边长pi，直角边长为1）斜边上随机选一点，然后投影到长为1的直角边应该满足条件。

原文见此：http://www.smallqiao.com/wp-content/plugins//down-as-pdf/generate.php?id=96002

给定一个函数rand5()，使函数rand7()可以随机等概率的生成1-7的整数

题目：

给定一个函数rand5()，该函数可以随机生成1-5的整数，且生成概率一样。现要求使用该函数构造函数rand7()，使函数rand7()可以随机等概率的生成1-7的整数。

思路：

很多人的第一反应是利用rand5() + rand()%3来实现rand7()函数，这个方法确实可以产生1-7之间的随机数，但是仔细想想可以发现数字生成的概率是不相等的。rand()%3 产生0的概率是1/5，而产生1和2的概率都是2/5，所以这个方法产生6和7的概率大于产生5的概率。

正确的方法是利用rand5()函数生成1-25之间的数字，然后将其中的1-21映射成1-7，丢弃22-25。例如生成(1，1)，(1，2)，(1，3)，则看成rand7()中的1，如果出现剩下的4种，则丢弃重新生成。

简单实现：

Java代码

public class Test {
public int rand7() {
int x = 22;
while(x > 21) {
x = rand5() + (rand5() - 1)*5;
}
return 1 + x%7;
}
}

我的备注：

这种思想是基于，rand()产生[0,N-1]，把rand()视为N进制的一位数产生器，那么可以使用rand()*N+rand()来产生2位的N进制数，以此类推，可以产生3位，4位，5位...的N进制数。这种按构造N进制数的方式生成的随机数，必定能保证随机，而相反，借助其他方式来使用rand()产生随机数(如 rand5() + rand()%3 )都是不能保证概率平均的。

此题中N为5，因此可以使用rand5()*5+rand5()来产生2位的5进制数，范围就是1到25。再去掉22-25，剩余的除3，以此作为rand7()的产生器.

给定一个函数rand()能产生0到n-1之间的等概率随机数，问如何产生0到m-1之间等概率的随机数？

int random(int m,int n){
int k=rand();
int max=n-1;
while(k<m){
k=k*n+rand();
max=max*n+n-1;
}
return k/(max/n);
}

如何产生如下概率的随机数？0出1次，1出现2次，2出现3次，n-1出现n次？

int random(int size){
while(true){
int m=rand(size);
int n=rand(size);
if(m+n<size)
return m+n;
}
}

http://hi.baidu.com/hins_pan/item/e4e91f4b1cbc37a8de2a9f6e

出处：http://blog.csdn.net/slowgrace/archive/2009/03/25/4022632.aspx

1、生成随机数的方法

FunctionSetEmpId()AsString
DimrefAsString
Randomize
ref=Int((99999-10000)*Rnd+10000)
SetEmpId=ref
EndFunction

This function’s purpose is to assign a unique five-digit number to each new employee. To generate a random integer between two given integers where ending_number = 99999 and beginning_number = 10000, the following formula is used:

=Int((ending_number - beginning_number) * Rnd + beginning_number)

2、按概率生成随机整数

以下参考：http://topic.csdn.net/t/20051018/10/4333135.html

如果要随机生成5个数,并控制它们出现的概率.

数字概率
1 10%
2 10%
3 10%
4 20%
5 50%

那就生成0-1的随机数
0 -- 0.1 1
0.1 -- 0.2 2
0.2 -- 0.3 3
0.3 -- 0.5 4
0.5 -- 1.0 5

3、按概率生成随机浮点数

以下来自和Tiger_Zhao的讨论。

如果要控制1个数落在某个区间的概率，比如要求在sngBegin和sngEnd之间生成一个随机数，这个随机数落在sngPB和sngPE之间的概率是P%。有两种方法，以第二种方法为好。

先说第一种方法，要点是：

（1）由于sngPB和sngPE将整个区间分成3部分，所以先分别计算随机数落在3部分的概率。落在sngPB和sngPE之间的概率是P%，这是已知的。余下的两个区间的总和概率是(1-p%),分到各个区间的概率按它们的长度分成。

（2）然后根据3个概率得到一个区间划分，落在第一个区间的，就在sngPB和sngPE之间生成一个随机数；落在第二个区间的，就是[sngBegin, sngPB]里生成随机数；落在第3个区间的，就在[sngPE,sngEnd]之间生数。

'create a random number between sngBegin and sngEnd
'with a probability of bytP to lie within sngPB and sngPE
PublicFunctionGetRndNumP(sngBeginAsSingle,sngEndAsSingle,sngPBAsSingle,sngPEAsSingle,bytPAsByte)AsSingle
DimbytP1AsByte,bytP2AsByte

Debug.Assert(sngPB>=sngBegin)And(sngPE>=sngPB)And(sngEnd>=sngPE)

'计算其他区间的概率
bytP1=((sngPB-sngBegin)/((sngEnd-sngBegin)-(sngPE-sngPB)))*(100-bytP)'[sngBegin, sngPB]
bytP2=100-bytP-bytP1'[sngPE, sngEnd]

'依据概率投射到相应区间
SelectCaseGetRandomNum(1,100)
Case1TobytP
GetRndNumP=GetRandomNum(sngPB,sngPE)
Case(bytP+1)To(bytP+bytP1)
GetRndNumP=GetRandomNum(sngBegin,sngPB)
Case(bytP+bytP1)+1To100
GetRndNumP=GetRandomNum(sngPE,sngEnd)
EndSelect
EndFunction

PublicFunctionGetRandomNum(sngBeginAsSingle,sngEndAsSingle)AsSingle
Randomize
GetRandomNum=(sngEnd-sngBegin)*Rnd+sngBegin
EndFunction

这个办法有个问题，就是用了两次随机数，这样实际上影响了它的随机性。Tiger_Zhao建议的第二种方法则没有这个问题，做法是：多个段有不同权重时其实可以映射成相同权重（缩放 [sngPB, sngPE] 区间，相对调整 sngEnd），这样只要一次 Rnd() 就可以完成，代码如下。

'create a random number between sngBegin and sngEnd
'with a probability of bytP to lie within sngPB and sngPE
PublicFunctionGetRndNumP(sngBeginAsSingle,sngEndAsSingle,sngPBAsSingle,sngPEAsSingle,bytPAsByte)AsSingle
DimsngPLenAsSingle
DimsngTLenAsSingle'total length
DimsngIncreasedAsSingle'需要缩放的长度
DimsngResultAsSingle

sngPLen=sngPE-sngPB
sngTLen=sngEnd-sngBegin

Debug.Assert(sngPB>=sngBegin)And(sngPE>=sngPB)And(sngEnd>=sngPE)
Debug.Assert(bytP<100)And(bytP>0)
Debug.AssertsngTLen<>sngPLen

'映射原来的区间为等权重区间
If(sngPLen/sngTLen)*100=bytPThen
GetRndNumP=GetRandomNum(sngBegin,sngEnd)
ExitFunction
EndIf

'((sngPLen + sngIncreased) / (sngTLen + sngIncreased)) * 100 = bytP
sngIncreased=((bytP/100)*sngTLen-sngPLen)/(1-(bytP/100))

'缩放回原来区间
sngResult=GetRandomNum(sngBegin,sngEnd+sngIncreased)
SelectCasesngResult
CasesngBeginTosngPB
GetRndNumP=sngResult
CasesngPBTo(sngPE+sngIncreased)'等比例缩放
GetRndNumP=sngPB+(sngResult-sngPB)*sngPLen/(sngPLen+sngIncreased)
Case(sngPE+sngIncreased)TosngEnd+sngIncreased'简单平移
GetRndNumP=sngResult-sngIncreased
EndSelect
EndFunction

另，yesvery说，VB产生的是伪随机数，不是真正的随机数。所以，不能完全满足正态分布。

给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数

问题：

给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

解答：

假设我们要等概率生成一个3位的10进制数(000 - 999)，我们可以在随机生成整数0到9的函数基础上，随机生成3个数字组成三位数就得到了结果。

这里类似，我们首先必须认识到：任何一个数都可以用5进制的数来表示，如12 = 5进制(22) = 2*5 + 2。因此假设我们要随机生成[0,444]范围的数，我们只要随机生成3个5进制的数字组合就可以。

这里的主要问题是：7不是5的幂次方。

但是我们可以将某一个5的幂次方均分成 7 段(分别为0 - 6，等概率的落到每一段)，利用5进制随机成一个数，看这个数在哪一个段，就代表我们要生成哪一个数字，这样就保证了等概率的生成0 - 6.

有一个小的问题就是：5的幂次方不能整除7，会遗漏最高的几个数。但是我们这里只要数字足够大，则遗漏的概率相当的小。

下面是简单的代码：

const int K = 10;//[0, 5^K - 1]
int Base[K],Rnd[K],Step; //Step表每个区间的长度
int Rand15() //已有的随机生成1 - 5的随机函数
{
return rand()%5 + 1;
}
void Init()
{
Base[0] = 1;
for(int i=1 ;i<K; ++i)
Base[i] = Base[i-1]*5;
Step = Base[K-1]*5/7;
//cout<<"Step = "<<Step<<"\tStep*7 = "<<Step*7<<endl;
srand(time(0));
}
int Rand17() //我们需要写的随机生成1 - 7的随机函数
{
int Sum = 0;
for(int i=0 ;i<K; ++i) //随机生成K个1到5的随机数
{
Rnd[i] = Rand15();
Sum += (Rnd[i]-1)*Base[i];
}
return Sum/Step + 1;
}

这里K = 10的时候，保证遗漏了2个数，即落到余数里面的概率是：2/9765625.

http://hi.baidu.com/nicker2010/item/38be6c4a9b7287a7de2a9f1d

假设rand5能随机生成1~5的5个数(均等概率)，利用rand5生成rand7() 1~7(均等概率)

1. 利用rand5求出rand2(),当rand5生成的数大于2时，一直循环，直到它生成的数为1或者2，且生成1和2的概率均为1/2，因为生成1和生成2的概率是相等的。

2. 利用rand2生成0和1（减1即可），连续使用三次，共有8种可能（二进制表示）：000 001 010 011 100 101 110 111，当生成的数为000时，重新计算，这样就可以得到1~7范围内的数，且概率是均等的。

[cpp]view plain copy print ?

#include <iostream>
#include <math.h>
usingnamespacestd;
intrand5()
{
returnrand()%5+1;
}
intrand2()
{
inttemp;
do
{
temp = rand5();
}while(temp > 2);
returntemp;
}
intrand7()
{
inttemp;
do
{
temp = (rand2()-1)<<2;
temp += (rand2()-1)<<1;
temp += rand2()-1;
}while(temp == 0);
returntemp;
}
intmain(int,char**)
{
intnum;
cout <<"输入总生成数:";
cin >> num;
intc1, c2, c3, c4, c5, c6, c7;
c1 = c2 = c3 = c4 = c5 = c6 = c7 = 0;
for(inti = 0; i < num; i++)
{
inttemp = rand7();
switch(temp)
{
case1:
c1++;
break;
case2:
c2++;
break;
case3:
c3++;
break;
case4:
c4++;
break;
case5:
c5++;
break;
case6:
c6++;
break;
case7:
c7++;
}
//cout << temp << "\t";
}
cout << endl;
cout <<"生成1的个数占总生成数的："<< (double)c1/num*100 <<"%"<< endl;
cout <<"生成2的个数占总生成数的："<< (double)c2/num*100 <<"%"<< endl;
cout <<"生成3的个数占总生成数的："<< (double)c3/num*100 <<"%"<< endl;
cout <<"生成4的个数占总生成数的："<< (double)c4/num*100 <<"%"<< endl;
cout <<"生成5的个数占总生成数的："<< (double)c5/num*100 <<"%"<< endl;
cout <<"生成6的个数占总生成数的："<< (double)c6/num*100 <<"%"<< endl;
cout <<"生成7的个数占总生成数的："<< (double)c7/num*100 <<"%"<< endl;
return0;
}

http://blog.csdn.net/peng_weida/article/details/7942682

4、利用等概率Rand5产生等概率Rand3

intRand3()
{
intx;
do
{
x=Rand5();
}while(x>=3);
returnx;
}

算法很简单，x是我们最终要输出的数字，只要它不在[0, 3)范围内，就不断地调用Rand5来更新它。直观地看，算法输出的数字只有0、1、2这三个，而且对任何一个都没有偏袒，那么显然每个数字的概率都是1/3，那让我们来严格地计算一下。

以输出0为例，看看概率是多少。x的第一个有效数值是通过Rand5得到的。Rand5返回0的概率是1/5，如果这事儿发生了，我们就得到了0，否则只有当Rand5返回3或4的时候，我们才有机会再次调用它来得到新的数据。第二次调用Rand5之后，又是有1/5的概率得到0，2/5的概率得到 3或4导致循环继续执行下去，如此反复。因此概率的计算公式为：

p=====15+25×(15+25×(15+25×(⋯)))15×∑∞i=0(25)i15×11−2515×5313

喏，计算表明，Rand3输出0的概率确实是1/3，对于另外两个数字也是一样的。

http://www.cnblogs.com/yysblog/archive/2012/06/27/2566276.html

调用RANDOM(0,1),实现RANDOM(a,b)的过程

问题：

描述RANDOM(a,b)的过程的一种实现，它只调用RANDOM(0,1)。作为a和b的函数，你的程序的期望运行时间是多少？
注：RANDOM(0,1)以等概率输出0或者1，
要求RANDOM(a,b)以等概率输出[a,b]之间的数(整数)

解决方案：

1，取 n=b-a+1，取最小的正整数m，使得 2^m >= n
2，调用RANDOM(0,1)，输出m-bit位整数N ( N >= 0 and N <= 2^m-1)
3， if N >=0 and N <= b-a
then return a+N
else 重新执行步骤 2

[a,b]之间每个数都是以 1/2^m 的概率输出的

渐进运行时间分析：

我觉得渐进时间分析应该用概率分析的方法，我觉得是服从几何分布：
假设进行一系列伯努利试验，每次成功的概率是p，失败的概率是q=1-p，在取得一次成功前一共要进行多少次试验？令随机变量X为取得一次成功所要进行的试验次数，则X的取值范围{1,2,......}。对k>=1，因为在一次成功前有k-1次失败，从而有
Pr[X=k]= q^(k-1)p
满足上式的分布称为几何分布[见算法导论 P686]
在算法中 p=(b-a+1)/2^m
期望运行次数(算法中生成m位序列的调用次数)为： E[X]=sum(k*q^(k-1)p) [k=1......+无穷]=1/p=2^m/(b-a+1)
用T表示调用一次RANDOM(0,1)所需要的时间，每次运行时间为输出m位bit的时间：O(log(b-a) × T)
期望运行时间：O（T × log(b-a) × 2^m/(b-a+1) ）=(约等于)O(T × log(b-a)) (因为m=(约等于)log(b-a+1))

http://blog.163.com/kevinlee_2010/blog/static/169820820201092533911883/

1、百度的一个面试题目:

.已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器， 使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；…， 构造一个发生器，使得它构造1、2、3、…n的概率均为1/n，要求复杂度最低。

初看确实有点头晕，也没什么思路。但是仔细想想为什么生成0和1的概率均为1/2，我们可以看成是生成0和1的概率是均等的。这样想之后，似乎就没那么不好理解了。

原始的随机数生成器，生成0 的概率为p,生成1的概率为1-p,那么怎么构造才能使得生成0和1的概率相等呢。或者说有两个独立的事件的概率是相等呢？

这样来做一下，让该随机数生成器生成两个数，那么序列是00,01,10,11概率分别为 p*p,p(1-p),(1-p)p,(1-p)*(1-p)

很明显，这四种情况中存在两个独立的事件概率是相等。也就是01和10，那么我把01看成是0,10看成是1，那么他们输出的概率均为p(1-p)，其他的情况舍弃。这样就得到了0和1均等生成的随机器了。

思维在扩展一下，生成1,2,…n的概率分别是1/n，也就是均等的。那么我们可以想怎么生成一个序列，里面有n个独立时间，概率是相等。而且我们能够猜测到这些概率的形式为 p^x*(1-p)^y,如果要相等，那么x必须等于y.这样就说明了序列中0和1的个数是相等的。而且这样的情况必须有多与n个才行。

数学表示就是 C(2x,x) >=n ，我们只需要知道x就能够知道序列要多长了。而且中间必定有超过n个概率为{p(1-p)}^x不相等序列。

问题就可以解决了。

其实卡我的问题是，丢掉那些多余的，只要n个等概率的序列，是否真的是等概率的（最终输出）。

2、腾讯面试题:

已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。

利用的方法和上个问题类似，如何能够得到一个等概率的独立事件。这个问题和上个问题不同的是，这里产生的序列，要变成和的形式或者其他的形式，那么概率就会发生变化了。

如果能够得到一组等概率的数，不管是什么数，只要等概率而且个数大于10，那么问题就可以解决了。

发现(rand7()-1)*7+rand7(),可以等概率的生成1到49。

呵呵，这不就得了，只要把11-49砍掉就可以了。不过这样的效率比较低。可以砍掉41-49，然后在把1-40映射到1-10，那么问题也就解决了。

3、腾讯面试题:

等概率采样数据流中的数字。

比如从数据流中等概率的采样k个数字。

怎么做呢？先拿到最开始的k个数字，然后以后的每个数字等概率的和这k个数字交换。那么就可以达到每个数字被抽取的概率是等概率的。

怎么证明呢？

采用归纳方法，假设前n个数字等概率的采样k个数字，那么每个数字被采样的概率为k/n,现在新来一个数字，变成了n+1个数字，那么每个数字被采样的概率变位k/(n+1),我们要证明这个

这个问题在计算机程序设计艺术书中提到，叫Reservoir Sampling（蓄水池采样），属于随机算法的一种。

现在假定存在了n个数字，来了第n+1个数字，那么第n+1个数字被选择的概率是k/n+1,那么我们推算其他的数字被选择的概率也是k/n+1

P(其余数字) = p(其余数字|第n+1个选择)*p(第n+1个选择) + p(其余数字|第n+1个不选择)*p(第n+1个不选择)

=k/n*(1-1/k)*k/(n+1) + k/n*(n+1-k)/(n+1)

= k*(k-1) / (n *(n+1) ) + k*(n+1-k) / (n*(n+1))

= k*n/(n *(n+1))

= k/(n+1)

得证。其余数字被选择的概率依然也是 k/(n+1)

4、调用RANDOM(0,1),实现RANDOM(a,b)的过程

问题：

描述RANDOM(a,b)的过程的一种实现，它只调用RANDOM(0,1)。作为a和b的函数，你的程序的期望运行时间是多少？
注：RANDOM(0,1)以等概率输出0或者1，
要求RANDOM(a,b)以等概率输出[a,b]之间的数(整数)

解决方案：

1，取 n=b-a+1，取最小的正整数m，使得 2^m >= n 2，调用RANDOM(0,1)，输出m-bit位整数N(N >= 0 and N <= 2^m-1) 3，ifN >=0and N <= b-a then return a+N else 重新执行步骤 2 [a,b]之间每个数都是以 1/2^m 的概率输出的

渐进运行时间分析：

我觉得渐进时间分析应该用概率分析的方法，我觉得是服从几何分布：
假设进行一系列伯努利试验，每次成功的概率是p，失败的概率是q=1-p，在取得一次成功前一共要进行多少次试验？令随机变量X为取得一次成功所要进行的试验次数，则X的取值范围{1,2,......}。对k>=1，因为在一次成功前有k-1次失败，从而有 Pr[X=k]= q^(k-1)p 满足上式的分布称为几何分布[见算法导论 P686] 在算法中 p=(b-a+1)/2^m 期望运行次数(算法中生成m位序列的调用次数)为：E[X]=sum(k*q^(k-1)p) [k=1......+无穷]=1/p=2^m/(b-a+1) 用T表示调用一次RANDOM(0,1)所需要的时间，每次运行时间为输出m位bit的时间：O(log(b-a) × T) 期望运行时间：O（T × log(b-a) × 2^m/(b-a+1) ）=(约等于)O(T × log(b-a))(因为m=(约等于)log(b-a+1))

2012-04-17 17:46

[转]C++生成随机数——生成任意范围内的等概率随机数

如果让你用C++来生成0——N-1之间的随机数，你会怎么做？你可能会说，很简单，看：

srand( (unsigned)time( NULL ) );
rand() % N;

仔细想一下，这个结果是随机的吗（当然，我们不考虑rand()函数的伪随机性）？

不是的，因为rand()的上限是RAND_MAX，而一般情况下，RAND_MAX并不是N的整数倍，那么如果RAND_MAX % = r，则0——r之间的数值的概率就要大一些，而r+1——N-1之间的数值的概率就要小一些。还有，如果N > RAND_MAX，那该怎么办？

下面给出一种比较合适的方案，可以生成任意范围内的等概率随机数 result。最后还有一个更简单的方法。

1、如果N<RAND_MAX+1，则要去除尾数，

R = RAND_MAX-(RAND_MAX+1)%N; //去除尾数
t = rand();
while( t > R ) t = rand();
result = t % N; // 符合要求的随机数

2、如果 N>RAND_MAX，可以考虑分段抽样，分成[n/(RNAD_MAX+1)]段，先等概率得到段再得到每段内的某个元素，这样分段也类似地有一个尾数问题，不是每次都刚好分到整数段，一定或多或少有一个余数段，这部分的值如何选取？

选到余数段的数据拿出来选取，先进行一次选到余数段概率的事件发生，然后进行单独选取：

r = N % (RAND_MAX+1); //余数
if ( happened( (double)r/N ) )//选到余数段的概率
result = N-r+myrandom(r); // myrandom可以用情况1中的代码实现
else
result = rand()+myrandom(N/(RAND_MAX+1))*(RAND_MAX+1); // 如果选不到余数段再进行分段选取

完整的代码：
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
const double MinProb=1.0/(RAND_MAX+1);
bool happened(double probability)//probability 0~1
{
if(probability<=0)
{
return false;
}
if(probability<MinProb)
{
return rand()==0&&happened(probability*(RAND_MAX+1));
}
if(rand()<=probability*(RAND_MAX+1))
{
return true;
}
return false;
}

long myrandom(long n)//产生0~n-1之间的等概率随机数
{
t=0;
if(n<=RAND_MAX)
{
long R=RAND_MAX-(RAND_MAX+1)%n;//尾数
t = rand();
while ( t > r )
{
t = rand();
}
return t % n;
}
else
{
long r = n%(RAND_MAX+1);//余数
if( happened( (double)r/n ) )//取到余数的概率
{
return n-r+myrandom(r);
}
else
{
return rand()+myrandom(n/(RAND_MAX+1))*(RAND_MAX+1);
}
}
}

还有另外一种非常简单的方式，那就是使用

random_shuffle( RandomAccessIterator _First, RandomAccessIterator _Last ).

例如，生成0——N-1之间的随机数，可以这么写

#include <algorithm>
#include <vector>

long myrandom( long N )
{
std::vector<long> vl( N ); // 定义一个大小为N的vector
for ( long i=0; i<N; ++i )
{
vl[i] = i;
}

std::random_shuffle( vl.begin(), vl.end() );

return (*vl.begin());
}

random_shuffle 还有一个三参数的重载版本

random_shuffle( RandomAccessIterator _First, RandomAccessIterator _Last, RandomNumberGenerator& _Rand )

第三个参数可以接受一个自定义的随机数生成器来把前两个参数之间的元素随机化。

这个方法的缺陷就是，如果只是需要一个随机数的话，当N很大时，空间消耗很大！

http://hi.baidu.com/hins_pan/item/32e29d733cc07915d1dcb36e

分享到：

概率随机问题 | 一次遍历等概率选取字符串中的某个字符

2013-05-27 20:48
浏览 859
评论(0)
分类:互联网
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论