首页 > 试题广场 >

（数据结构与算法）已知一随机发生器，产生0的概率是P，产生1

[问答题]
（数据结构与算法）已知一随机发生器，产生0的概率是P，产生1的概率是1-P。现在需要构造一个发生器，使得它构造0和1的概率均为1/2，请写出思路或伪代码 
添加回答
HughYoung头像 HughYoung

这是随机概率发生器的典型题目。

由于需要产生1/2，而用1位0，或1位1无法产生等概率，因此，考虑将随机数扩展成2位：

00   p*p

01  p*(1-p)

10  (1-p)*p

11 (1-p)*(1-p)

有上述分析知道，01和10是等概率的，因此我们只需要产生01和10就行了。

于是可以，遇到00和11就丢弃，只记录01和10。可以令，01表示0,10表示1，则等概率1/2产生0和1了。
发表于 2018-02-09 10:59:44 回复(0)
Ricardo201903081552408头像 Ricardo201903081552408
产生随机数N次
将N次随机数的和加起来，
可以预见和是将以N*(1-P)为轴呈正态分布
当和大于N*(1-P)就产生1，反之产生0
N越大产生0的几率越接近1/2
发表于 2019-03-08 19:51:16 回复(0)
提交观点

问题信息

算法工程师 唯品会 2018
来自：唯品会2018校招机器...
上传者：小小
难度：
2条回答 1995浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号