因为1/7是一个以5为底的无限小数，所以没有(完全正确的)解可以在常数时间内运行。一个简单的解决方案是使用拒绝抽样，例如:

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

这个循环的预期运行时间为25/21 = 1.19次迭代，但是永远循环的概率非常小。

简单的解决方案已经被很好地覆盖了:为一个random7结果取两个random5样本，如果结果超出了产生均匀分布的范围，就重新做一次。如果你的目标是减少对random5的调用次数，这是非常浪费的——对于每个random7输出，对random5的平均调用次数是2.38，而不是2，这是由于丢弃样本的数量。

你可以通过使用更多的random5输入一次生成多个random7输出来做得更好。对于使用31位整数计算的结果，最优结果是使用12次调用random5生成9个random7输出，平均每个输出调用1.34次。它是高效的，因为244140625个结果中只有2018983个需要废弃，或者不到1%。

Python演示:

def random5():
    return random.randint(1, 5)

def random7gen(n):
    count = 0
    while n > 0:
        samples = 6 * 7**9
        while samples >= 6 * 7**9:
            samples = 0
            for i in range(12):
                samples = samples * 5 + random5() - 1
                count += 1
        samples //= 6
        for outputs in range(9):
            yield samples % 7 + 1, count
            samples //= 7
            count = 0
            n -= 1
            if n == 0: break

>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606

从一个扩大浮动范围的链接来到这里。这个更有趣。而不是我是如何得出结论的，我突然想到，对于一个给定的随机整数生成函数f，以“基数”b(在这种情况下是4，我会告诉为什么)，它可以展开如下:

(b^0 * f() + b^1 * f() + b^2 * f() .... b^p * f()) / (b^(p+1) - 1) * (b-1)

这将把随机生成器转换为FLOAT生成器。我将在这里定义2个参数b和p。虽然这里的“基数”是4，但b实际上可以是任何东西，它也可以是无理数等p，我称之为精度是你想要的浮点生成器的良好粒度的程度。可以把这看作是对rand7的每次调用对rand5的调用数。

但我意识到，如果你把b设为底数+1(在这种情况下是4+1 = 5)，这是一个最佳点，你会得到均匀的分布。首先摆脱这个1-5生成器，它实际上是rand4() + 1:

function rand4(){
    return Math.random() * 5 | 0;
}

为了达到这个目的，你可以用rand5()-1替换rand4

接下来是将rand4从整数生成器转换为浮点生成器

function toFloat(f,b,p){
    b = b || 2;
    p = p || 3;
    return (Array.apply(null,Array(p))
    .map(function(d,i){return f()})
    .map(function(d,i){return Math.pow(b,i)*d})
    .reduce(function(ac,d,i){return ac += d;}))
    /
    (
        (Math.pow(b,p) - 1)
        /(b-1)
    )
}

这将把我写的第一个函数应用到一个给定的rand函数。试一试:

toFloat(rand4) //1.4285714285714286 base = 2, precision = 3
toFloat(rand4,3,4) //0.75 base = 3, precision = 4
toFloat(rand4,4,5) //3.7507331378299122 base = 4, precision = 5
toFloat(rand4,5,6) //0.2012288786482335 base = 5, precision =6
...

现在，您可以将这个浮动范围(0-4 include)转换为任何其他浮动范围，然后将其降级为整数。这里我们的底是4，因为我们处理的是rand4，因此b=5的值会给你一个均匀分布。当b增长超过4时，你将开始在分布中引入周期性间隙。我测试了从2到8的b值，每个值都有3000分，并与原生数学进行了比较。随机的javascript，在我看来甚至比本机本身更好:

http://jsfiddle.net/ibowankenobi/r57v432t/

对于上面的链接，单击分布顶部的“bin”按钮以减小分箱大小。最后一个图表是原生数学。随机的，第四个d=5是均匀的。

在你得到浮动范围后，要么与7相乘并抛出小数部分，要么与7相乘，减去0.5并四舍五入:

((toFloat(rand4,5,6)/4 * 7) | 0) + 1   ---> occasionally you'll get 8 with 1/4^6 probability.
Math.round((toFloat(rand4,5,6)/4 * 7) - 0.5) + 1 --> between 1 and 7

这里允许作业题吗?

这个函数进行粗略的“以5为基数”的数学运算，生成0到6之间的数字。

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}

下面是Adam回答的Python实现。

import random

def rand5():
    return random.randint(1, 5)

def rand7():
    while True:
        r = 5 * (rand5() - 1) + rand5()
        #r is now uniformly random between 1 and 25
        if (r <= 21):
            break
    #result is now uniformly random between 1 and 7
    return r % 7 + 1

我喜欢把我正在研究的算法扔进Python，这样我就可以摆弄它们，我想我把它贴在这里，希望它对外面的人有用，而不是花很长时间来拼凑。

对于0-7的值，你有以下内容:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

从左到右，Rand5()有p(1) ={2/ 5,2 / 5,3 /5}。因此，如果我们补这些概率分布(~Rand5())，我们应该能够使用它来生成我们的数字。我稍后会给出解决方案。有人有什么想法吗?

R