有一个随机数发生器，以概率P产生0，概率(1-P)产生1，请

[问答题]

有一个随机数发生器，以概率P产生0，概率(1-P)产生1，请问能否利用这个随机数发生器，构造出新的发生器，以1/2的概率产生0和1。请写明结论及推理过程。

推荐

哈哈哈32

这道题想等概率产生0、1，就需要找到两个独立事件，这个两个独立事件发生的概率相同，已知随机数生成器可以以p产生0，以1-p产生1，所以有下面4个独立事件，用随机数生成器产生00，01，10，11，各自的概率分别为p*p，p*(1-p)，(1-p)*p，(1-p)*(1-p)可以发现生成01，10的概率相同，因此只保留这两种情况敏感词舍弃，然后将01映射为0，10映射为1，则等概率0，1随机数生成器可得到

编辑于 2015-02-10 20:25:18 回复(5)

评估未通过

这题我面试的时候遇到过，当时思路是叠加多个原始构造器，通过每次叠加的和与期望值对比，来决定是0和1，思路得到了面试官的采纳。具体如下：

迭代N次，则期望E=( (1-p)*1 + p*0) * N 。比较累加N次的和Sum和E，Sum大则返回0，Sum小则返回1。

拓展1：用等概率生成（0,1）的构造器等概率生成（0,1,2,3）。

假设，原始构造器为Rand2()，则Rand2()*2为（0,2），Rand2()*2 + Rand2()则可以生成（0,1,2,3）。注意Rand2()*2 + Rand2()不等于Rand2()*3，后者等于（0,3），只用了一次构造器。前者由part1:（0,2）和part2:（0,1）构成。最终结果（0,1,2,3）任何一个数字都由part1和part2中唯一的数字相加得到。

用Rand4（等概率生成0,1,2,3）可以进一步生成Rand16。方法为：Rand4()*4 + Rand4()

拓展2：用等概率生成（0,1）的构造器等概率生成（0,1,2,3，...，N）。

思路同上相似。由（0,1）的构造器可以生成（0，...，2^n）的构造器，其中每次构造生成的随机数个数是上一次的平方。只需要构造到保证2^n>N即可。当得到的随机数处于[N, 2^n）时，递归生成一次，直到构造数为[0,N)时，退出本次随机数生成。代码思路可以参数楼上追梦_吹吹风同学的答案。

编辑于 2017-07-22 21:38:16 回复(2)

追梦_吹吹风

randp()以概率p产生0，概率（1-p）产生1；

a=0,b=1的概率为p(1-p),将其视为0

a=1,b=0的概率也为p（1-p）,将其视为1

则产生0和1的概率相等

int randequal() { ;int a=randp();

int b=randp();

if(a==0;b==1) return 0;

if(a==1;b==0)

return 1;

return randequal();

}

编辑于 2015-09-11 20:15:55 回复(0)

InkPower

已知：产生0的概率为P，产生1的概率为（1-P）
则：产生01的概率为P（1-P），产生10的概率为（1-P）P，两者相等
则：新函数，产生01返回0，产生10返回1.

发表于 2017-08-12 15:03:31 回复(0)

每天积累一点hong

让随机发生器产生两个数，总共有4种情况，将其中两种情况映射为1，另外两种为0

发表于 2017-03-24 17:07:00 回复(2)

小刀初试

这个是二项分布B(n,p).当p较小，而n足够大时，二项分布近似为正态分布N(sqrt(np(1-p)),np).正态分布是关于x=np直线左右对称的，必然存在若干对(xi,xi')相互对称，即概率相同。若将其他的情况视为噪声，只考虑对称的点(xi,xi')，则两个概率比值为1:1.将其映射为0和1,即可。

发表于 2015-10-08 13:30:33 回复(0)

FFF乔碧罗

今天百度二面问到了这个题目，跪了直接。

发表于 2015-09-18 17:05:24 回复(0)

袁斌

<div> public int getRand() </div> <div> { </div> <div>      int x,y; </div> <div>     while((x = rand()) == (y = rand())) </div> <div>      ; </div> <div>      return x; </div> <div> } </div>

发表于 2015-08-24 15:04:39 回复(0)