随机函数扩大,如rand5()构造rand7()

数据结构 yan loading.. 3评论 已收录

引例

利用random(0,1)产生0或1,从而组成二进制数,来完成random(a,b)的实现

解决办法:运行random(0,1)函数k次,使得2k>=(b-a+1),将得到[0,2k)的整数区间,如何将[0,2k)映射到[a,b]的整数区间,保证产生各整数的概率相等,同为1/(b-a+1)?

1.当存在k使得2k=(b-a+1)时,只需将产生的二进制数与[a,b]整数一一对应,即可满足概率同为1/(b-a+1)的要求.

例如,random(3,6),k=2. 此时,对应关系可为00~3,01~4,10~5,11~6.产生的概率为1/4.

2.当不存在k使得2k=(b-a+1)时,产生[0,2k)区间整数的概率为1/2k,小于1/(b-a+1).[0,2k)如何映射到[a,b]整数区间.

思路一:扩大[0,2k)区间,使得2k可以被(b-a+1)整除,这样可以把[0,2k)分成N段时,每一段对应[a,b]里的一个整数.

但这个思路,是不可行的,因为不存在这样的k值.要么2k=(b-a+1),要么2k>(b-a+1)且不可被(b-a+1)整除.

思路二:参取截断映射,即 [0,2k) 的前部分映射到[a,b],这样虽然可以达到产生整数的概率相等,但不等于1/(b-a+1),还有如果产生[0,2k)后部分的值如何处理.

这个思路,是可行的如果产生后部分的值,就继续调用自身,重新random.从结果输出分析,最终random(a,b)最终输出的只有[a,b]里的整数,而且每个整数的概率相等,因而其产生的概率值是1/(b-a+1).

利用rand5()产生rand7()

rand5()产生1到5的整数,rand7()产生1到7的整数。

解决办法:解决思路与上述的练习题是一样的.利用rand5()产生的一个整数空间,然后将其映射到[1,7]的整数空间上,映射时保证概率相等,且等于1/7.

(1)利用预置数组  该方法简单,易理解,但是不具扩展性,需要额外存储空间.

(2)常规实现方法  可扩展,主要分为三步,构造大的整数区间,限制整数区间,最后映射整数区间.

(3)看似正确的方法 其实错误的方法

与方法2的思路一样,构造新的整数区间,但是方法3中构造的整数区间并不是等概率的.

第4代码中,将会产生5^7种可能的计算,但最终这些可能映射到[7,35]的整数区间中,但是[7,35]区间内整数的产生的概率并不相等.

例如,通过累加区间[0,1]三次,可以得到[0,3]的区间,但是[0,3]每个整数的概率并不相等,分别为1/8,3/8,3/8,1/8.

对于常规办法的进一步剖析

1、如果 rand5() + rand5(), 我们能够产生一个均匀分布的 1 – 10 吗?

答案是否定的。比如对于 6来讲(4+2, 2+4, 3+3),它被生成的生成的概率比1 (1+0,0+1)要大。

2、我们不可能用rand5()直接产生 1- 7 的数,不管你用加减乘除都不行。

所以,我们要构造一个更大的范围,使得范围里每一个值被生成的概率是一样的,而且这个范围是7的倍数。

代码如下:

第三行代码产生一个均匀分布的 0, 5, 10, 15, 20的数。

第四行代码产生一个均匀分布的 0, 1, 2, 3, 4 的数。相加以后,会产生一个 0到24的数,而且每个数(除0外)生成的概率是一样的。我们只取 1 – 21 这一段,和7 取余以后+1就能得到完全均匀分布的1-7的随机数了。

关注<爱上极客>公众号,定期推送精彩内容!

喜欢 (2)

如未说明则本站原创,转载请注明出处:爱上极客 » 随机函数扩大,如rand5()构造rand7()


0
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(3)个小伙伴在吐槽
  1. 好教程 学习了
    五常大米网2015-07-20 15:06 回复
  2. 不错
    dxx2015-11-25 16:47 回复
  3. http://www.nowamagic.net/librarys/veda/detail/2172
    yan2015-11-25 17:53 回复