以等概率生成数字

Question

给你一个函数，比方说 bin()，它将以相等的概率生成 0 或 1。现在给你一系列连续的整数，比如 [a,b]（包括 a 和 b）。

写一个函数说 rand() 使用 bin() 以等概率生成范围 [a,b] 内的数字

Answer 1

帮助，但没有代码：

您可以轻松地将范围 [0,2 ** n] 移动到 [a,a+2 ** n]
您可以轻松地从 [0,2**n-1]
如果您需要一个不是 2 的幂的数字，只需生成一个最大为 2 ** n 的数字，如果超过您需要的数字则重新掷骰

Answer 2

您需要的洞察力是您的 bin() 函数 returns 单个二进制数字，或 "bit"。调用它一次会给你 0 或 1。如果你调用它两次，你会得到两位 b0 和 b1，它们可以组合为 b1 * 2 + b0，给你一个 0、1、2 或3 概率相等。如果你调用它三次，你会得到三个位 b0、b1 和 b2。把它们放在一起，你得到 b2 * 2^2 + b1 * 2 + b0，给你 {0, 1, 2, 3, 4, 5, 6, 7} 的成员等概率。以此类推，想加多少就加多少。

您的范围 [a, b] 有 m = b-a+1 个值。您只需要足够的位来生成 0 和 2^n-1 之间的数字，其中 n 是使 2^n-1 大于或等于 m 的最小值。然后只需缩放该设置以从 a 开始就可以了。

假设给定范围 [20, 30]。那里有 11 个数字，从 20 到 30（含）。 11 大于 8 (2^3)，但小于 16 (2^4)，因此您需要 4 位。使用 bin() 生成四个位 b0、b1、b2 和 b3。将它们放在一起作为 x = b3 * 2^3 + b2 * 2^2 + b1 * 2 + b0。您将得到一个结果 x，介于 0 和 15 之间。如果 x > 11，则生成另外四位。当 x <= 11 时，你的答案是 x + 20.

Answer 3

减去数字得出您的范围：

Decimal: 20 - 10 = 10
Binary : 10100 - 01010 = 1010

算出你需要多少位来表示这个：4。

对于其中的每一个，生成一个随机的 1 或 0：

num_bits = 4
rand[num_bits]
for (x = 0; x < num_bits; ++x)
  rand[x] = bin()

让我们在这之后说rand[] = [0,1,0,0]。将此数字添加回您的范围的开头。

Binary: 1010 + 0100 = 1110
Decimal: 10 + 4 = 14

Answer 4

您可以随时将范围 [a,b] 更改为 [0,b-a]，表示 X = b - a。然后你可以定义一个函数 rand(X) 如下：

function int rand(X){
   int i = 1;
   // determine how many bits you need (see above answer for why)
   while (X < 2^i) {
      i++;
   }
   // generate the random numbers
   Boolean cont = true;
   int num = 0;
   while (cont == true) {
      for (j = 1 to i) {
         // this generates num in range [0,2^i -1] with equal prob
         // but we need to discard if num is larger than X
         num = num + bin() * 2^j;
      }
      if (num <= X) { cont = false}
   }
   return num;
}

以等概率生成数字

Generate number with equal probability

algorithm

probability