Chinaunix

标题: 已知一个函数f可以得到1-5间的随机数，问怎么得到1-7的随机数 [打印本页]

作者: glq2000 时间: 2010-07-06 18:36
标题: 已知一个函数f可以得到1-5间的随机数，问怎么得到1-7的随机数
本帖最后由 glq2000 于 2010-07-06 20:18 编辑

在 http://blog.csdn.net/DKarthas/archive/2007/11/05/1868212.aspx看到一个面试题，博主只是提出了问题，没有给出解答，所以在这发一下，希望知道解的tx解答下：）

问题：

已知一个函数f可以等概率的得到1-5间的随机数，问怎么等概率的得到1-7的随机数，

这个问题是有解的么？若无解，说明原因，若有解，那解是什么？

(该问题已解决，剧透一下，正解在17楼~~~~~~~~)

作者: evaspring 时间: 2010-07-06 18:41
本帖最后由 evaspring 于 2011-02-19 23:49 编辑

占着沙发这样好的位置当然要作点贡献，公布下比较接近标准的答案：

算法思路是：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3

int rand7()
{
int a;
while( (a=rand5()*5+rand5()) > 26 );
return (a-3)/3;
}

复制代码

或者

int rand7()
{
int sum = 0;
for(int i=0; i<7; i++)
{
sum += ( rand5() - 1 ) * pow(5,i) ;
}
return (sum%7+1);
}

复制代码

作者: iamxmz 时间: 2010-07-06 18:53
本帖最后由 iamxmz 于 2010-07-06 19:18 编辑

运行7次f()加起来除5

写完之后想了一下,7只会出现一次,前边的数都会出现很多次,这个不对.

作者: glq2000 时间: 2010-07-06 18:55
回复 2# evaspring

f()+f()%2 的取值范围是 1到6啊

后来我改为 f()+f()%3，这样取值范围倒是1到7了，但取七的概率是

前面需要为5，后面需要为2或者5，所以 1/5 * 2/5 = 2/25, 也不是1/7，满足不了等概率的条件。。。。。。。。。

作者: egmkang 时间: 2010-07-06 18:55

f() + f() % 2
evaspring 发表于 2010-07-06 18:41

这个好像不是平均分布的把

作者: glq2000 时间: 2010-07-06 19:01
回复 2# evaspring

f()随机返回1-5，那f()运行7次相加的话，再除以7的话，最大也就是 5*7/7 = 5, 根本取不到6和7啊。
如果你的意思是对7取余，即使先不考虑等概率，取余的结果中包含0，而要求是对1-7返回等概率，不包括0。

我感觉这个题是个数学题。。。。。。

作者: glq2000 时间: 2010-07-06 19:03
对，有两点要特别注意，一是等概率等返回1-7中的某个数，而是f()的取值是1-5，他可以等概率的返回一到五，现在要等概率的返回1-7，不包括0，

这个题目是有解的么？解是什么？无解的话，原因是？

作者: churchmice 时间: 2010-07-06 19:10
回复 6# glq2000

仔细看，人家是除以5

作者: iamxmz 时间: 2010-07-06 19:12
我改了,写错了,先写的除7.不过除5也不对,这样7只会出现1次.

作者: egmkang 时间: 2010-07-06 19:12
3楼是正解

作者: iamxmz 时间: 2010-07-06 19:14
f()运行7次加起来模7呢?我写个程序试试..

作者: glq2000 时间: 2010-07-06 19:19
回复 9# iamxmz

恩得到7的概率是7个1/5相乘, 而不是1/7. 我再怀疑这个题是不是没有解啊但又证明不了。。。。。。

作者: glq2000 时间: 2010-07-06 19:21
回复 11# iamxmz

模7的话有可能为0。。而要求是等概率的返回1-7，不包括0

ps, 好变态的题啊

作者: churchmice 时间: 2010-07-06 19:22
回复 9# iamxmz

嗯，的确那样产生是有问题的，我想想

作者: redspider 时间: 2010-07-06 19:25
rand() * (7/5)

作者: iamxmz 时间: 2010-07-06 19:26

回复 iamxmz

模7的话有可能为0。。而要求是等概率的返回1-7，不包括0

ps, 好变态的题 ...
glq2000 发表于 2010-07-06 19:21

我简略了一步而已,要得到A-B之间的数都是模(B-A+1)然后加A的,具体到这个题上就是模7然后+1.

最新结果,分布还是不平均,误差在0.2%左右.

作者: churchmice 时间: 2010-07-06 19:45
本帖最后由 churchmice 于 2010-07-06 19:47 编辑

from
http://www.mitbbs.com/article_t/Quant/31188147.html

