一尘不染

生成对Random(0,1)进行调用的Random(a,b)

algorithm

有一个已知的Random(0,1)函数,它是一个统一的随机函数,这意味着它将给出0或1,概率为50%。实现Random(a, b)只调用Random(0,1)

到目前为止,我将范围ab放入基于0的数组中,然后得到索引0、1、2 … ba。

然后调用RANDOM(0,1)ba次,将结果相加为生成的idx。并返回元素。

但是,由于书中没有答案,所以我不知道这种方法是正确的还是最好的。如何证明返回每个元素的概率是完全相同的1/(b-a+1)

正确/更好的方法是什么?


阅读 445

收藏
2020-07-28

共1个答案

一尘不染

如果您的RANDOM(0,1)返回0或1,每个返回的概率为0.5,那么您可以生成位,直到您有足够的二进制数来表示数字(b-a +
1)。这会给您一个随机数,但范围会稍大一些:如果失败,您可以测试并重复。像这样(在Python中)。

def rand_pow2(bit_count):
    """Return a random number with the given number of bits."""
    result = 0
    for i in xrange(bit_count):
        result = 2 * result + RANDOM(0, 1)
    return result

def random_range(a, b):
    """Return a random integer in the closed interval [a, b]."""
    bit_count = math.ceil(math.log2(b - a + 1))
    while True:
        r = rand_pow2(bit_count)
        if a + r <= b:
            return a + r
2020-07-28