给定一个生成1到5rand5()范围内随机整数的函数，编写一个生成1到7rand7()范围内随机整数的函数

在我建议的解决方案中，我只调用rand5一次

真正的解决方案

float rand7()
{
    return (rand5() * 7.0) / 5.0 ;
}

这里的分布是缩放的，所以它直接取决于rand5的分布

整数解

int rand7()
{
    static int prev = 1;

    int cur = rand5();

    int r = cur * prev; // 1-25

    float f = r / 4.0; // 0.25-6.25

    f = f - 0.25; // 0-6

    f = f + 1.0; // 1-7

    prev = cur;

    return (int)f;
}

这里的分布取决于rand7(i) ~ rand5(i) * rand5(i-1)

rand7(0) ~ rand5(0) * 1

这是我在看过别人的答案后得出的最简单的答案:

def r5tor7():
    while True:
        cand = (5 * r5()) + r5()
        if cand < 27:
            return cand

Cand在[6,27]范围内，如果r5()的可能结果是均匀分布的，则可能结果是均匀分布的。你可以用下面的代码来测试我的答案:

from collections import defaultdict

def r5_outcome(n):
    if not n:
        yield []
    else:
        for i in range(1, 6):
            for j in r5_outcome(n-1):
                yield [i] + j

def test_r7():
    d = defaultdict(int)
    for x in r5_outcome(2):
        s = sum([x[i] * 5**i for i in range(len(x))])
        if s < 27:
            d[s] += 1
    print len(d), d

R5_outcome(2)生成r5()结果的所有可能组合。我使用与解决方案代码中相同的筛选器进行测试。你可以看到所有的结果都是相等的，因为它们有相同的值。

这里我们使用约定的rand(n) -> [0, n - 1]

从我读到的许多答案中，它们要么提供了一致性，要么提供了暂停保证，但不能同时提供(adam rosenfeld的第二个答案可能)。

然而，这样做是可能的。我们基本上有这样的分布:

这给[0-6]上的分布留下了一个漏洞:5和6没有 发生的概率。想象一下，现在我们试图通过移动 概率分布和求和。

事实上，我们可以把初始分布平移1，然后 重复将得到的分布与移位的初始分布相加 2，然后3，以此类推，直到7，不包括在内(我们涵盖了整个范围)。 如下图所示。颜色的顺序，对应 步骤，是蓝色->绿色->青色->白色->品红->黄色->红色。

因为每个插槽由7个移位分布中的5个覆盖(移位从 0到6)，因为我们假设随机数是独立于1的 Ran5()呼叫另一个，我们获得

p(x) = 5 / 35 = 1 / 7       for all x in [0, 6]

这意味着，给定来自ran5()的7个独立随机数，我们可以 计算一个在[0-6]范围内具有均匀概率的随机数。 实际上是ran5()概率 分布甚至不需要均匀，只要样本是均匀的 独立(所以每次试验的分布保持不变) 同样，这也适用于5和7之外的其他数字。

这为我们提供了以下python函数:

def rand_range_transform(rands):
    """
    returns a uniform random number in [0, len(rands) - 1]
    if all r in rands are independent random numbers from the same uniform distribution
    """
    return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic

可以这样使用:

rand5 = lambda : random.randrange(5)

def rand7():
    return rand_range_transform([rand5() for _ in range(7)])

如果我们调用rand7() 70000次，我们可以得到:

max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0:  10019
1:  10016
2:  10071
3:  10044
4:  9775
5:  10042
6:  10033

这很好，尽管远非完美。事实上，我们的一个假设是 在这个实现中很可能是false:我们使用一个PRNG，因此，结果 的值依赖于上一个结果。

也就是说，使用一个真正随机的数字来源，输出也应该是 真正随机的。这个算法在任何情况下都终止。

但这是有代价的:我们需要为一个rand7()调用7次rand5() 调用。

#!/usr/bin/env ruby
class Integer
  def rand7
    rand(6)+1
  end
end

def rand5
  rand(4)+1
end

x = rand5() # x => int between 1 and 5

y = x.rand7() # y => int between 1 and 7

．．尽管这可能被认为是作弊。

我不喜欢从1开始的范围，所以我将从0开始:-)

unsigned rand5()
{
    return rand() % 5;
}

unsigned rand7()
{
    int r;

    do
    {
        r =         rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
    } while (r > 15623);

    return r / 2232;
}

以下是我的回答:

static struct rand_buffer {
  unsigned v, count;
} buf2, buf3;

void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
  buf->v = buf->v * n + v;
  ++buf->count;
}

#define PUSH(n, v)  push (&buf##n, n, v)

int rand16 (void)
{
  int v = buf2.v & 0xf;
  buf2.v >>= 4;
  buf2.count -= 4;
  return v;
}

int rand9 (void)
{
  int v = buf3.v % 9;
  buf3.v /= 9;
  buf3.count -= 2;
  return v;
}

int rand7 (void)
{
  if (buf3.count >= 2) {
    int v = rand9 ();

    if (v < 7)
      return v % 7 + 1;

    PUSH (2, v - 7);
  }

  for (;;) {
    if (buf2.count >= 4) {
      int v = rand16 ();

      if (v < 14) {
        PUSH (2, v / 7);
        return v % 7 + 1;
      }

      PUSH (2, v - 14);
    }

    // Get a number between 0 & 25
    int v = 5 * (rand5 () - 1) + rand5 () - 1;

    if (v < 21) {
      PUSH (3, v / 7);
      return v % 7 + 1;
    }

    v -= 21;
    PUSH (2, v & 1);
    PUSH (2, v >> 1);
  }
}

它比其他的稍微复杂一点，但我相信它最小化了对rand5的调用。与其他解决方案一样，它有小概率会循环很长时间。