o***d 发帖数: 313 | 1 http://www.careercup.com/question?id=12426697
Given a random number generator say r(5) generates number between 1-5
uniformly at random , use it to in r(7) which should generate a random
number between 1-7 uniformly at random.
===========solution:
my solution is the same with this:
>>>>>>>>>
Let f() be the random function that returns a number between (1,5).
Let g() = f() -1; then g is a function that returns a number between (0,4).
Let h() = g()/4; then h is a function that returns a number between (0,1).
Let i() = h()*6; then i is a function that returns a number between (0,6)
Let j() = i() + 1; then j is a function that returns a number between (1,7).
but careercup's thread:>>>>>>>>>
int rand7() //random number from 1 - 7
{
int r = 0;
do
{
int a = rand(5) - 1; //uniformly at random from 0 to 4
int b = rand(5) - 1; //uniformly at random from 0 to 4
r = 5*b + a; //uniformly at random from 0 to 24
}
while (r >= 21); // in this event, we have to roll again
//postcondition of loop: we have a number uniformly at random between 0
and 20
return r % 7 + 1;
//there are 3 numbers in [0, 20] for each possible return value
//so each has equal probability.
}
我的答案有问题么?我觉得没有问题吧? | l*******b 发帖数: 2586 | 2 你的答案不对。。。给的随机数发生器只得到整数。
【在 o***d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.careercup.com/question?id=12426697 : Given a random number generator say r(5) generates number between 1-5 : uniformly at random , use it to in r(7) which should generate a random : number between 1-7 uniformly at random. : ===========solution: : my solution is the same with this: : >>>>>>>>> : Let f() be the random function that returns a number between (1,5). : Let g() = f() -1; then g is a function that returns a number between (0,4). : Let h() = g()/4; then h is a function that returns a number between (0,1).
| w****x 发帖数: 2483 | 3 reject sampling
调两次 r(5) => 5 * 5 =〉25的block | o***d 发帖数: 313 | 4 ?没写要求整数阿.如果要求整数,那确实不对
thanks
【在 l*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的答案不对。。。给的随机数发生器只得到整数。
| z**********2 发帖数: 307 | 5 随机数发生器,内部是什么样的
【在 o***d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.careercup.com/question?id=12426697 : Given a random number generator say r(5) generates number between 1-5 : uniformly at random , use it to in r(7) which should generate a random : number between 1-7 uniformly at random. : ===========solution: : my solution is the same with this: : >>>>>>>>> : Let f() be the random function that returns a number between (1,5). : Let g() = f() -1; then g is a function that returns a number between (0,4). : Let h() = g()/4; then h is a function that returns a number between (0,1).
| e********2 发帖数: 495 | 6 抛两次产生两个随机数(x,y):
(1,2) (2,1) (1,1)对应1
(1,3) (3,1) (2,2)对应2
(1,4) (4,1) (3,3)对应3
(1,5) (5,1) (4,4)对应4
(2,3) (3,2) (5,5)对应5
(2,4) (4,2) (3,4)对应6
(2,5) (5,2) (4,3)对应7
遇到其他的组合再抛。
直到遇到以上组合为止。
【在 o***d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.careercup.com/question?id=12426697 : Given a random number generator say r(5) generates number between 1-5 : uniformly at random , use it to in r(7) which should generate a random : number between 1-7 uniformly at random. : ===========solution: : my solution is the same with this: : >>>>>>>>> : Let f() be the random function that returns a number between (1,5). : Let g() = f() -1; then g is a function that returns a number between (0,4). : Let h() = g()/4; then h is a function that returns a number between (0,1).
| n****r 发帖数: 120 | 7 有三个问题:
第一个问题:题目要求是int r7,也就是说要求等概率随机产生[1..7]之间的一个数
第二个是你的解法:
说白了,就是 rand7 = 6*((rand5 - 1)/4)+1,这里面涉及两个问题,如果你用int来做
这个计算,最后结果将是1或者7。若用double来处理,应该是可以返回[1..7]之间的数
,但是不是等概率的。原因是因为数学运算的时候无法避免精度上的变化,这个变化会
影响到随机性。我试了一下,这个算法好像产生3这个数的概率奇低(如果不是不能的
话)
第三个是你提到的Career Up的解法
while (r >= 21); //这里应该是 while (r>21); | o***d 发帖数: 313 | 8 明白了,谢谢
【在 n****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有三个问题: : 第一个问题:题目要求是int r7,也就是说要求等概率随机产生[1..7]之间的一个数 : 第二个是你的解法: : 说白了,就是 rand7 = 6*((rand5 - 1)/4)+1,这里面涉及两个问题,如果你用int来做 : 这个计算,最后结果将是1或者7。若用double来处理,应该是可以返回[1..7]之间的数 : ,但是不是等概率的。原因是因为数学运算的时候无法避免精度上的变化,这个变化会 : 影响到随机性。我试了一下,这个算法好像产生3这个数的概率奇低(如果不是不能的 : 话) : 第三个是你提到的Career Up的解法 : while (r >= 21); //这里应该是 while (r>21);
| z**x 发帖数: 16 | 9 有没有更好的方法 依赖于随机数和小于某个数 , 总感觉没谱。
另外为啥 4b a是uniform啊,那同理能不能 ran 0 70, 这样就每次固定次数解
决了
明白了,谢谢
【在 o***d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 明白了,谢谢
| t****t 发帖数: 6806 | 10 从1,2,3,4,5的均匀随机数发生器里产生的等概率状态数是5^N种. 要生成一个1,2,3,..
.7的均匀随机数发生器, 你需要的状态数一定是7的倍数.
但是对于任何有限的N, 5^N永远不可能被7整除, 所以任何"固定次数"的解必定是错的.
【在 z**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有没有更好的方法 依赖于随机数和小于某个数 , 总感觉没谱。 : 另外为啥 4b a是uniform啊,那同理能不能 ran 0 70, 这样就每次固定次数解 : 决了 : : 明白了,谢谢
| t****t 发帖数: 6806 | 11 当然是while(r>=21), 因为只有0~20的区间是可以接受的.
【在 n****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有三个问题: : 第一个问题:题目要求是int r7,也就是说要求等概率随机产生[1..7]之间的一个数 : 第二个是你的解法: : 说白了,就是 rand7 = 6*((rand5 - 1)/4)+1,这里面涉及两个问题,如果你用int来做 : 这个计算,最后结果将是1或者7。若用double来处理,应该是可以返回[1..7]之间的数 : ,但是不是等概率的。原因是因为数学运算的时候无法避免精度上的变化,这个变化会 : 影响到随机性。我试了一下,这个算法好像产生3这个数的概率奇低(如果不是不能的 : 话) : 第三个是你提到的Career Up的解法 : while (r >= 21); //这里应该是 while (r>21);
|
|