这是一个创建于 3807 天前的主题，其中的信息可能已经有所发展或是发生改变。
通过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()可以随机产生概率均等的1-5这5个自然数。
要求通过rand5()，实现rand7()，即产生随机分布在1-7区间内的自然数。
大多数解法就是一个思路：把rand5()范围扩大然后映射到1-7这个区间内：
http://www.cnblogs.com/dwdxdy/archive/2012/07/28/2613135.html
但事实上，这些算法在极端情况下，会出现无限循环而得不到结果。
求(证)：
有没有一种解法，能在有限的步骤内实现上述要求？
 |
1
Mutoo 2013-12-06 23:33:58 +08:00
理论上是收敛的，不会无限循环。可以构造更大的组合使收敛速度加快。也就是用空间换时间。
|
 |
2
sNullp 2013-12-07 00:06:28 +08:00
因为只用 1/5 通过加或者乘都无法得出 1/7 ，所以理论上永远存在无限循环。
|
 |
3
SoloCompany 2013-12-07 00:27:00 +08:00
连续调用 7 次 rand5() 求和然后除以 5 取整不行么？
|
 |
4
9hills 2013-12-07 00:34:31 +08:00
@SoloCompany 取下整就不是随机了，各点不是等概率的
|
|
5
9hills 2013-12-07 00:36:37 +08:00
@SoloCompany 这样最后应该是一个正态分布的概率图
|
|
6
SoloCompany 2013-12-07 00:40:00 +08:00
@9hills 我错了，简单验算一下，实验 n 次的结果数是 5 ^ n 不可能整除 7，可以推断是无法得到真随机的 rnd7()，但非常逼近还是可以的
|
|
7
9hills 2013-12-07 00:41:39 +08:00
@SoloCompany 不考虑取整。。你这个实际概率分布是正态分布啊<_<
|
|
8
SoloCompany 2013-12-07 00:48:20 +08:00
@9hills 我的意思已经不是相加了，是n阶矩阵，然后对结果数分类，由于不能整除7，算法总是会有一个余数存在，不能完全实现 rnd7()
以n=4为例，5^4=625 = 7*89 + 2 可以把625个结果按89个结果分类，落在这些结果中就取对应的值。但剩下2的区间就无法覆盖，就是说有 2/625 的偏差 |
|
9
SoloCompany 2013-12-07 00:56:17 +08:00
基于这个思路可以完善那个递归算法，先根据区间划分，然后进行实验
每次递归如果得到的4个rand5()结果落在 623 个结果内，就可以直接返回结果 如果不幸落在那 2 个结果里面，需要重复实验（也就是递归调用） 可以限制一下递归次数（比如10），如果10次随机数返回都落在那个2里面（这个几率很低了），就直接返回0 |
 |
10
suriv520 OP @SoloCompany 摔！为毛v2ex没有回复提醒……
是的。我凭感觉也认为没有能在确定步骤内的得到结果的算法。或者说，理论上通过一元运算或二元运算，也无法将概率区间一一映射。 但貌似没办法给出严格意义上的证明…… |
 |
11
regmach 2013-12-08 04:59:19 +08:00
插一个问题,怎么得到rand3() ?`
|
Select Language