01发生器产生均匀分布

题目

1.有一个随机数发生器，能以概率p生成0，以概率1-p生成1，问如何做一个随机数发生器，使得生成0和1的概率相等。

2.用上面那个生成0和1的概率相等的随机数发生器，怎样做一个随机数发生器使得它生成
的数在1…N之间均匀分布。

思考

第一题比较简单，可以用原发生器周期性地产生2个数，直到生成01或者10。
由于生成01和10的概率均为p(1-p)，故预先任意指定01为0（或1），10为1（或0）即可。即可等概率的产生0和1。

Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/14
'''
1.有一个随机数发生器，能以概率p生成0，以概率1-p生成1，问如何做一个随机数发生器，使得生成0和1的概率相等。

2.用上面那个生成0和1的概率相等的随机数发生器，怎样做一个随机数发生器使得它生成的数在1…N之间均匀分布。
'''
import random
class Solution:
    def random_index(self):
        # """随机变量的概率函数"""
        # 参数rate为list<int>
        # 返回概率事件的下标索引
        # 这是一个10%概率产生0，90%概率产生1的生成器
        rate = [1, 9]

        start = 0
        index = 0
        randnum = random.randint(1, sum(rate))
        for index, scope in enumerate(rate):
            start += scope
            if randnum <= start:
                break
        return index

    def Rand1(self):
        # 第一题：可以用原发生器周期性地产生2个数，直到生成01或者10。
        i1 = self.random_index()
        i2 = self.random_index()
        if i1 == 0 and i2 == 1:
            return 1
        elif i1 == 1 and i2 ==0:
            return 0
        else:
            return self.Rand1()

    def Rand2(self, K: int):
        # 第二题，需要一些思考……想到位运算，因为i个二进制位随机的选择0或1，可以随机的构成0~2^i的数，
        # 而这些数构成了所有的组合数。因此是等概率出现的。
        # 比如：2位二进制位，这两位可以随机为0或1而互不影响，
        # 随机的构成了00 01 10 11，它们代表了四个数，且这四个数是等概率的。
        pass
        length = len(bin(K)[2:])
        res = ''
        for i in range(length):
            res += str(self.Rand1())
        if int(res, 2) > K:
            return self.Rand2(K)
        else:
            return int(res, 2)


if __name__ == '__main__':
    solution = Solution()
    rand1 = []
    for i in range(20):
        rand1.append(solution.Rand1())
    print(rand1)
    
    rand2 = []
    for i in range(20):
        rand2.append(solution.Rand2(100))
    print(rand2)

看一下结果：

OK， 完美符合要求！
可能缺点就是，时间复杂度有点高？？？