D***n 发帖数: 149 | 1 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);
}
}
哪位高手能解释一下这段代码的正确性?? |
s*****n 发帖数: 5488 | 2 只用rand(5) -1, 产生0 5 10 15 20 25.需要再用一次生成01234
然后
0 + 01234
5 + 01234
10 +....
.....
就是0..25 的random distribution了。
剩下的就很好理解了。
given
【在 D***n 的大作中提到】 : 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);
|
s**x 发帖数: 7506 | 3 1 <= rand5() <= 5
0 <= rand5() -1 <= 4
0 <= 5 *(rand5() -1) <= 20
1 <= 5 *(rand5() -1) + ( rand5() - 1) <= 25 |
d**e 发帖数: 6098 | 4 你这个没解释清楚为什么要这样做,上面slimcan说得比较明白。
【在 s**x 的大作中提到】 : 1 <= rand5() <= 5 : 0 <= rand5() -1 <= 4 : 0 <= 5 *(rand5() -1) <= 20 : 1 <= 5 *(rand5() -1) + ( rand5() - 1) <= 25
|
s*****y 发帖数: 897 | 5 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**e 的大作中提到】 : 你这个没解释清楚为什么要这样做,上面slimcan说得比较明白。
|
s*****y 发帖数: 897 | 6 also here:
http://www.mytechinterviews.com/equal-probability-between-1-and
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5();
if (num < 22) return ((num % 7) + 1);
}
}
a
【在 s*****y 的大作中提到】 : 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);
|
d**e 发帖数: 6098 | 7 区别不是很大吧
只是一个算1-25,一个算0-24
【在 s*****y 的大作中提到】 : also here: : http://www.mytechinterviews.com/equal-probability-between-1-and : int rand7() { : while (1) { : int num = 5*(rand5()-1) + rand5(); : if (num < 22) return ((num % 7) + 1); : } : } : : a
|
s*****y 发帖数: 897 | 8 one generate 0 - 6
one generate 1 - 7
【在 d**e 的大作中提到】 : 区别不是很大吧 : 只是一个算1-25,一个算0-24
|
D***n 发帖数: 149 | |
d**e 发帖数: 6098 | 10 但我觉得 num%7 + 1 得不到 0...
【在 s*****y 的大作中提到】 : one generate 0 - 6 : one generate 1 - 7
|
s*****y 发帖数: 897 | 11 Why need to generate 0?
【在 d**e 的大作中提到】 : 但我觉得 num%7 + 1 得不到 0...
|
d**e 发帖数: 6098 | 12 我没说需要0啊,只是你说一个是0-6,但我觉得得不到0
因为都是得到1-7,所以生成0-24(if num < 21) 和1-25(if num < 22)没什么区别吧
【在 s*****y 的大作中提到】 : Why need to generate 0?
|
s*****y 发帖数: 897 | 13 不好意思,眼花了,看错了原来树上的代码,以为那里没有加1。
【在 d**e 的大作中提到】 : 我没说需要0啊,只是你说一个是0-6,但我觉得得不到0 : 因为都是得到1-7,所以生成0-24(if num < 21) 和1-25(if num < 22)没什么区别吧
|
c****p 发帖数: 6474 | 14 好像还有更给力的版本。。
目前这个版本,存在一直出大于22的数的可能。。。。
given
【在 D***n 的大作中提到】 : 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);
|