基本方法就是产生一串序列
1,4,5,3,2,4
然后前后两两划分为一组，比如(1,4),(5,3)，因为总共有5X5 =25种等概率的可能，不能被7整除，可以拿掉4种，这样剩下21种，编号为#1,#2,...#21
如果出现#1,#2,#3则输出1，....如果出现#19,#20,#21则输出7，如果出现了被拿掉的那4种情况则忽略之

作者: glq2000 时间: 2010-07-06 20:05
17楼是正解，多谢 churchmice iamxmz等人的解答 ~~~~~~~~

作者: zy31887493 时间: 2010-07-07 13:26
提示: 作者被禁止或删除内容自动屏蔽

作者: egmkang 时间: 2010-07-07 13:30

from

基本方法就是产生一串序列
1,4,5,3,2,4
然后前后两两划分为一组，比如(1,4),(5,3)，因为总共有 ...
churchmice 发表于 2010-07-06 19:45

恩,这个NB

作者: rain_fish 时间: 2010-07-07 13:37

from

基本方法就是产生一串序列
1,4,5,3,2,4
然后前后两两划分为一组，比如(1,4),(5,3)，因为总共有 ...
churchmice 发表于 2010-07-06 19:45

顶！！！

作者: goubao198562 时间: 2010-07-07 14:51
本人比较愚笨忽略的四种情况出现的概率是4/25 是不是也这1-7的概率并不是很平均阿如果当前随机结果就是这4/25中的一个那这次随机的数字该是哪个？

作者: zy31887493 时间: 2010-07-07 14:55
提示: 作者被禁止或删除内容自动屏蔽

作者: goubao198562 时间: 2010-07-07 15:04
回复 20# zy31887493

（ 1 2 3 4 5 ）与（1 2 3 4 5）两两组合总共是5*5种 1*1 1*2 1*3 1*4 1*5 2*1 2*2 2*3 ... 5*5这25种

作者: zy31887493 时间: 2010-07-07 15:55
提示: 作者被禁止或删除内容自动屏蔽

作者: bruceteen 时间: 2010-07-07 23:35
本帖最后由 bruceteen 于 2010-07-07 23:37 编辑

看了大家的讨论，俺就着大家的思路也写了一个（但有所变形），不知道变形后的思路是否正确，错了就丢人了

int rand7()
{
int a;
while( (a=rand5()*5+rand5()) > 26 );
return (a-3)/3;
}

算法思路是：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3

作者: peidright 时间: 2010-07-08 00:16
本帖最后由 peidright 于 2010-07-08 00:19 编辑

。。。我弄错了

作者: noword2k 时间: 2010-07-08 09:02

看了大家的讨论，俺就着大家的思路也写了一个（但有所变形），不知道变形后的思路是否正确，错了就丢人了
...
bruceteen 发表于 2010-07-07 23:35

rand5()*5+rand5() 不就是rand5()*6吗？

作者: goubao198562 时间: 2010-07-08 09:44
回复 27# bruceteen

我想知道怎样舍去四个数不影响概率的你的思路跟十七楼大体上部是一样吗

作者: churchmice 时间: 2010-07-08 10:20
回复 18# glq2000

http://www.google.com/search?hl= ... mp;oq=&gs_rfai=

第一个就是

作者: churchmice 时间: 2010-07-08 10:24
http://fayaa.com/tiku/view/164/
这里还提供了其他一些方法

作者: goubao198562 时间: 2010-07-08 10:33
这道题如果仅仅是取1-7的随机数那方法很多如果1-7随机数产生的概率一样的话目前大家找的答案我都还理解不了

作者: starwing83 时间: 2010-07-08 11:18
我之前想了个办法：调用f七次，每次都加5，这样第一次生成1~5内的数字，第二次生成6~10……第七次生成31~35，然后把七个数字加起来除以5……不知道成不成……

作者: benjiam 时间: 2010-07-08 14:01
那个网页打不开不知道他的算法是什么。

17 l 的做法其实还是有问题的是非等概率的。

因为% 7 的时候 0- 6 ，结果有3个被遗弃了所以是不准的

一个平面的话我有个简单的算法

5 + 5f() +f() 是在 11-35 之间均匀分布的. 可以证明的

但是要随机得到1-7 还是得不到。

算法的精要应该是 2点 f() 的计算结果集要求是均匀分布的。
第二起点落点要是 7的倍数

2 没做到。

作者: starwing83 时间: 2010-07-08 14:03
LS：是等概率的，可以证明。

作者: benjiam 时间: 2010-07-08 14:18
一个非7 倍数的区间产生的结果应该不是均衡的。抛弃的话，这个函数就会无法返回结果。无限的回调。

简单 %7 那么肯定是不均衡的了

作者: bruceteen 时间: 2010-07-08 14:20

rand5()*5+rand5() 不就是rand5()*6吗？
noword2k 发表于 2010-07-08 09:02

