如何从生成0/1的随机数生成器构建随机数生成器

Question

随机数生成器以相等的概率生成0或1

如何创建另一个可以生成0到N之间的整数的随机数生成器

Answer 1

很容易生成0到2 ^ k - 1范围内的随机数。当n不是2的幂时，你可以找到n <2 ^ k的最小k，并重复生成0范围内的随机数。到2 ^ k - 1直到你得到一个实际上<n。在获得命中之前预期的试验次数小于2（因为选择k是最小的，命中的概率是> 0.5）所以这在实践中将是相当有效的。一个Python实现来充实这些想法：

from random import randint
from math import ceil,log

#a test function to generate random bits:
def rand2(): return randint(0,1)

def rand2n(n):
     #returns a random int in range 0 to 2^n - 1
     p = 1
     s = 0
     for i in range(n):
          if rand2() == 1:s += p
          p *= 2
     return s

def randn(n):
     #returns random int in range 0,...,n-1
     k = ceil(log(n,2))
     while True:
          x = rand2n(k)
          if x < n:
               return x #else, loop

Answer 2

将N转换为二进制。获取位数（比如n）。现在使用您拥有的生成器生成n位随机位。然后将新数字转换为十进制并除以N.您将得到介于0到N之间的数字。