读书人

random(a,b)是如何实现的

发布时间: 2012-06-08 12:55:24 作者: rapoo

random(a,b)是怎么实现的?
假设有一个函数random(0,1)等概率的返回0,1;怎么利用它实现random(a,b),等概率的返回a到b的整数?
如果a+(b-a)*random(0,1)的话是二项分布,显然不对。
还有一个常见的随机试验是几何分布,显然也不对。

这个问题算法导论上说是一个确定的算法,可是书上没有答案。

[解决办法]
如果我们想得到[a,b]范围内等概率分布的整数,可以先将这个区间映射到一个二进制范围内,然后根据二进制数字的位数,调用相应次数的random(0,1)。

拿[1,7]举例来说,如果我们想得到1~7内整数的等概率分布,就可以连续调用random(0,1)三次,这样得到的是0~2^3-1范围内等概率分布的整数。如果得到0的话就舍弃,剩下的就是1~7内整数的等概率分布。

读书人网 >软件架构设计

热点推荐