如何让穿制服的任意一间，B用已知的穿制服的随机函数随机的（0,1） [英] how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)

问题描述

背景有关的问题

我在读一本书的算法。有一章，这是关于偶合。章后，有一个锻炼区。但书中并没有回答这些演习。现在的问题是运动的问题。但它不是从学校的功课。

I am reading a algorithm book. There is a chapter, which is regarding Randoms. after the chapter, there is an exercise section. but the book has no answers to those exercises. The question is one exercise question. But it is not homework from school.

说，

已知有RANDOM（0,1）的功能，它是一个穿制服随机函数，这意味着，它会给0或1，以概率50％。现在设计一个算法，仅使用这种公知的随机（0,1），以生成的随机数范围内的a，b（含）。

There is known RANDOM(0,1) function, it is a uniformed random function, which means, it will give 0 or 1, with probability 50%. Now design an algorithm, only using this known RANDOM(0,1), to generate random number in range a,b(inclusive).

我虽然到目前为止，把范围AB的0的数组，然后我有索引0，1，2 ... BA。

what I though so far is, put the range a-b in a 0 based array, then I have index 0, 1, 2...b-a.

然后调用随机的（0,1）BA倍，总结的结果产生IDX。并返回该元素

then call the RANDOM(0,1) b-a times, sum the results as generated idx. and return the element.

然而，因为在书没有答案，我不知道这种方式是正确的或最好的。如何证明返回每个元素的概率是完全相同的，并且 1 /（B-A + 1）的

however since there is no answer in the book, I don't know if this way is correct or the best. How to prove that the probability of returning each element is exactly same and is 1/(b-a+1) ?

和什么是正确的/更好的方式来做到这一点？ （如果有）。

And what is the right/better way to do this? (if there was.)

推荐答案

如果你随机的（0,1）返回0或1，每个概率0.5，那么你可以生成位，直到你有足够的重新present数（B-A + 1）个二进制。这给你一个随机数略微偏大范围：您可以测试，如果失败重复。像这样的东西（在Python）。

If your RANDOM(0, 1) returns either 0 or 1, each with probability 0.5 then you can generate bits until you have enough to represent the number (b-a+1) in binary. This gives you a random number in a slightly too large range: you can test and repeat if it fails. Something like this (in 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

这篇关于如何让穿制服的任意一间，B用已知的穿制服的随机函数随机的（0,1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！