algorithm - 以等概率生成数字

Question

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

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

Answer 1

您需要的洞察力是您的 bin()函数返回单个二进制数字或“位”。调用它一次会给你 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 .