阿里的随机数面试题思路分享

我觉得这是个挺有趣的题目，回复里面讨论了几点方法，可惜大部分都有些缺陷或者需要调用多次 foo 函数。我想说下我的想法。在此之前，我们需要回顾一下二进制的基础，

无符号的二进制 4 位 可以表达 0000 到 1111 也就是十进制的 0 到 15
无符号的二进制 5 位 可以表达 00000 到 11111 也就是十进制的 0 到 31

回复中一开始 @gaobing 提出了：

那 0 或 1 拼数字 ，2 位的 数字 共 4 种排列，3 位的 8 种排列，4 位的 16 种排列 ， 拿出 10 种排列指代 [ 0 -9] 这几个数字，剩下的 6 种排列不返回，重新计算随机数，直到出现 另外 10 种情况。

这是正确的解法，其实 Python 就是这样实现的，（源码在这里），不过在这个问题里，我们可以发现这种解法的弊端在于，有 6/16 也就是超过三分之一的的情况下需要重新计算随机数，平均来说我们需要运行多少次 foo 函数才能得到结果呢？我们可以计算一下：有 10/16 的情况我们只需要运行 4 次 foo 函数，剩下的 6/10 的情况我们需要重新计算随机数，但是，重新计算随机数还是可能超过区间，要一直计算直到小于区间。我不会讨论计算的细节，不过我们可以计算出平均需要运行 6.4 次 foo 函数。（读者可以自行推导）

有没有更好的方法呢？试想一下 random 函数是怎么实现的，随机生成一个很大的数字，然后在我们需要的范围内取模，回复也有提到这类解法：

1. 我们可以首先生成一串 32 位 的二进制序列并转换成整数，既然 foo 函数的 0 和 1 是随机的，那么这个二进制序列也就随机代表了 0 - 2 的 32 次方减 1 里面所有整数的值，
2. 把整数对 10 取模即可。

这个算法问题在于，他需要多次调用 32 次 foo 函数，并且需要模运算，而且不是严格意义上的 10% 的概率（因为所有数字的出现并不能被 10 整除）。更好的方法是什么呢？我们结合两种方法，

1. 我们运行 5 次 foo 函数得到一个二进制序列并将其转成整数（十进制范围 0 - 31 ）
2. 如果这个整数是 30 或者 31 的话，我们重新计算随机数，如果在 0 到 29 之间的话，那么我们将其对 10 取模。

为什么是运行 5 次呢，因为 5 位二进制能表示 0 到 31，而 31 是最小的最接近能被 10 整除的数字。（ 0 到 29 这 30 个数字刚好能被 10 整除）。同样可以计算出计算平均运行 foo 函数 5.33 次。时间复杂度为 O(5.33 * foo) 。欢迎大家留下自己的观点。

Python 代码如下

import random
import collections

def get_result():
    binary_lst = []
    for i in range(5):
        binary_lst.append(foo())
    binary_str = ''.join(binary_lst)
    return int(binary_str, 2)

def foo():
    return random.choice(['0', '1'])

def bar():
    res = get_result()
    while res == 30 or res == 31:
        res = get_result()
    return res % 10

count = collections.defaultdict(int)

for i in range(100000):
    count[bar()] += 1

print(count)