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

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