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 的大作中提到】
: 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 的大作中提到】
: 你的答案不对。。。给的随机数发生器只得到整数。
| z**********2
发帖数: 307 | 5 随机数发生器，内部是什么样的
【在 o***d 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 有三个问题：
: 第一个问题：题目要求是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 的大作中提到】
: 明白了,谢谢
| t****t
发帖数: 6806 | 10 从1,2,3,4,5的均匀随机数发生器里产生的等概率状态数是5^N种. 要生成一个1,2,3,..
.7的均匀随机数发生器, 你需要的状态数一定是7的倍数.
但是对于任何有限的N, 5^N永远不可能被7整除, 所以任何"固定次数"的解必定是错的.
【在 z**x 的大作中提到】
: 有没有更好的方法 依赖于随机数和小于某个数 ， 总感觉没谱。
: 另外为啥 4b a是uniform啊，那同理能不能 ran 0 70， 这样就每次固定次数解
: 决了
:
: 明白了,谢谢
| t****t
发帖数: 6806 | 11 当然是while(r>=21), 因为只有0~20的区间是可以接受的.
【在 n****r 的大作中提到】
: 有三个问题：
: 第一个问题：题目要求是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);
|
|
