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

This topic created in 4566 days ago, the information mentioned may be changed or developed.

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

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

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

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

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

rand5

rand7

自然数

11 replies • 1970-01-01 08:00:00 +08:00

Mutoo

Dec 6, 2013

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

sNullp

Dec 7, 2013

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

SoloCompany

Dec 7, 2013

连续调用 7 次 rand5() 求和然后除以 5 取整不行么？

9hills

Dec 7, 2013

@SoloCompany 取下整就不是随机了，各点不是等概率的

9hills

Dec 7, 2013

@SoloCompany 这样最后应该是一个正态分布的概率图

SoloCompany

Dec 7, 2013

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

9hills

Dec 7, 2013

@SoloCompany 不考虑取整。。你这个实际概率分布是正态分布啊<_<

SoloCompany

Dec 7, 2013

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

SoloCompany

Dec 7, 2013

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

suriv520

Dec 7, 2013

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

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

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

regmach

Dec 8, 2013

插一个问题,怎么得到rand3() ?`