有一个已知的Random(0,1)函数,它是一个统一的随机函数,这意味着它将给出0或1,概率为50%。实现Random(a, b)只调用Random(0,1)
Random(0,1)
Random(a, b)
到目前为止,我将范围ab放入基于0的数组中,然后得到索引0、1、2 … ba。
然后调用RANDOM(0,1)ba次,将结果相加为生成的idx。并返回元素。
RANDOM(0,1)
但是,由于书中没有答案,所以我不知道这种方法是正确的还是最好的。如何证明返回每个元素的概率是完全相同的1/(b-a+1)?
1/(b-a+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