x**8
发帖数: 1939 | 1 我做了一个rand5 7次，然后再 %7 + 1,
这个我算了一下，基本均匀，但是不完全均匀，
这个可以吗？
取得1到7的次数分别为：
11177
11172
11158
11144
11144
11158
11172
大侠请指点！ |
|
t**a
发帖数: 33 | 2 Think about rand2 to rand3 firstly:
throw twice.
11=1
12=2
21 =3
22 rethrow
The left part is like binary number.
rand5 to rand7 can also work by throwing twice, you have 25 candidates, make
use of the first 21 to reduce the possibility of rethrow. |
|
n****e
发帖数: 678 | 3 Write a method to generate a random number between 1 and 7, given a method
that generates a random number between 1 and 5 (i.e., implement rand7()
using rand5()).
给出的解是：
public static int rand7() {
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 21) return (num % 7 + 1);
}
}
想问一下为什么这么做是对的？
如果这样写对吗？
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 7) return (num + 1);
}
或者
while (true) {
int num = 5 * (rand5() - 1) +... 阅读全帖 |
|
p******r
发帖数: 2999 | 4 rand5()随机产生1-5
(rand5()-1)*5生成0,5,10,15,20
(rand5()-1)*5+rand5()就能随机生成1-25之间的数
然后通过模7来生成1-7的随机数
由于25不能被7整除，所以只考虑1-21之间
最后的表达式为
((rand5()-1)*5+rand5())%7+1 |
|
x*****p
发帖数: 1707 | 5 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
... 阅读全帖 |
|
s**x
发帖数: 7506 | 6 1 <= rand5() <= 5
0 <= rand5() -1 <= 4
0 <= 5 *(rand5() -1) <= 20
1 <= 5 *(rand5() -1) + ( rand5() - 1) <= 25 |
|
n******r
发帖数: 1247 | 7 int rand10(){
int x=rand5();
while (x==3) x=rand5();
if (x<3) return rand5();
else return rand5()+5;
}
int rand7(){
int x=rand10();
while (x>7) x=rand10();
return x;
} |
|
r*******l
发帖数: 511 | 8 用rand5 产生 rand7
5*(rand5 -1) + (rand5-1)
为啥不直接5*rand5 to get < 25, then mod 7?
谁来说说 |
|
D*********y
发帖数: 876 | 9 5*(rand5()-1)：产生0,5,10,15或者20
5 * (rand5() - 1) + rand5()就是1-25之间的随机数
如果我没有记错的话，后面那个while应该是:
if(i<21) return i%7
while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;
产生的是2-5，就不对了
至于楼主的做法，
i = 6*(rand5()-1)，产生的是0,6，12，18或者24 |
|
q*****9
发帖数: 85 | 10 int rand8(){
int tmp = 0;
if((tmp=rand5()+rand5()+rand5()+...rand5())<=5)//eight
return 1;
else if(tmp<=10)
return 2;
......
} |
|
g**********y
发帖数: 14569 | 11 rand5()产生 1..5
rand5() - 1 ~ 0..4
5*(rand5()-1) ~ 0, 5, 10, 15, 20
再call rand5()-1 ~ 0..4
这样等概率产生了0~24 |
|
T**********a
发帖数: 15 | 12 //19.9Write a method to generate a random number between 1 and 7, given
a method
//that generates a random number between 1 and 5 (i.e., implement rand7(
) using
//rand5())
public static int rand5(){
return (int)(Math.random()*100) % 5+1;
}
public static int rand7() {
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 21) return (num % 7 + 1);
}
}
Question:
for the following line:
return (i... 阅读全帖 |
|
B*******g
发帖数: 1593 | 13 int num = 5*(rand5() -1) + rand5（）- 1；
和
int num = 5*rand5() - rand5();是否一样啊？ |
|
h****8
发帖数: 599 | 14 来自主题: JobHunting版 - 问一个老题 如何用rand5（返回1~5） 来做一个rand7（返回1~7）的函数
答案如下但是不理解：
int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
} |
|
i**r
发帖数: 40 | 15 num = 5*(rand5() -1) + rand5（）- 1
Using two rand5() to generate uniformly distributed random number in the
range of [0, 24]
if (num < 21) return num % 7;
Discard num >= 21 so that rand7() will output random number [0..6] uniformly
. |
|
f**********8
发帖数: 2276 | 16 Rand[1,7] is not Rand[0,6], so the last line of solution should be
if (num < 21) return num % 7 +1; right?
Also, why use num=6*(rand5()-1), not 5*(rand5()-1) , or 4*(rand5()-1). any
difference? |
|
l*******o
发帖数: 791 | 17 这样做行么？
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;
} |
|
H******7
发帖数: 1728 | 18 在别的论坛看到别人再问。觉得不太明白。
Expand a random range from 1-5 to 1-7
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1
and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
WHy can't I just put
i = 6*(rand5()-1); |
|
t**********n
发帖数: 145 | 19 1没有保证平均概率
2返回的数值的范围也不对呀
在别的论坛看到别人再问。觉得不太明白。
Expand a random range from 1-5 to 1-7
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1
and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
WHy can't I just put
i = 6*(rand5()-1); |
|
D***n
发帖数: 149 | 20 19.10 Write a method to generate a random number between 1 and 7, given
a method that generates a random number between 1 and 5 (i.e., implement
rand7() using rand5()).
看了书的答案还是不太明白啊。。。为什么rand2()用decision tree表示，到leaf会有
3的result？？
answer: public static int rand7()
{
while(true)
{
int num = 5 * ( rand5() - 1) + ( rand5() - 1);
if ( num < 21 ) return ( num % 7 + 1);
}
}
哪位高手能解释一下这段代码的正确性？？ |
|
w***o
发帖数: 109 | 21 为什么不能用rand5（）* 5 + rand5()?
我看没什么问题，关键看你怎么取舍数字。
比如：
int ret = 0;
while(ret < 10)
ret = rand5() * 5 + reand5()；
return (ret % 7) + 1; |
|
n****e
发帖数: 678 | 22 想通了，
5 * (rand5() - 1) + (rand5() - 1);
前面这个系数5是不能随便改的，因为是rand5，所以只有系数为5的时候所生成的书才
是随机的。
这种情况下21是最大的被7整除的数，所以解答是这么给的。
多谢指教！ |
|
G**********s
发帖数: 70 | 23 这两个都错的。。rand5+rand5 之后就不是uniform distributed 了 |
|
c****s
发帖数: 241 | 24 3)那个我错了，多谢，多谢。正确的应该是这个吧：
rand7(){
int i;
do{
i=(rand5()-1)*5+rand5();
} while(i>21);
return i%7;
} |
|
a*u
发帖数: 2334 | 25 为什么是
do{
i=(rand5()-1)*5+rand5();
} while(i>21);
?
我那个可以再加一个Rand(5)，然后1-5，+0；6-10，+1； 11-15， +2 也是平均的 |
|
h*h
发帖数: 23 | 26 还是不太明白这个. loop里面为什么要乘5呢? 乘4行不行呢? 比如把loop改成下面这样:
i=(rand5()-1)*4+rand5();
i应该是1 - 21之间的数, do-while loop的目的不就是找一个1 - 21 之间的数吗? 这
样也不需要do-while loop了.
请牛人指教.
谢谢 |
|
m*****g
发帖数: 226 | 27 我怎么记得是
rand7()
{
i= rand5()*rand5();
if(i<=21) return i%7+1;
else return rand7();
}
样: |
|
B*******g
发帖数: 1593 | 28 来自主题: JobHunting版 - 问一个老题 5*(rand5() -1) + rand5（）- 1
生成的是0-24的随机数 分布可以自己算算看 |
|
K******g
发帖数: 1870 | 29 请教一下，为什么
已知rand[1,5], 求rand[1,7].
可以像下面一样做呢？
int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
}
有什么理由吗？ |
|
s*******s
发帖数: 27 | 30 5*(rand5()-1) + (rand5()-1) gives rand24, which can be used to generate
rand7() |
|
f**********8
发帖数: 2276 | 31 int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
}
谁能解释一下这个解答？看不懂 |
|
i**r
发帖数: 40 | 32
you are right.
let me break down the expression:
r1 = rand5()-1; // r1 is in {0,1,2,3,4}
r2 = 5*r1; // r2 is in { 0,5,10,15,20 }
r3 = rand5()-1; // another random num in { 0,1,2,3,4}
r4 = r2+r3 ; // r4 could be any element of { 0, 1, ..., 24}
The key is to maintain the uniform distribution property of random number
generator. Using 6 or 4 will either bring in an gap or an overlap in the
expanded range,then the distribution will not be uniform. |
|
s*****n
发帖数: 5488 | 33 这题以前有讨论。以前也没理解就是记住了。今天推了一下。
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正好落在前面的空
隙中，不会出现重复。 |
|
s*****u
发帖数: 15 | 34 5*(rand5 - 1) + (rand5 - 1) 必须是7的倍数时，才可以mod7得到rand7.
具体倍数是多少只影响效率，不影响答案，所以取3*7最优。 |
|
i**********e
发帖数: 1145 | 35 有个好办法，就是初始化以下的 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 |
|
t**********n
发帖数: 145 | 36 嗯范围可以解决，
但是理论上可以证明，rand5()是没有能力只通过一次随机数的产生，和一些四则运算
，来获得更大范围的随机数的。
（前提是，这里说的都是整数哦。。。如果是实数范围的话另当别论啦。）
所以必须通过多次rand5()才行呢
范围没事，可以用 rejection sampling解决。 |
|
s*****y
发帖数: 897 | 37 I do not think it is right one.
I think this one is right:
http://stackoverflow.com/questions/137783/expand-a-random-range
1-7
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 a
nd 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7 |
|
|
d********t
发帖数: 9628 | 39
为啥要 5*(rand5()-1) + (rand5()-1)? |
|
g**e
发帖数: 6127 | 40 rand5 * rand5 does not yield 1-25 uniform distribution... |
|
|
i***h
发帖数: 12655 | 42 you mean
(rand5 - 1) * 5 + rand5
? |
|
f**w
发帖数: 163 | 43 尼马 rand5()*rand5()这个连7都没有，还均匀分布
run 两次是 run 两次
第一次的结果是i, 第二次的结果是j
let x = i*5 + j, then u get 1-25 evenly distributed |
|
z******w
发帖数: 36 | 44 int cal() {
int c = 0;
while (true) {
int a = rand5();
int b = rand5();
a --;
b --;
c = a * 5 + b;
if (c < 21) break;
}
int res = c % 7;
return res + 1;
} |
|
a******e
发帖数: 710 | 45 int num = 5 * (rand5() - 1) + (rand5() - 1);
这一句生成0-24之间的整数且均匀分布。每个整数出现的概率都是相等的。
所以0-20这21个数出现的概率也是相等的。
取余数之后，每个余数0-6出现的概率也是相等的。 所以此算法是正确的。
效率问题：
这个算法循环一次就成功的概率为 21/25 = 84%。循环的次数服从几何分布。 平均复
杂度为25/21
你的第一种写法中，每次循环成功概率为7/25 = 14%。 平均复杂度为25/7。
所以cc150中的解法复杂度要好于你的解法。 |
|
n****e
发帖数: 678 | 46 能讲讲为什么原来的做法是对的吗？
如果上面3中alternative都可以，那下面这个写法应该比解答的效率要高吧：
while (true) {
int num = 6 * (rand5() - 1) + (rand5() - 1);
if (num < 28) return (num % 7 + 1);
} |
|
n****e
发帖数: 678 | 47 多谢解释啊！
那下面这个写法应该比解答的效率要高吧：
while (true) {
int num = 6 * (rand5() - 1) + (rand5() - 1);
if (num < 28) return (num % 7 + 1);
} |
|
f**********8
发帖数: 2276 | 48 【 以下文字转载自 JobHunting 讨论区 】
发信人: foolsgarden8 (小兔子), 信区: JobHunting
标 题: 如果给随即函数rand[1,5] 如何产生rand[1,7]
发信站: BBS 未名空间站 (Tue Jun 8 00:51:44 2010, 美东)
int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
}
谁能解释一下这个解答？看不懂 |
|
a******0
发帖数: 262 | 49 rand5*5+rand5 if <=24 then mod8? |
|
|