rand5()*5+rand5() 中 rand5() 和 rand5() 是不一定相等的，它是随机数，每次的返回值都是随机的

作者: benjiam 时间: 2010-07-08 14:38

rand5()*5+rand5() 中 rand5() 和 rand5() 是不一定相等的，它是随机数，每次的返回值都是随机的
bruceteen 发表于 2010-07-08 14:20

握手我们2的算法是一样的。
但是可能无限回调。是不安全的

作者: churchmice 时间: 2010-07-08 14:54
回复 35# benjiam

问题反过来很简单，1-7的等概率产生1-5的等概率，直接f()-2就可了，如果结果小于等于零则舍弃。这样产生1-5的概率每个都是1/7，加起来总共是5/7，那剩下的2/7哪去了？当然是当结果小于等于零的时候给被丢弃掉了，但是产生的1-5还是等概率的。如果这一点理解了，那原题也不难理解，通过组合产生了25种等概率的事件，随便舍去4种，剩下的21种时间不仍然是等概率的么？每3个事件均对应产生同样的数字，所以产生的数字最后也是等概率的，为3/25,当然有4/25的概率被舍弃，需要重新生成一次

作者: snroman 时间: 2010-07-08 17:02
回复 1# glq2000

(f()-1)*6/4+1

作者: jerryz920 时间: 2010-07-08 19:58
本帖最后由 jerryz920 于 2010-07-08 20:34 编辑

这个其实和算法导论上的一个题很像么：已知random等概率返回0或者1，那么试写一个函数等概率返回[a,b]之间的整数。思路就是2进制表示[0, b-a]之间的数，先计算出至少需要多少位，按位生成一个二进制数，一旦大于b-a就重新生成。放到这里的话，表示成5进制就可以了~

推广一下：对于等概率可以生成k个连续整数函数的函数randomk，设计生成[a,b]之间的整数的算法：
令n = b - a;则等概率生成[0，n]上的一个整数即可。于是用k进制表示生成的整数，设m=ceiling(logk(n)),

int randN() {
while (res > n) {
for (i = 0; i < m; i++)
gen bit i for res with randomk
}
return res;
}

复制代码

期望的运行时间为t*m* i * (1 - (n+1)/k^m)^(i-1) * ((n+1)/k^m)，i从1加到无穷，t表示randomk的运行时间，那么计算这个级数的值为t*m*k^m/(n+1).
带入到这个题目，期望运行时间为50*t/7，还是很快的。

作者: goldenfort 时间: 2010-07-09 09:34
讨厌讨论各种面试题，这些题目在某国好象都是类似于唐 jun ,这些能吹会拍的人出的，能有什么水平。可惜呀，好资源一半让狗占了。

作者: 奶茶dsk 时间: 2010-07-09 10:46
回复 42# jerryz920

高论

作者: goubao198562 时间: 2010-07-09 11:10
回复 40# churchmice

照这种理论我是不是可以认为如果一个函数能随机生成[1,N] 那这个函数不用改变只要舍弃某些值也就能随机生成[1,M] (其中M < N)

作者: bruceteen 时间: 2010-07-09 14:45
题目是从CU上看到的，我的算法是：
int rand7()
{
int a;
while( (a=rand5()*5+rand5()) > 26 );
return (a-3)/3;
}
可惜没办法验证，不知道这个算法是否正确？（问题一）。
（验证方法是通过双循环将两个rand5()分别换成1 2 3 4 5，但剔除掉(5,2)(5,3)(5,4)(5,5)这四个组合）

算法思路是：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3

注：
我觉得不能将 while( (a=rand5()*5+rand5()) > 26 ) 其中一个rand5()移到while之外，即不能写成
int b = rand5();
int a;
while( (a=b*5+rand5()) > 26 ); 或 while( (a=rand5()*5+b) > 26 );
因为出现 >26 的情况，说明 b 有很大机率很大，从而又导致while之后的a有很大机率很大，破坏了平衡性。
这个备注中的看法对么？（问题二）

但，令人惋惜的是，这不是一个严格意义上的算法，因为“计算机算法”比“数学上的算法”多两个限定，是“有限时间有限步骤内……”，而while( (a=rand5()*5+rand5()) > 26 )可能会循环超过可忍耐次数，即某次运行这段代码可能到地球灭亡时还没结束，虽然几率很低，但有可能发生。

------------------------------------------------------------------------------------

google了一下，找到另一种方法：（本质和上面的算法相同，但要使得第二步不产生多余的数）
找到一个五进制的数 444…4，这个数正好能被7整除
于是他找到444444（五进制）这个数，也就是15624
产生nnnnnn（五进制）的方法很简单，就是每位都通过rand5-1来产生
然后将nnnnnn%7+1就得到了均匀分布于1到7的算法。

