可否在有限步骤内通过函数rand5()得到rand7()？

通过rand5()实现rand7()是一个挺有名的概率学面试题。是这样的：

函数rand5()可以随机产生概率均等的1-5这5个自然数。
要求通过rand5()，实现rand7()，即产生随机分布在1-7区间内的自然数。

大多数解法就是一个思路：把rand5()范围扩大然后映射到1-7这个区间内：
http://www.cnblogs.com/dwdxdy/archive/2012/07/28/2613135.html

但事实上，这些算法在极端情况下，会出现无限循环而得不到结果。

求(证)：
有没有一种解法，能在有限的步骤内实现上述要求？

Mutoo

2013 年 12 月 6 日

理论上是收敛的，不会无限循环。可以构造更大的组合使收敛速度加快。也就是用空间换时间。

sNullp

2013 年 12 月 7 日

因为只用 1/5 通过加或者乘都无法得出 1/7 ，所以理论上永远存在无限循环。

SoloCompany

2013 年 12 月 7 日

@9hills 我错了，简单验算一下，实验 n 次的结果数是 5 ^ n 不可能整除 7，可以推断是无法得到真随机的 rnd7()，但非常逼近还是可以的

SoloCompany

2013 年 12 月 7 日

@9hills 我的意思已经不是相加了，是n阶矩阵，然后对结果数分类，由于不能整除7，算法总是会有一个余数存在，不能完全实现 rnd7()
以n=4为例，5^4=625 = 7*89 + 2
可以把625个结果按89个结果分类，落在这些结果中就取对应的值。但剩下2的区间就无法覆盖，就是说有 2/625 的偏差

SoloCompany

2013 年 12 月 7 日

基于这个思路可以完善那个递归算法，先根据区间划分，然后进行实验
每次递归如果得到的4个rand5()结果落在 623 个结果内，就可以直接返回结果
如果不幸落在那 2 个结果里面，需要重复实验（也就是递归调用）
可以限制一下递归次数（比如10），如果10次随机数返回都落在那个2里面（这个几率很低了），就直接返回0

suriv520

2013 年 12 月 7 日

@SoloCompany 摔！为毛v2ex没有回复提醒……

是的。我凭感觉也认为没有能在确定步骤内的得到结果的算法。或者说，理论上通过一元运算或二元运算，也无法将概率区间一一映射。

但貌似没办法给出严格意义上的证明……

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/92136

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.