r*******l
发帖数: 511 | 1 用rand5 产生 rand7
5*(rand5 -1) + (rand5-1)
为啥不直接5*rand5 to get < 25, then mod 7?
谁来说说 | x*****p
发帖数: 1707 | 2 5*rand5 mod 7 can only generate 0, 5, 3, 1, 6 and can not generate 2,4. | x*****p
发帖数: 1707 | 3 Even the formula
5*(rand5 - 1) + (rand5 - 1) mod 7
can not generate an evenly distributed rand7
Assume rand5 generates 1, 2, 3, 4, 5, we set X = rand5 - 1
and Y = rand5 - 1. Then we have the following table for 5X + Y mod 7
X Y 5X+Y
0 0 0
0 1 1
0 2 2
0 3 3
0 4 4
1 0 5
1 1 6
1 2 0
1 3 1
1 4 2
2 0 3
2 1 4
2 2 5
2 3 6
2 4 0
3 0 1
3 1 2
3 2 3
3 3 4
3 4 5
4 0 6
4 1 0
4 2 1
4 3 2
4 4 3
Thus in rand7, 0, 1, 2, 3 appears at probability 4/25, 4, 5 6 appears at
probability 3/25 | x*****p
发帖数: 1707 | 4 So if rand5 is iid, then it is impossible to generate rand7 also with iid. | r*******l
发帖数: 511 | 5 career cup经典题
答案也是标准答案
我就是没太明白
【在 x*****p 的大作中提到】
: So if rand5 is iid, then it is impossible to generate rand7 also with iid.
| l*******o
发帖数: 791 | 6 这样做行么？
unsigned short int rand_7()
{
bool high,middle,low;
high=rand5()>3?1:0;
middle=rand5()>3?1:0;
low=rand5()>3?1:0;
unsigned short int result=high*4+middle*2+low;
return result;
}
unsigned short int rand7()
{
unsigned short int res=rand_7();
while(!res)
{
res=rand_7();
}
return res;
} | s*****n
发帖数: 5488 | 7 这题以前有讨论。以前也没理解就是记住了。今天推了一下。
int rand7()
{
int a;
while( (a=(rand5()-1)*5+(rand5()-1)) > 20 );
return a/3 + 1;
}
trick是，第一次生成5*[0..4],第二次生成[0..4],so 所有可能组合是
0 0
0 1
0 2
0 3
0 4
5 0
5 1
5 2
5 3
5 4
10 0
10 1
10 2
10 3
10 4
.....
从而生成了0 到24的等概率随机数。除去后面4个不需要的数，就是0..20的随机数。
退而光之，如果用rand x 生成rand y,x如果小于y.那么
先构成(rand x -1)* x + rand x -1 的随进数先。因为rand x - 1正好落在前面的空
隙中，不会出现重复。
【在 x*****p 的大作中提到】
: Even the formula
: 5*(rand5 - 1) + (rand5 - 1) mod 7
: can not generate an evenly distributed rand7
: Assume rand5 generates 1, 2, 3, 4, 5, we set X = rand5 - 1
: and Y = rand5 - 1. Then we have the following table for 5X + Y mod 7
: X Y 5X+Y
: 0 0 0
: 0 1 1
: 0 2 2
: 0 3 3
| s*****u
发帖数: 15 | 8 5*(rand5 - 1) + (rand5 - 1) 必须是7的倍数时，才可以mod7得到rand7.
具体倍数是多少只影响效率，不影响答案，所以取3*7最优。
【在 x*****p 的大作中提到】
: Even the formula
: 5*(rand5 - 1) + (rand5 - 1) mod 7
: can not generate an evenly distributed rand7
: Assume rand5 generates 1, 2, 3, 4, 5, we set X = rand5 - 1
: and Y = rand5 - 1. Then we have the following table for 5X + Y mod 7
: X Y 5X+Y
: 0 0 0
: 0 1 1
: 0 2 2
: 0 3 3
| i**********e
发帖数: 1145 | 9 有个好办法，就是初始化以下的 5 x 5 矩阵：
1 2 3 4 5
1 1 2 3 4 5
2 6 7 1 2 3
3 4 5 6 7 1
4 2 3 4 5 6
5 7 0 0 0 0
两次 rand5 就会生成两个 1-5 的随机数，把它们设为矩阵的 row and column（其实就是对应矩阵里的某一个位置）.如果矩阵返回的值为 1-7 某个数，就直接返回那个值。如果返回的值是0，那无所谓，重新生成两个随机数，再次检查矩阵，直到找到 1-7 为止。
这个放弃重新sample的原理 其实是根据数学概率论的 rejection sampling. 想知道更多的话，你可以看看这个维基百科连接：
http://en.wikipedia.org/wiki/Rejection_sampling
有一个很有趣的问题，就是以上的方法，平均调用 rand5() 多少次？
还有一个更有趣的问题就是，以上的方法能再优化吗？应该怎么优化呢？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 r*******l 的大作中提到】
: 用rand5 产生 rand7
: 5*(rand5 -1) + (rand5-1)
: 为啥不直接5*rand5 to get < 25, then mod 7?
: 谁来说说
|
|
