f**********8
发帖数: 2276 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: foolsgarden8 (小兔子), 信区: JobHunting
标 题: 如果给随即函数rand[1,5] 如何产生rand[1,7]
发信站: BBS 未名空间站 (Tue Jun 8 00:51:44 2010, 美东)
int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
}
谁能解释一下这个解答？看不懂 |
z****e
发帖数: 2024 | 2 构造一个5×5的概率空间，等概率产生25个事件，前面21个可以构造被7整除的等概率
事件数。
超过21就不算重来。 |
l******e
发帖数: 12192 | |
N***m
发帖数: 4460 | 4 ft, i have deleted it
【在 l******e 的大作中提到】
: 你再算算？呵呵
|
N***m
发帖数: 4460 | 5 因为我发现对于奇数p,(2x+1)%p for x=0,1,2,...,p-1是x的乱序。
我就想有没有更有效或者简洁的办法？
【在 l******e 的大作中提到】
: 你再算算？呵呵
|
X****r
发帖数: 3557 | 6 从1-n的随机数产生1-m的随机数，前者的概率空间的“粒度”是1/n^k，
所以除非存在整数k和a使n^k=am，不然就必然要扔掉一些数。对于给定
的n和m，一种比较有效率（就有效利用原来的随机数而言）的方法是找
一对整数b,k使m^b(在比例上)接近但不超过n^k，每b个输入如果落在
m^b之内的话就产生k个输出，不然从新取。这样每个输出平均就只需要
(k*n^k)/(b*m^b)个输入。
当然以上假设输入输出都是独立均匀分布的。如果输出不需要独立均匀分
布的话就随便了。
【在 N***m 的大作中提到】
: 因为我发现对于奇数p,(2x+1)%p for x=0,1,2,...,p-1是x的乱序。
: 我就想有没有更有效或者简洁的办法？
|
N***m
发帖数: 4460 | 7 受教了~~
【在 X****r 的大作中提到】
: 从1-n的随机数产生1-m的随机数，前者的概率空间的“粒度”是1/n^k，
: 所以除非存在整数k和a使n^k=am，不然就必然要扔掉一些数。对于给定
: 的n和m，一种比较有效率（就有效利用原来的随机数而言）的方法是找
: 一对整数b,k使m^b(在比例上)接近但不超过n^k，每b个输入如果落在
: m^b之内的话就产生k个输出，不然从新取。这样每个输出平均就只需要
: (k*n^k)/(b*m^b)个输入。
: 当然以上假设输入输出都是独立均匀分布的。如果输出不需要独立均匀分
: 布的话就随便了。
|
z****e
发帖数: 2024 | 8 红猪侠下午好啊。
【在 X****r 的大作中提到】
: 从1-n的随机数产生1-m的随机数，前者的概率空间的“粒度”是1/n^k，
: 所以除非存在整数k和a使n^k=am，不然就必然要扔掉一些数。对于给定
: 的n和m，一种比较有效率（就有效利用原来的随机数而言）的方法是找
: 一对整数b,k使m^b(在比例上)接近但不超过n^k，每b个输入如果落在
: m^b之内的话就产生k个输出，不然从新取。这样每个输出平均就只需要
: (k*n^k)/(b*m^b)个输入。
: 当然以上假设输入输出都是独立均匀分布的。如果输出不需要独立均匀分
: 布的话就随便了。
|
X****r
发帖数: 3557 | 9 你这个不是均匀分布的。比如出7的机率才1/25。 |
X****r
发帖数: 3557 | 10 中午好。
【在 z****e 的大作中提到】
: 红猪侠下午好啊。
|
|
|
z****e
发帖数: 2024 | 11 咱俩应该都反过来问候对方。
呵呵。
【在 X****r 的大作中提到】
: 中午好。
|
d****e
发帖数: 251 | 12 明白了，以前碰到过类似的情况（double precision的空间），现在都忘了。
不过原题还是有个小问题，目标区域是[1,7]。
【在 X****r 的大作中提到】
: 你这个不是均匀分布的。比如出7的机率才1/25。
|
B*******g
发帖数: 1593 | 13 int num = 5*(rand5() -1) + rand5（）- 1；
和
int num = 5*rand5() - rand5();是否一样啊？ |
t****t
发帖数: 6806 | 14 你把上面那个式子展开能得到下面那个吗？
【在 B*******g 的大作中提到】
: int num = 5*(rand5() -1) + rand5（）- 1；
: 和
: int num = 5*rand5() - rand5();是否一样啊？
|
d****p
发帖数: 685 | 15 5X(rand()-1)+rand()-1
= 5Xrand() + (rand() -6)
= 5Xrand() + X where X in [-1, -5]
= 5Xrand() + (-rand())
【在 t****t 的大作中提到】
: 你把上面那个式子展开能得到下面那个吗？
|
z****e
发帖数: 2024 | 16 好眼力。
【在 d****p 的大作中提到】
: 5X(rand()-1)+rand()-1
: = 5Xrand() + (rand() -6)
: = 5Xrand() + X where X in [-1, -5]
: = 5Xrand() + (-rand())
|
