BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ beyond (囧RZ) 于 (Sun Dec 19 09:46:24 2010) 提到: 假设知道rand5()函数（等概率随机生成1-5），如何写rand7()函数（等概率随机生成1-7）？ ☆─────────────────────────────────────☆ Guilt (恶魔) 于 (Sun Dec 19 09:58:04 2010) 提到: (rand5()-1)/4*6+1 感觉是这样的。。 ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Sun Dec 19 12:53:42 2010) 提到: 你这个俨然不正确... 这个问题有个很通用的解... 先构造一个等概率产生0和1的函数... int Rand() { int i=rand5(); if(i>=4) return 0;//2/5的概率返回0 else if(i<=2) retrun 1;//2/5的概率返回1 else retrun Rand();//再次调用,1/10的概率返回0或1 } 然后构造等概率产生1-7的函数... int rand7() { int result=0; for(int i=0;i<3;i++) { if(Rand()==1) result|=(1<<i); } if(result==0) return rand7(); return result; } 【在 Guilt (恶魔) 的大作中提到: 】 : (rand5()-1)/4*6+1 : 感觉是这样的。。 ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sun Dec 19 12:58:24 2010) 提到: 为何不对……… 他（rand5-1）/4产生的不是随机0-1的数么？【在 shenlei (我爱果子|[路]|天山南北|潇湘隐士) 的大作中提到: 】 : 你这个俨然不正确... : 这个问题有个很通用的解... : 先构造一个等概率产生0和1的函数... : ................... ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sun Dec 19 13:01:43 2010) 提到: 而且lz没说随机生成1-7的是不是整数啊…… 【在 shenlei (我爱果子|[路]|天山南北|潇湘隐士) 的大作中提到: 】 : 你这个俨然不正确... : 这个问题有个很通用的解... : 先构造一个等概率产生0和1的函数... : ................... ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Sun Dec 19 13:05:25 2010) 提到: 0或1乘6再加一只能得到1和7... 还有就是产生五个随机数的函数怎么能线性计算得到7个数?... 【在 renne (歼灭天使玲) 的大作中提到: 】 : 为何不对……… : 他（rand5-1）/4产生的不是随机0-1的数么？ ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sun Dec 19 13:05:33 2010) 提到: 题目不严谨啊…… 如果rand5产生的是1 2 3 4 5的话 rand5-1就是 0 1 2 3 4 然后除4就是 0 0 0 0 1了……肯定破坏随机性了那这样版主的解法才对如果rand5是[1-5]区间的话……应该那个做法对吧…… 【在 renne (歼灭天使玲) 的大作中提到: 】 : 为何不对……… : 他（rand5-1）/4产生的不是随机0-1的数么？ ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sun Dec 19 13:06:14 2010) 提到: 你理解的是0和1……我理解的是0到1…… 【在 shenlei (我爱果子|[路]|天山南北|潇湘隐士) 的大作中提到: 】 : 0或1乘6再加一只能得到1和7... : 还有就是产生五个随机数的函数怎么能线性计算得到7个数?... ☆─────────────────────────────────────☆ Guilt (恶魔) 于 (Sun Dec 19 13:08:50 2010) 提到: 【在 shenlei 的大作中提到: 】 : 你这个俨然不正确... : 这个问题有个很通用的解... : 先构造一个等概率产生0和1的函数... : ................... 我理解的也是连续的随机数。。不是离散的随机整数。。 ☆─────────────────────────────────────☆ FadeToBlack (口口口 <- codepage error again?) 于 (Sun Dec 19 13:09:11 2010) 提到: 你这种解法从randN()生产randX()要求X必须为2^M-1的形式咯？【在 shenlei 的大作中提到: 】 : 你这个俨然不正确... : 这个问题有个很通用的解... : 先构造一个等概率产生0和1的函数... : ................... ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Sun Dec 19 13:11:26 2010) 提到: 我看完想着如果是连续的就不难了...没有必要上来问...呵呵... 【在 Guilt (恶魔) 的大作中提到: 】 : 我理解的也是连续的随机数。。不是离散的随机整数。。 ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Sun Dec 19 13:12:29 2010) 提到: 也不必啊... 比如题目要求1-12,那个方法产生0-15,判断一下,不在要求范围内重新rand,反正1-12是等概率产生的... 【在 FadeToBlack (口口口 <- codepage error again?) 的大作中提到: 】 : 你这种解法从randN()生产randX()要求X必须为2^M-1的形式咯？ ☆─────────────────────────────────────☆ Guilt (恶魔) 于 (Sun Dec 19 13:15:45 2010) 提到: 【在 shenlei 的大作中提到: 】 : 我看完想着如果是连续的就不难了...没有必要上来问...呵呵... : 【在 Guilt (恶魔) 的大作中提到: 】 : : 我理解的也是连续的随机数。。不是离散的随机整数。。 : ................... 哈哈。。是我想当然了。。审题不认真的老毛病啊。。 ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Sun Dec 19 13:18:22 2010) 提到: 也可能是我错了呵呵... 【在 Guilt (恶魔) 的大作中提到: 】 : 哈哈。。是我想当然了。。审题不认真的老毛病啊。。 ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sun Dec 19 13:20:03 2010) 提到: 这题自己出的不严谨…… 【在 Guilt (恶魔) 的大作中提到: 】 : 哈哈。。是我想当然了。。审题不认真的老毛病啊。。 ☆─────────────────────────────────────☆ FadeToBlack (口口口 <- codepage error again?) 于 (Sun Dec 19 13:26:58 2010) 提到: 只有回答错的，没有题目错的。应该是此题分两种情况考虑，实数范围内blablabla，整数范围内blablabla ps. 不过要是面试官要求面试者，那就是题目考虑不全面了。具体得分两种情况考虑，看谁是刀俎，谁是鱼肉【在 renne 的大作中提到: 】 : 这题自己出的不严谨…… ☆─────────────────────────────────────☆ bupt070082 (Debug) 于 (Sun Dec 19 15:46:30 2010) 提到: 利用条件概率的概念p(y|x)=p(xy)/p(x)，(rand5(),rand5())可得到x-y平面25个等概率出现的坐标，取其中21个坐标，每三个映射为一个数。此时，p(x)=21/25,p(xy)=3/25,p(y|x)=1/7 int rand7() { complex<int> x; do { x=complex<int>(rand5(),rand5()); if(x==complex<int>(1,1)||x==complex<int>(1,2)||x==complex<int>(2,1)) { return 1; } else if(x==complex<int>(1,3)||x==complex<int>(2,2)||x==complex<int>(3,1)) { return 2; } else if(x==complex<int>(1,4)||x==complex<int>(2,3)||x==complex<int>(3,2)) { return 3; } else if(x==complex<int>(4,1)||x==complex<int>(1,5)||x==complex<int>(2,4)) { return 4; } else if(x==complex<int>(3,2)||x==complex<int>(4,2)||x==complex<int>(5,1)) { return 5; } else if(x==complex<int>(2,5)||x==complex<int>(3,4)||x==complex<int>(4,3)) { return 6; } else if(x==complex<int>(5,2)||x==complex<int>(3,5)||x==complex<int>(4,4)) { return 7; } } while (true); return 0; } ☆─────────────────────────────────────☆ Guilt (恶魔) 于 (Sun Dec 19 15:50:31 2010) 提到: 【在 bupt070082 的大作中提到: 】 : 利用条件概率的概念p(y|x)=p(xy)/p(x)，(rand5(),rand5())可得到x-y平面25个等概率出现的坐标，取其中21个坐标，每三个映射为一个数。此时，p(x)=21/25,p(xy)=3/25,p(y|x)=1/7 : int rand7() : { : ................... 惊现处女贴？ ☆─────────────────────────────────────☆ PeterKing (PeterKing) 于 (Sun Dec 19 16:43:52 2010) 提到: 【在 bupt070082 的大作中提到: 】 : 利用条件概率的概念p(y|x)=p(xy)/p(x)，(rand5(),rand5())可得到x-y平面25个等概率出现的坐标，取其中21个坐标，每三个映射为一个数。此时，p(x)=21/25,p(xy)=3/25,p(y|x)=1/7 : int rand7() : { : ................... 王振旺？牛人！！ ☆─────────────────────────────────────☆ math (3664.2436498) 于 (Sun Dec 19 18:49:01 2010) 提到: 这么做是对的，但代码写得有点繁琐，这么写就OK了 int rand7() { int r; while((r=(rand5()*5+rand5())/3-1) > 7) ; return r; } 【在 bupt070082 的大作中提到: 】 : 利用条件概率的概念p(y|x)=p(xy)/p(x)，(rand5(),rand5())可得到x-y平面25个等概率出现的坐标，取其中21个坐标，每三个映射为一个数。此时，p(x)=21/25,p(xy)=3/25,p(y|x)=1/7 : int rand7() : { : ................... ☆─────────────────────────────────────☆ math (3664.2436498) 于 (Sun Dec 19 19:02:47 2010) 提到: 此算法也是对的，但先从rand5()过渡到rand2()，平均需耗费1.25次调用rand5()，再从rand2()到rand7()需要3.43次调用，所以平均要4.3次调用rand5()函数，并不是最优的。【在 shenlei 的大作中提到: 】 : 你这个俨然不正确... : 这个问题有个很通用的解... : 先构造一个等概率产生0和1的函数... : ................... ☆─────────────────────────────────────☆ buptrh (【ipv6粉丝团】团帐房|emi大婶) 于 (Sun Dec 19 20:27:05 2010) 提到: 借楼再问个题。接到个题目要求到随机数，比如1-5随机吧，但是要严格等概率，用时间得出来的伪随机能算是严格等概率么？或者有其他更好的办法？ ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sun Dec 19 20:32:36 2010) 提到: 计算机有办法真随机么？【在 buptrh (【ipv6粉丝团】团帐房|emi大婶) 的大作中提到: 】 : 借楼再问个题。接到个题目要求到随机数，比如1-5随机吧，但是要严格等概率，用时间得出来的伪随机能算是严格等概率么？或者有其他更好的办法？ ☆─────────────────────────────────────☆ buptrh (【ipv6粉丝团】团帐房|emi大婶) 于 (Sun Dec 19 20:44:24 2010) 提到: 不知道，那个题目要求严格等概率，我也不知是不是真的随机。【在 renne 的大作中提到: 】 : 计算机有办法真随机么？ : 【在 buptrh (【ipv6粉丝团】团帐房|emi大婶) 的大作中提到: 】 : : 借楼再问个题。接到个题目要求到随机数，比如1-5随机吧，但是要严格等概率，用时间得出来的伪随机能算是严格等概率么？或者有其他更好的办法？ : ................... ☆─────────────────────────────────────☆ math (3664.2436498) 于 (Sun Dec 19 20:50:41 2010) 提到: 一般用线性同余法就足够对付很多应用了，用时间一般只是获得初始化种子。如果要通过很多复杂的独立性检验，线性同余法是不够的，可以参考Knuth的论著。如果只要平均分布这种检验，找一个素数做模就能满足要求。【在 buptrh 的大作中提到: 】 : 借楼再问个题。接到个题目要求到随机数，比如1-5随机吧，但是要严格等概率，用时间得出来的伪随机能算是严格等概率么？或者有其他更好的办法？ : -- ☆─────────────────────────────────────☆ math (3664.2436498) 于 (Sun Dec 19 20:56:48 2010) 提到: 能否真正随机对于应用来说其实不是那么重要，而且计算机算法无论多复杂也只能做到伪随机。最重要的是我们到底在关注什么，只要能通过独立性检验的伪随机函数就是满足我们需要的 ☆─────────────────────────────────────☆ buptrh (【ipv6粉丝团】团帐房|emi大婶) 于 (Sun Dec 19 21:53:43 2010) 提到: 好，谢谢，受教了。明天仔细研究下。【在 math 的大作中提到: 】 : 一般用线性同余法就足够对付很多应用了，用时间一般只是获得初始化种子。如果要通过很多复杂的独立性检验，线性同余法是不够的，可以参考Knuth的论著。如果只要平均分布这种检验，找一个素数做模就能满足要求。 : 【在 buptrh 的大作中提到: 】 : : 借楼再问个题。接到个题目要求到随机数，比如1-5随机吧，但是要严格等概率，用时间得出来的伪随机能算是严格等概率么？或者有其他更好的办法？ : ................... ☆─────────────────────────────────────☆ acde (nianqi) 于 (Mon Dec 20 11:00:21 2010) 提到: 太赞了，不过是不是应该是小于8呢？【在 math 的大作中提到: 】 : 这么做是对的，但代码写得有点繁琐，这么写就OK了 : int rand7() : { : ................... ☆─────────────────────────────────────☆ math (3664.2436498) 于 (Mon Dec 20 14:40:10 2010) 提到: 小于8就直接return了，大于7才需要继续取。【在 acde 的大作中提到: 】 : 太赞了，不过是不是应该是小于8呢？ : 【在 math 的大作中提到: 】 : : 这么做是对的，但代码写得有点繁琐，这么写就OK了 : ................... ☆─────────────────────────────────────☆ lthnainiu (闲步红尘) 于 (Mon Dec 20 23:53:38 2010) 提到: 【在 shenlei 的大作中提到: 】 : 你这个俨然不正确... : 这个问题有个很通用的解... : 先构造一个等概率产生0和1的函数... : ................... 我想弱弱的问一下 result|=(1<<i); 这个语句代表的是什么意思啊买没看懂|=和<<符号没理解上去 ☆─────────────────────────────────────☆ siwind (siwind) 于 (Sat Dec 25 11:08:31 2010) 提到: 这个是概率论的问题吧。随机变量 X 在区间[1,5]上服从均匀分布，随机变量 Y = (X/5)*7 在区间 [1,7]上服从均匀分布。 so , rand5()*7/5 ☆─────────────────────────────────────☆ siwind (siwind) 于 (Sat Dec 25 11:22:06 2010) 提到: 离散型随机变量 X 在均匀均匀的取值1,2,3,4,5 离散型随机变量 U = [X/2.5](取整)在0,1上均匀取值随机变量 Y = （U1 + U2 + U3 + U4 + U5 + U6 + U7）在1-7上均匀取值，其中U1-U7 和随机变量U同分布。 so , 代码.......... ☆─────────────────────────────────────☆ siwind (siwind) 于 (Sat Dec 25 11:24:32 2010) 提到: U = [X/2.5](取整)在0,1上均匀取值这个有问题， U不会在 0,1上均匀取值 ☆─────────────────────────────────────☆ siwind (siwind) 于 (Sat Dec 25 12:12:36 2010) 提到: 2L 正解 ☆─────────────────────────────────────☆ siwind (siwind) 于 (Sat Dec 25 12:50:00 2010) 提到: 离散的情况，我给个效率更高的算法： int rand7() { int result = 0; for(int i=0;i<2;i++) result = result*5 + rand5() -1; if( result >=21 ) return rand7(); return （result/3） + 1; } ====================================================== 改自19L的代码： int rand7() { int r; while((r=( (rand5()-1)*5+rand5()-1)/3 +1) > 7) ; return r; } ☆─────────────────────────────────────☆ renne (歼灭天使玲) 于 (Sat Dec 25 12:51:09 2010) 提到: 有人给过了…… 【在 siwind (siwind) 的大作中提到: 】 : 离散的情况，我给个效率更高的算法： : int rand7() : { : ................... ☆─────────────────────────────────────☆ stephenlaw (stephenlaw) 于 (Sat Dec 25 19:55:46 2010) 提到: 连续调用两次Rand5（），生成11代表1,12代表2，13代表3，以此类推，22代表7，剩下的情况排除。 ☆─────────────────────────────────────☆ siwind (siwind) 于 (Sun Dec 26 10:03:22 2010) 提到: nice ☆─────────────────────────────────────☆ arcsinxy (loser) 于 (Sun Dec 26 12:51:27 2010) 提到: 25种可能你排除掉18种，效率太低【在 stephenlaw 的大作中提到: 】 : 连续调用两次Rand5（），生成11代表1,12代表2，13代表3，以此类推，22代表7，剩下的情况排除。 : --

[合集] 问个笔试中遇到的随机数问题