修改均匀随机数生成器的范围

Question

我得到一个函数rand5(),它在均匀分布中生成闭区间[1,5]中的随机整数.我如何使用rand5(),而不是别的,来创建一个函数rand7(),它在[1,7]中生成整数(再次,均匀分布)？

---

1. 我搜索了stackoverflow,发现了许多类似的问题,但不完全像这个问题.
2. 我最初的尝试是rand5()+ 0.5*rand5()+ 0.5*rand5().但是这不会以均匀的概率从1到7生成整数.任何答案或答案链接都是非常受欢迎的.

Answer 1

请注意,使用有限数量的draw5()调用无法实现完美的均匀分布,因为对于每个k:5^k % 7 != 0- 因此您将始终拥有一些"备用"元素.

这是一个具有无限draw5()使用次数的解决方案:

画两个数字,x1,x2.这有5*5 = 25种可能的结果.

注意25/7~ = 3.57.选择3*7 = 21种组合,这样每个组合将映射到[1,7]中的一个数字,对于所有其他4个数字 - 重绘.

例如:

(1,1),(1,2),(2,1) : 1
(3,1),(1,3),(3,2): 2
(3,3),(1,4),(4,1): 3
(2,4),(4,2)(3,4): 4
(4,3), (4,4), (1,5): 5
(5,1), (2,5), (5,2) : 6
(5,3), (3,5), (4,5) : 7
(5,4),(5,5),(2,3), (2,2) : redraw

Answer 2

好吧，我不得不考虑一会儿，但实际上并不难。想象一下，你有 rand2，它输出 0 或 1，而不是 rand5。你可以通过简单地执行以下操作来使 rand2 成为 rand5 的我们

rand2() {
    if(rand5() > 2.5) return 1
    else return 0
}

现在多次使用 rand2 做一棵树来得到 rand7。例如，如果你启动 rand7 可以在抛出 rand2 之后在 [1,2,3,4,5,6,7] 中，它给出 0 你现在子集到 [1,2,3,4] 并在另一个抛出或之后rand2 是 1，你将其子集化为 [3,4]，最后抛出 1 给出 rand7 的输出为 4。一般来说，这个树技巧可以使用 rand2 并映射到 randx，其中 x 是任何整数。