前几天看到我司的一道面试题，给出一个rand3函数，能够等概率返回1、2、3，要求实现一个rand7函数，能够等概率的返回1-7
初看题目，有两种思路
- 调用rand3的结果除以3，再乘以7，这样得到的结果是7/3，14/3以及7，显然不符合题目要求
- 重复调用rand3的结果7次，再除以3，这样得到的结果为7/3～7，也不符合题目要求
反过来想想，如果是提供rand7函数，要求给出一个rand3函数，就很简单了，因为出现1-7的概率都是1/7，因此只需要在出现1-3的时候返回即可，这给我们提供了一种思路，如果两个rand3的结果相乘，会得倒1-9这九种结果，只需要将1-7的结果赋给rand7即可
[1, 2, 3]
[4, 5, 6]
[7, 0, 0]
python实现如下
def rand7():
i, j = rand3(), rand3()
if i == 2 and j >= 1:
return rand7()
return (i - 1) * 3 + j
上面这种方法在求rand9之前都是有效果的，但是超过9的随机数就没有办法表示了，于是，需要想新的方法
其实，还有一种方法，本质和上面的方法差不多，即根据
3 * (rand3() - 1) + rand3()
通过这个式子，同样能得到1-9九种可能，python代码如下所示
def rand7():
num = 3 * (rand3() - 1) + rand3()
if num > 7:
return rand7()
return num % 7 + 1
最后给出一个通用性的函数，传入m, n即能获得对应的概率生成函数
def universal_rand(m, n):
"""
m: 传入的进制数
n: 需要输出的进制数
"""
tmp = m * (m - 1)
max_sum = m + tmp
level = 1
while max_sum < n:
tmp *= m
max_sum += tmp
level += 1
threshold = (max_sum / n) * n
def rand(threshold, m, n, level):
"""
threshold: 丢弃数据的门槛
m: 传入的进制数
n: 需要输出的进制数
level: 层数
"""
num = randm()
tmp = randm() - 1
for _ in xrange(level):
tmp *= m
num += tmp
if num > threshold:
return rand(threshold, m, n, level)
return num % n + 1
return rand(threshold, m, n, level)