随机数实现

这类题目通常是给你一个函数 可以实现 一个区间内的随机数，然后让你设计另一个函数，去实现指定区间
内的随机数。

如：一个函数可以实现1-5的随机数，设计另一个函数，实现1-7的随机数。

通常的实现方法：

1. 通过给定的随机数实现函数，想办法实现一个随机函数 $g$，可以等概率得到0和1；
2. 通过这个随机函数 $g$，结合移位运算，实现新的随机数函数。

# 一个函数可以实现1-5的随机数，设计另一个函数，实现1-7的随机数
class Rand2rand:
    def f5(self):
        return int(random.random()*5) + 1

    # 等概率得到0和1
    def g01(self):
        while True:
            tmp = self.f5()
            if tmp < 3:
                return 0
            elif tmp > 3:
                return 1
            else:
                continue

    # 等概率得到0-6
    def f06(self):
        while True:
            tmp = (self.g01() << 2) + (self.g01() << 1) + (self.g01() << 0)
            if tmp == 7:
                continue
            else:
                return tmp

    # 等概率得到1-7
    def f17(self):
        return self.f06() + 1

    # 验证结果
    def testRes(self, testTimes: int):
        arr = [0] * 7
        for i in range(testTimes):
            tmp = self.f17()
            arr[tmp-1] += 1

        for i in range(len(arr)):
            print(f'{i+1} 出现了 {arr[i]} 次')


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

更一般的问题，给定一个可以产出[min, max]之间的等概率随机数函数，生成一个可以等概率生成[from, to]之间的随机数函数

class Rand2randGeneral:
    """
    更一般的问题，给定一个可以产出[min, max]之间的等概率随机数函数，
    生成一个可以等概率生成[from, to]之间的随机数函数
    """
    def __init__(self, min, max):
        self.min = min
        self.max = max

    def randomBox(self):
        diff = int(random.random() * (self.max - self.min + 1))
        randomValue = self.min + diff
        return randomValue

    def getrand01(self):
        size = self.max - self.min + 1

        # 判断size 是奇数还是偶数
        isOdd = True if (size & 1) != 0 else False
        mid = int(size/2)

        while True:
            ans = self.randomBox() - self.min
            if isOdd and ans == mid:
                continue
            elif ans < mid:
                return 0
            else:
                return 1

    def getRandGeneral(self, fromValue, toValue):
        if fromValue == toValue:
            return fromValue

        rangeVal = toValue - fromValue
        num = 1
        while (1 << num) - 1 < rangeVal:
            num += 1

        while True:
            ans = 0
            for i in range(num):
                ans |= self.getrand01() << i
            if ans > rangeVal:
                continue
            else:
                return ans + fromValue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49