这个算法是错误的，因为 444444（五进制）内包含有15625个数，不是15624个数，前者不是7的整数倍。
用我的变形算法来描述就是：
通过 r*5^0 + r*5^1 + r*5^2 + r*5^3 + r*5^4 + r*5^5 产生 3906 到 19530 共15625个数的均匀分布，可惜15625不是7的整数倍，还是需要舍弃掉最后一位。作者错误在于马虎的认为 0至n 内有n个数，其实是n+1个数。

虽然作者的结果是错误的，但思路是正确的，只要能找到一个数n，使得 4 + 4*5 + 4*25 + 4*125 + 4*625 + 4*3125 + …… 的结果加一后是7的整数倍。
我用代码暴力求解，在数据溢出之前都没找到这个数。于是从理论上分析，444…4（五进制）+1 也就是 5的x次方，永远不可能是7的倍数。

还google到其它一些巧妙的算法，但可惜作者并没有真正理解“随机”的概念。

------------------------------------------------------------------------------------

思考一下 rand5()+rand5()，将产生 1/25个2，2/25个3，3/25个4，4/25个5，5/25个6，4/25个7，3/25个8，2/25个9，1/25个10。
如果能找到一个公式，使之产生一系列不同几率的数，将这些数分成7组，使得每组数的几率总和为1/7就可以了。
假设这个公式f需要n个rand5()为自变量，则最多产生5^n个数，不是“最多”的情况说明不同参数组合产生了相同的数，无论是不是“最多”的情况，都可以证明每个数的几率都必然是 1/(5^n) 的整数倍。
那么无论怎么分组，每组数的几率总和都应该是 m * 1/(5^n)。
求 m/(5^n) = 1/7 的整数解，即求 5^n = 7m 的整数解，很显然是无解的。（前者的个位数不是0就是5，而后者的个位数不可能是0或5）
因此自此证明这个问题是无解的。

作者: churchmice 时间: 2010-07-09 19:11
回复 45# goubao198562

当然可以

作者: klyh305 时间: 2010-07-10 09:25
17楼：
是不是可以这样理解呢：随便从这25个二元组中选出七个，这七个每个出现的概率是1/25，将这七个数字分别对应到1-7，然后重复的执行(rand(), rand())，直到出现前面7个二元组中的一个，这时就产生了一个1-7之间的随机数，这些随机数是等概率的

作者: churchmice 时间: 2010-07-10 09:30
回复 48# klyh305

是的，只要是7的倍数个就可以了，所以要舍弃掉一些值

但是从效率方面来考虑的话还是舍弃尽可能少的值

作者: guoruimin 时间: 2010-07-10 09:54
本帖最后由 guoruimin 于 2010-07-11 16:11 编辑

回复 17# churchmice
17楼的算法，确实是真正随机的，却不是严格的算法。
致命的漏洞是当出现的组合不符合条件时，重新生成！
从概率上来讲：重新生成符合条件的组合需要一万年，也是可能的。
所以是不可靠的算法！

有 1 - 5 之间的随机数 n1, n2, ... n7
则有 7 - 35 之间的随机数 m = n1 + n2 + ... + n7
则有 1 - 7 之间的随机数 k = m / 5

该算法始终稳定在 rand 7 次！

但该算法似乎不是真正随机的。
中间的几个数出现的概率比较高吧？

作者: churchmice 时间: 2010-07-10 10:40
本帖最后由 churchmice 于 2010-07-10 10:45 编辑

回复 50# guoruimin

侬说的对，凡事讲概率，那你可以计算一下，由于是25种情况种舍弃了4种，所以舍弃的概率是4/25

那么我连续舍弃100次的概率是多少？ (4/25)^100
连续舍弃1000次呢？这概率是多么的小啊，舍弃这么多次对于现代的计算机来说只是瞬间的事情，所以不存在性能的问题
如果恰如你所说，这个算法不幸的连续舍弃了n次，导致需要运行个1万年才能出结果，你可以去算算这个时候的n值是多大，对应的概率是多小？
这世界上没有100%会发生的事情，计算机中硬盘挂掉，cpu计算出现错误都有一个概率，就连寄存器（硬件）也会有一个meantime to work,也就是能够正常工作的概率。

