algorithm - 创建一个使用另一个随机函数作为种子生成随机数的函数

Question

您有一个函数 f1()，它以相等的概率生成 0 或 1。编写一个函数 f200()，使用 f1() 生成 1 到 200(含)范围内的数字。

有人建议采用以下方法:抛一枚硬币，然后根据结果判断数字是否会超过一半或少于一半。对每一半递归地执行此操作。选择一半是通过 2 的幂来完成的。

选择2的幂是因为我们可以得到所有的数字吗？

import random as rd 

def prob200(half):
    if half >= 200:
        return 0    
    #f1 can be replaced by this rd.randint(0, 1)
    toss_value = f1() 
    # check if toss falls in this current half and then change the half for next recursion. 
    # we change half from 1, 2, 4, 8, 16, 36, 64, 128
    result = toss_value*half + prob200(half<<1)
    if result > 200:
        return prob200(1)
    else:
        return result

for i in range(0, 10):
    print(prob200(1))

Answer 1

使用随机位生成器创建一个具有 n 位的数字 x(例如，如果需要更好的精度，则 n=32 或更高=更均匀的分布)，然后将其转换为所需的范围 r(例如 r=200)，如下所示:结果=floor(x/2^n * r)+1

例如，如果使用 n=8，则将使用随机位生成器(函数 f1)生成一个 8 位数字，该数字的范围为 0-255(含)。然后将其除以 2^8=256，因此我们将得到一个介于 0 和 255/256 之间的数字。然后乘以 200，结果将在 0 到 199.2 之间。最后，我们将其向下舍入并加 1，得到 1 到 200 之间的数字。

但是由于我们只使用了 8 个随机位 (n=8)，因此均匀性不是很好。我们有效地生成了 0-255(源范围)之间的数字，并将其转换为 1-200(目标范围)之间的数字。目标范围中的大多数数字在源范围中都有一个对应的数字，但其他数字(例如数字 1)有两个对应的源数字(0 和 1)。所以有些数字出现的概率是 1/256，而其他数字出现的概率是 2/256。

为了改善这一点，我们可以使用 n=16，那么概率差异最多为 1/2^16。

这是一个程序，它首先尝试使用 8 位生成随机数，但如果溢出 4 次，则它会使用我描述的方法，生成 32 位数字并将其转换为输出范围:

import math
import random

def f1():
  return random.randint(0,1)

def rand_by_bits(n):
  v=0
  for i in range(n):
    v=(v<<1)+f1()
  return v

def rand_by_range(r):
  n=0
  t=r
  while t>0:
    t>>=1
    n+=1

  for i in range(4):
    v=rand_by_bits(n)
    if v<r:
      break

  if v>=r:
    n=32
    v=math.floor(float(rand_by_bits(n))/(1<<n)*r)

  return v+1

def main():
  random.seed()
  print(rand_by_range(200))