function Rand7
   put 200 into x
   repeat while x > 118
      put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
   end repeat
   return (x mod 7) + 1
end Rand7

3次调用Rand5，平均125次中只重复6次。

把它想象成一个5x5x5的3D数组，一遍又一遍地填满1到7，还有6个空格。重新滚动空白。rand5调用在该数组中创建一个以5为基数的三位索引。

4D或更高的n维数组的重复次数会更少，但这意味着对rand5函数的更多调用将成为标准。你会在更高维度上得到递减的效率回报。在我看来，三个似乎是一个很好的折衷方案，但我还没有对它们进行测试。它是特定于rand5实现的。

对于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

function Rand7
   put 200 into x
   repeat while x > 118
      put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
   end repeat
   return (x mod 7) + 1
end Rand7

3次调用Rand5，平均125次中只重复6次。

把它想象成一个5x5x5的3D数组，一遍又一遍地填满1到7，还有6个空格。重新滚动空白。rand5调用在该数组中创建一个以5为基数的三位索引。

4D或更高的n维数组的重复次数会更少，但这意味着对rand5函数的更多调用将成为标准。你会在更高维度上得到递减的效率回报。在我看来，三个似乎是一个很好的折衷方案，但我还没有对它们进行测试。它是特定于rand5实现的。

以下是我的发现:

Random5产生1~5的范围，随机分布 如果我们运行3次并将它们加在一起，我们将得到3~15个随机分布的范围 在3~15范围内执行算术 (3~15) - 1 = (2~14) (2~14)/2 = (1~7)

然后我们得到1~7的范围，这是我们正在寻找的Random7。

这相当于Adam Rosenfield的解决方案，但对一些读者来说可能更清楚一些。它假设rand5()是一个函数，返回1到5范围内的统计随机整数。

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

就像亚当说的，在最坏的情况下，它可以一直运行下去，但从统计上看，最坏的情况永远不会发生。：）

这个解决方案不浪费任何熵，并给出了范围内第一个可用的真正随机数。随着每一次迭代，得不到答案的概率可证明地降低了。在N次迭代中得到答案的概率是0到max (5^N)之间的随机数小于该范围内7的最大倍数(max-max%7)的概率。必须迭代至少两次。但这对所有解都是成立的。

int random7() {
  range = 1;
  remainder = 0;

  while (1) {
    remainder = remainder * 5 + random5() - 1;
    range = range * 5;

    limit = range - (range % 7);
    if (remainder < limit) return (remainder % 7) + 1;

    remainder = remainder % 7;
    range = range % 7;
  }
}

数值上等价于:

r5=5;
num=random5()-1;
while (1) {
   num=num*5+random5()-1;
   r5=r5*5;
   r7=r5-r5%7;
   if (num<r7) return num%7+1;
}

第一个代码以模形式计算。第二个代码只是简单的数学。或者我在某个地方犯了错误。: -)