e****q
发帖数: 1668 | 1 rand(5) generates a random integer number between [1, 5], how do you
generate a random integer number between [1, 7] when you can only call
rand(5)? | E*******0
发帖数: 465 | 2 function b=rand()
{
a=rand(5);
b=a*7/5;
} | e****q
发帖数: 1668 | 3 they ask for 'integer' from [1,7].
【在 E*******0 的大作中提到】
: function b=rand()
: {
: a=rand(5);
: b=a*7/5;
: }
| n******r
发帖数: 1247 | 4 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;
}
【在 e****q 的大作中提到】
: they ask for 'integer' from [1,7].
| p***o
发帖数: 3399 | 5 very easy
sqrt((rand(5)-3)^2)+rand(5)
【在 n******r 的大作中提到】
: 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;
| g*******y
发帖数: 1930 | 6 very wrong
两个rand(5)一共产生25中情况
不管你怎么设计mapping方案，都不可能均匀的分配给7个数！因为7不整除25
【在 p***o 的大作中提到】
: very easy
: sqrt((rand(5)-3)^2)+rand(5)
| H*M
发帖数: 1268 | 7 he is a famous performance artist.
【在 g*******y 的大作中提到】
: very wrong
: 两个rand(5)一共产生25中情况
: 不管你怎么设计mapping方案，都不可能均匀的分配给7个数！因为7不整除25
| c*********n
发帖数: 1057 | 8 看不太懂，能解释下么？
【在 n******r 的大作中提到】
: 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;
| p***o
发帖数: 3399 | 9 怎么不对啊，不用解释吧
rand(5)可以generate出(1,2,3,4,5)
rand(5)-3=(-2,-1,0,1,2)
所以(rand(5)-3)^2=(0,1,4)
sqrt（（rand(5)-3）^2）=(0,1,2)
sqrt（（rand(5)-3）^2）+rand(5)=(0,1,2)+(1,2,3,4,5)=(1,2,3,4,5,6,7)
什么整除不整除的，哪有那么复杂啊
【在 g*******y 的大作中提到】
: very wrong
: 两个rand(5)一共产生25中情况
: 不管你怎么设计mapping方案，都不可能均匀的分配给7个数！因为7不整除25
| H*M
发帖数: 1268 | 10 with equal probability
【在 p***o 的大作中提到】
: 怎么不对啊，不用解释吧
: rand(5)可以generate出(1,2,3,4,5)
: rand(5)-3=(-2,-1,0,1,2)
: 所以(rand(5)-3)^2=(0,1,4)
: sqrt（（rand(5)-3）^2）=(0,1,2)
: sqrt（（rand(5)-3）^2）+rand(5)=(0,1,2)+(1,2,3,4,5)=(1,2,3,4,5,6,7)
: 什么整除不整除的，哪有那么复杂啊
| | | p***o
发帖数: 3399 | 11 那个没辙，要不把随机改成任意好了，嘿嘿
【在 H*M 的大作中提到】
: with equal probability
| H*M
发帖数: 1268 | 12 no artist here!
【在 p***o 的大作中提到】
: 那个没辙，要不把随机改成任意好了，嘿嘿
| c******o
发帖数: 1277 | 13 first you need to ask if they want uniformed ramdom value
if yes, it is abit hard, the worst case is that
rand(5) + 5* (rand(5)-1) and re do if there the result is 22, 23, 24, 25
and then divide by 3 and get ceiling. | E*******0
发帖数: 465 | 14 Sorry. I misunderstood the question. | E*******0
发帖数: 465 | 15 A={1,2};
B={1,2,3,4};
C=all pairs of one number from A and one number from B except {1,1}
So the number of set C is 2*4-1=7.
Set a number [1,7] for each element from C.
Namely,
Rand(7)
{
while(1)
{A=Rand(5);
if (A<=2) break;}
while(1)
{B=Rand(5);
if ((B<=4) && (A!=1) && (B!=1)) break;}
switch
case A=1, B=2: return 1;
case A=1, B=3: return 2;
case A=1, B=4: return 3;
case A=2, B=1: return 4;
case A=2, B=2: return 5;
case A=2, B= | f****r
发帖数: 997 | 16 想到过正确的办法，但在效率上不完美
如果有1-5的等概率函数，那么产生1-4，1-3，1-2的等概率函数都很容易，比如1-4的
等概率函数，可以这样：
while (Rand(5)!=5)
return Rand(5)
以Rand（2）为例，当然不需要把3-5都去除，可以这样：
while (Rand(5)!=5)
{
if Rand(5)<3
return 1
else rerurn 2
}
由于任何整数都可以表示为二进制，用三次Rand(2)表示三位二进制，可以等概率出现0
-7，剩下的就是把出现0的时候去掉（结果是0时，再随机一次)即可。 | h***r
发帖数: 726 | 17 为什么一定要表示成2进制呢？
對原题，把7表示成5进制。
推而广之，效率就比表示成二进制要效率高了。
【在 f****r 的大作中提到】
: 想到过正确的办法，但在效率上不完美
: 如果有1-5的等概率函数，那么产生1-4，1-3，1-2的等概率函数都很容易，比如1-4的
: 等概率函数，可以这样：
: while (Rand(5)!=5)
: return Rand(5)
: 以Rand（2）为例，当然不需要把3-5都去除，可以这样：
: while (Rand(5)!=5)
: {
: if Rand(5)<3
: return 1
| f****r
发帖数: 997 | 18 当然不必要表示成2进制，只是提供一个思路，2进制是最容易让人理解，也是适应面最
广的。
但遗憾的是不管用几进制，都达不到完美效率。不知道有没有更好的办法。 | H*****L
发帖数: 5705 | 19 把7表示成5进制? could u elaborate more?
【在 h***r 的大作中提到】
: 为什么一定要表示成2进制呢？
: 對原题，把7表示成5进制。
: 推而广之，效率就比表示成二进制要效率高了。
| h***r
发帖数: 726 | 20 7 = 12 （5进制)
【在 H*****L 的大作中提到】
: 把7表示成5进制? could u elaborate more?
| t****t
发帖数: 6806 | 21 这个题, 如果答案不用循环reject就一定是错的. 因为5^n永远不能被7整除, 所以如果
固定产生n个[1,5]的均匀随机整数, 可能得到的状态空间永远不能分成7等分, 即不能
产生[1,7]的均匀随机整数, if all states are used.
所以你说的"完美效率"是不可能达到的. 但是这很正常.
【在 f****r 的大作中提到】
: 当然不必要表示成2进制，只是提供一个思路，2进制是最容易让人理解，也是适应面最
: 广的。
: 但遗憾的是不管用几进制，都达不到完美效率。不知道有没有更好的办法。
|
|
