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);
|