照你这么说密码学都不用搞了，比如密钥是128位，那我随便猜一个也有1/(2^12

的概率命中
但实际中的情况时，如果一个事件发生的概率很小（究竟多小算小要根据实际应用场景确定），我们就认为它不会发生，就可以放心的去用

反观你这个算法

有 1 - 5 之间的随机数 n1, n2, ... n7
则有 1 - 35 之间的随机数 m = n1 + n2 + ... + n7
则有 1 - 7 之间的随机数 k = m % 7 + 1

要证明k是等概率的有两种情况：
1. m是等概率分布在1-35之间，这个是不可能的
因为根本没有任何可能使得m=1
2.m在1-35之间的分布不是等概率的，但是经过m%7 + 1的操作后成为了等概率，那可以算一下
k=1要求: m=0,7,14,21,18,35
m=0 的概率为0
m=35的概率为 (1/5)^7
其余几种我没算过，但是你要这玩意加起来等于1/7，我认为很悬

作者: bruceteen 时间: 2010-07-10 14:26
re 楼上：你混淆了现实中的“小概率”概念，和计算机中的“算法”概念

无论你说的概率有多小，都是一个非0的概念，那么它就违背了计算机算法的定义。

“计算机中硬盘挂掉，……” ------ 在计算机算法中对计算机的定义是运行无误的，但有时间和能量供应的限制。你不能要求一个算法可能会运行操过可接受的时间（比如到宇宙灭亡），也能要求一个算法可能会用掉可接受的能量（比如整个太阳系的能量）。
假如你还不理解，那么我给你一个 int main() {return 0; } 你认为这么代码正确吗？按照你的逻辑，那就是这么代码不能100%正确，因为运行期间可能停电，计算机中硬盘挂掉，cpu计算出现错误都有一个概率，……
而我认为的，“计算机中硬盘挂掉，……”和这段代码是否正确无关。我说的是代码正确性，不是某次程序是否能执行成功。即使某次因为硬盘挂掉而运行失败，这段代码依然是100%正确的。

“比如密钥是128位，那我随便猜一个也有1/(2^12的概率命中” ------ 你说得很正确，但我所知的所有加密算法定义都不是要求0%命中，而是要求低于某个实际的安全值。当然，如果你一定要篡改某加密算法的定义为0%命中，那么次密码算法自然是错误的。

作者: jerryz920 时间: 2010-07-10 16:30
对死抠定义的表示无语。那么修改一下好了，运行10000次还没有产生要求的随机数，那么随便挑个在(1-7）之间的数。从计算机的角度来看，这会已经看不出来有什么概率上的差别了~其实随机算法之所以随机，就是因为它关注的不是最差的情况下是怎么样的，而是关心的期望的效率是怎么样的。当然如果你可以证明如果使用伪随机的一个序列可以导致这个算法无解，那么另当别论。

作者: guoruimin 时间: 2010-07-10 16:38
回复 51# churchmice
我的方法只是一种思路，提出时我就指出了：可能不是真正随机的。没有时间细想了。
只是想讨论一种真正严格的算法。
或许这个题目是无解的！

作者: bruceteen 时间: 2010-07-10 17:41

对死抠定义的表示无语。那么修改一下好了，运行10000次还没有产生要求的随机数，那么随便挑个在(1-7）之间的 ...
jerryz920 发表于 2010-07-10 16:30

“那么随便挑个在(1-7）之间的数” ------ 随机和均值的概念不同
随机：当你抛硬币，连续10000000000000000次都是正面朝上，第10000000000000001次反面朝上的概率还是只有1/2
均值：当你第一次取得A，则第二次取得B的几率比取得A的几率高；如果第二次还是取得A，则第三次取得B的几率会更高……

“对死抠定义的表示无语” ----- 什么叫“死抠定义”？如果你连“计算机算法”这个定义都可以抛弃的话，那你不如直接将题目中“随机”的概念改为“伪随机”，这样问题变得更简单，直接用C库中的rand()函数来实现。

A: 已知一个人被雷电劈中的几率是a，一个人中六合彩的概率是b，请问即中六合彩又遭雷劈的概率是不是a*b？
B: 不是a*b，是0，因为两者概率都极低，相乘后更低，所以是0而不是a*b。
A: 我问的是数学上的几率概念
B: 对死抠定义的你表示无语：（
A: ……-_-!!……

作者: bruceteen 时间: 2010-07-10 17:46

回复 churchmice
我的方法只是一种思路，提出时我就指出了：可能不是真正随机的。没有时间细想了。
只是 ...
guoruimin 发表于 2010-07-10 16:38

你的思路确实是无解的，因为每个数的出现几率的最小粒度是1/5^n，在整数范围内无解

作者: bruceteen 时间: 2010-07-10 18:04
是不是一个严格的计算机算法和能不能在实际生活中使用是两个不同点。
很多严格的计算机算法并不能在实际生活中使用，实际生活中使用的好多不是严格的计算机算法，比如GUID生产算法。

不能因为windows有bug，就认为windows不可以使用；不能因为windows被使用着，就认为windows无bug。两个完全不同的概念，不要混为一谈

两个概念都有其适用范围，我也可以列举一个相冲突的例子：
hash表的统计学效率比平衡二叉树高，但在要求实时的算法片段中（“实时”的概念不是要求响应速度快）从来不用hash表，因为hash表可能在某次操作时花费超额的时间。

作者: gcd0318 时间: 2010-07-10 19:56
本帖最后由 gcd0318 于 2010-07-10 20:01 编辑

纯数学意义上，只要1＋7＊（f－1）／5就可以了，但是在计算机上实现的话，要考虑小数精度，味道就变了，这才是有必要讨论的余地所在
不知道ls的大部分人为什么把话题扯到那么远

作者: keithnwsuaf 时间: 2010-07-10 20:11
应该可以用二元一次方程解决吧，而且多解！

作者: bruceteen 时间: 2010-07-10 20:25
纯数学意义上，只要1＋7＊（f－1）／5就可以了
不知道ls的大部分人为什么把话题扯到那么远
------ 因为他们看到的题目是“1-5间的随机数”，而你看到的是“1.0-5.0间的随机数”，讨论的题目不一样呀：）

作者: mike79 时间: 2010-07-11 13:52
连续7次调用，把所有返回值相加后模7？

作者: gcd0318 时间: 2010-07-11 15:54
回复 60# bruceteen

你的意思是说必须整数？那么此题无解
我可以给出数学证明

作者: bruceteen 时间: 2010-07-11 16:11
回复 62# gcd0318
你是怎么证明的？如果不介意的话，教教我吧

我原先的证明方法是：
立出所有可能的运算符，比如+ - *等，因为rand5的几率为1/5，所以+ - * 等的几率“最小粒度”为1/5^n
当然运算符还有/等等，但用/等时需要有限制，不能产生小数。这样的话就可以将/变形为*a*1/5，根号等操作亦然。
即无论给出的公式是如何的复杂，其结果都应该是1/5^n的整数倍。（n可以取任意整数）
m / 5^n = 1/7 在整数范围内无解

昨天想出了一个更直观的证明方法，直接用几率参与运算
因为几率的运算符，只有+ - * max min等有限的几个，而且都可以转化为*操作。另外100%可以转化为1/5+1/5+1/5+1/5+1/5，200%可以转化为2*1
所以1/5^n粒度的几率无论怎么参与计算，其结果都可以化简为m / 5^n
m / 5^n = 1/7 在整数范围内无解

假如可以引入极限的话，要想使得 m / 5^n = 1/7 有解，只有当n是无穷大时

作者: bruceteen 时间: 2010-07-11 18:02
本帖最后由 bruceteen 于 2010-07-11 18:10 编辑

我收回上面的证明方法，不但繁杂，而且还有一个画蛇添足引出的bug

我现在的证明方式是：
任意一个含有n个自由度为5的自变量的公式，无论多么稀奇古怪，都将产生5^n个值，虽然某些值可能相同。
5^n 不可能是 7 的倍数。（前者个位数为5，后者个位数不可能是5）

作者: bigCiCi 时间: 2010-07-11 22:05
1.5*f()-0.5

大家觉得这样对不对？
出来的是1~7之间的随机数，且为均匀分布（因为f()为均匀分布）

作者: snroman 时间: 2010-07-11 22:11
回复 2# evaspring

如果是随机整数的话算法比较麻烦，近似的可以有取整整函数:

(f()+f()+f()+f()+f()+f()+f())/5

作者: 深蓝苹果 时间: 2010-07-13 14:03
本帖最后由深蓝苹果于 2010-07-13 14:24 编辑

回复 1# glq2000

做一个区间映射不就行了。。。

(f() - 3) * 3/2 + 3

不过这样做离散度肯定会加大

作者: glq2000 时间: 2010-07-13 16:30
回复 32# churchmice

恩在看多谢~~~~

作者: linzhoulxyz 时间: 2010-07-14 14:18

高手，学习了

作者: zbhddt6 时间: 2010-07-23 20:07
生成随机数一到七，实际就是随机生成一个数，由三个bit组成，能从1-5随机生成0-1就可以的了，（这个可以随机生成0-7----如果为0继续生成一次，直到非零就生成1-7的随机数了）
函数随机值缩小，
func_1_7()
{
i = func_0_7();
while(i==0) {i= func_0_7();}
return i;
}

func_0_7()
{
i = 0;
i |= func_0_1();
i |= func_0_1()<<1;
i |= func_0_1()<<2;
return i;
}

func_0_1()
{
do{
i=func_1_5();
}while (i==5)
return i%2 - 1;
}

作者: davelv 时间: 2010-07-23 20:42
这种等概率随机问题在算法导论上有讲到

设一个随机函数rand()可以生成[0,MAX)的等概率随机数，求[N,M)的等概率随机数公式如下
( rand() / ((double)(MAX)) ) * (M-N) + N

作者: wenkai169 时间: 2010-07-26 21:44
想想

作者: gcd0318 时间: 2010-07-30 17:37
回复 63# bruceteen

你好，我也应该收回一下……其实当时我只是大致的在集合的cardinality上考虑了一下，觉得两个集合应该相同才有可能，如果是实数范围内，那么[0，5]和[0，7]是相同的，但是{0，1，2，3，4，5}和{0，1，2，3，4，5，6，7}肯定是不同的，所以应该不存在一个满单射（1-1 & onto），那么，如果原像集是等概率随机的，则象集无法做到等概率随机
从映射关系上，5元集合A到7元集合B的映射，根据鸽笼原理，必然存在至少1个原象映射到至少2个象上……这句话说的比较13，简单点就是说，A里至少有一个数要和B里的两个数对应起来，那么如果A是等概率随机，A中的a1对应到B中的b1和b2，其他都是1对1，那么b1和b2的概率必然比其他几个bi要低
大致是这么个思路，但是严谨的证明……我还得再想想

作者: gcd0318 时间: 2010-07-30 17:38
回复 72# davelv

您和我出的是一个错，人家要整数

作者: gcd0318 时间: 2010-07-30 17:42
回复 67# bigCiCi

哦，您这个说法有理，但是所谓的舍弃，如果中间有值落下去怎么办

作者: davelv 时间: 2010-07-30 19:02

回复 davelv

您和我出的是一个错，人家要整数
gcd0318 发表于 2010-07-30 17:38

那么只需在最后结果上int取整即可。

作者: gcd0318 时间: 2010-08-01 12:48
回复 77# davelv

直接取整的话，应该不是等概率的，您再想想看对不对？

作者: davelv 时间: 2010-08-01 17:53
本帖最后由 davelv 于 2010-08-01 18:00 编辑

回复 78# gcd0318

不会的，我的[N,M)是半开半闭区间。
一个强制取整就是把小数的[0,1),[1,2),...,[M-1,M)这M个分区间之顺序集合变成了自然数顺序集(0,1,2,...,M-1)，也就是[0,M)整数区间。由于[0,M)是均匀的的，所以每个分区间是均匀的，所以取整后的区间也是是均匀的。

作者: gcd0318 时间: 2010-08-01 23:48
本帖最后由 gcd0318 于 2010-08-01 23:50 编辑

回复 79# davelv

我明白你的意思，但是区别在于，原题中的f如果只能等概率的在5个整数之间取随机数，那么最后映射到子区间，也只能落在5个区间内，所以要把［1，7）分成5个子区间，必然有至少一个子区间内的整数多于1个，或者把5个点变成7个区间，那么也就必然至少有一个区间里没有整点
当然了，如果改造f，那确实可以达到目的

作者: davelv 时间: 2010-08-02 09:17

回复 davelv

我明白你的意思，但是区别在于，原题中的f如果只能等概率的在5个整数之间取随机数， ...
gcd0318 发表于 2010-08-01 23:48

原来它1-5区间也是整型阿，这样子的确会有问题呢。看来我犯错误了，认真看看前人回帖吧！谢谢指点

作者: gcd0318 时间: 2010-08-02 12:42

原来它1-5区间也是整型阿，这样子的确会有问题呢。看来我犯错误了，认真看看前人回帖吧！谢谢指点
davelv 发表于 2010-08-02 09:17

应该是，所以我觉得您和我犯的是一个错，我现在开始倾向于无解了

作者: bigCiCi 时间: 2010-09-17 21:50
回复 76# gcd0318

因为舍弃的概率是0.16，如果正好落到了这个概率那么就舍弃，这样，连续出现舍弃的概率是很小的，连续舍弃3次的概率为0.004096。。。。

不好意思最近没上cu 回复的晚了:wink:

作者: johnniecheng052 时间: 2010-09-27 15:36
同上

作者: ping222s 时间: 2011-01-29 02:31
运行7次除以5。。。行不行？？？

作者: cjaizss 时间: 2011-01-29 08:50
本帖最后由 cjaizss 于 2011-02-15 23:10 编辑

我越来越倾向于这是一个抽象代数题,答案是得不到吧,需要建模吧.
作为面试题似乎不太合适
还是补全这个说明吧：取部分样本来作为样本空间的做法……可能永远不会结束，不同于我们平常所说的算法。

作者: ypzhou25 时间: 2011-01-29 09:56

作者: mubuntuy 时间: 2011-02-15 23:03
顶三楼。

作者: lbiiun 时间: 2011-11-30 11:25
本帖最后由 lbiiun 于 2011-11-30 11:26 编辑

把随机生成的1~5减一，得到等概率的0~4。　　运算7次加起来 % 5。　变成0~6的随机值。　再加一。　　取得1~7的随机值。
g++ -o rand rand.cpp
[root@rhel5 test]# ./rand
19991809 20002464 19996255 20002461 20007011
2040299 2041333 2041300 2040076 2041494 2041305 2039907
[root@rhel5 test]# cat rand.cpp
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
int r = 0;
int i = 0;
int j = 0;
int s = 0;
unsigned long a5[5] = {0};
unsigned long a7[7] = {0};

for (i = 0; i < 100000000; i++)
{
      r = rand() % 5;
      a5[r]++;
      s += r;
      if (++j >= 7)
      {
         j = 0;
         s %= 7;
         a7++;
      }
}
for (i = 0; i < 5; i++)
      cout << a5 << " ";
cout << endl;

for (i = 0; i < 7; i++)
      cout << a7 << " ";
cout << endl;
return 0;
}
这段结果在一定程度上说明了生成的1~7是等概率的。

虽然五次运算结果加起来不是等概率的。但我感觉
0 + 7 + 14 + 21 +28
1 + 8 + 15 + 22 + 29
....

这七组概率分别加起来，概率应该是相等的。
作者: ecloud 时间: 2011-12-16 22:45
F()7次相加，结果写成7进制数，然后只取个位就可以了
作者: hbmhalley 时间: 2011-12-16 22:52
回复 3# iamxmz

3L正解，(f()+f()+f()+f()+f()+f()+f()-1)/5+1即可
作者: A.com 时间: 2011-12-17 18:07
本帖最后由 A.com 于 2011-12-17 18:23 编辑

嗯，这个无解
作者: gentoo_fly 时间: 2011-12-18 23:14
这种问题没多大的意思，有点玩智商测试的味道，
现实的话，还是重新写一个函数，为什么非得调用那个函数啊
作者: gentoo_fly 时间: 2011-12-18 23:41
这种问题没多大的意思，有点玩智商测试的味道，
现实的话，还是重新写一个函数，为什么非得调用那个函数啊
作者: tcwm1_cu 时间: 2012-02-09 12:54
本帖最后由 tcwm1_cu 于 2012-02-10 09:48 编辑

编辑掉自己愚昧的言论
作者: cokeboL 时间: 2012-03-23 18:51
本帖最后由 cokeboL 于 2012-03-23 18:53 编辑

の
作者: x5miao 时间: 2012-03-23 19:48
只要一个函数可以随机产生1和0，就可以随机产生任何数字。
作者: slucx 时间: 2012-03-31 18:52

churchmice 发表于 2010-07-06 19:45
from
http://www.mitbbs.com/article_t/Quant/31188147.html

这个拿出了4种后还是等概率事件吗？
求解
作者: ethantsien 时间: 2012-05-17 11:25
为什么17楼是正解，出现了那4中情况就忽略之？一个取随即数的函数，能出现取不到的情况吗？
作者: maximdx 时间: 2012-05-22 16:12

ethantsien 发表于 2012-05-17 11:25
为什么17楼是正解，出现了那4中情况就忽略之？一个取随即数的函数，能出现取不到的情况吗？

如果取到了那4种情况中的任何一个，就放弃重来，这实际上就相当于缩小总体的样本。
不过我不明白为什么要减少4种情况，我觉得这样更加合理：
只考虑以下7种情况分别对应1-7：
(1,1), (1,2), (1,3), (1,4), (1,5), (2,1), (2,2)
剩下的出现就全部放弃重来。和17楼的方法相比，这样就省掉了18种情况，岂不是来得更方便？
作者: fallening_cu 时间: 2012-05-23 07:15
f 可以产生　１-５　之间的数字，因此可以调用用　f 多次来产生　５　进制的数字，只要取某个子集作为样本空间就可得到　１-７　之间的随机数。

比如说：　应用　f 两次，得到数字　ab，　翻译成　１０　进制就是　(a-1)*5+(b-1)，取值范围在　[０，２４］，只要使用其子集　[０,６]　即可映射产生　１-７　之间的随机数，如果　(a-1)*5+(b-1) 不在[0,6] 之间，则一直重复这个过程直到　(a-1)*5+(b-1) 落在　[0,6] 之间；　当然使用子集[1,7]也可以，直接就可以不用映射了。使用更长的子集　[0,13]　让两个数字映射一个随机数也可；　１７　楼的解法是使用了长度为　２１　的一个子集。如果应用　f 三次则有更多的子集可以选择；而且使用的子集越长，产生的随机数被　reject 的几率就更小。　比如应用　f　二十三次，得到数字　abcd....xyz, 转换成十进制，取值可在　[0,11920928955078124], 而如果选择子集为　[0,11920928955078121] (11920928955078121=1702989850725446*7-1)，则执行一次被拒绝的概率大致为0.00000000000000025166，而应用　f 两次使用长度为２１　的空间，执行一次被拒绝的概率是 0.16
作者: cobras 时间: 2012-06-03 01:00
只有缩小样本一种算法可行，运行7次除5在边界上有问题，不是等概率的。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2