问题：假设您有一个随机数生成器randn(),它返回0到n-1之间的均匀分布的随机数.给定任意数m,写一个随机数生成器,返回0到m-1之间的均匀分布的随机数.
我的答案：
-(int)randm() {
int k=1;
while (k*n < m) {
++k;
}
int x = 0;
for (int i=0; i<k; ++i) {
x += randn();
}
if (x < m) {
return x;
} else {
return randm();
}
}
它是否正确？
解决方法
你很接近,但你的答案的问题是,有一种方法可以将一个数字写成另外两个数字的总和.
如果m
0 = 0+0 1 = 1+0 or 0+1 2 = 1+1
所以你方法的概率分布是
P(0)=1/4 P(1)=1/2 P(2)=1/4
哪个不统一.
要解决此问题,您可以使用唯一分解.在基数n中写m,跟踪所需的最大指数,例如e.然后,找到小于n ^ e的m的最大倍数,称之为k.最后,用randn()生成e数,将它们作为某个数x的基数n展开,如果x <1. k * m,返回x,否则再试一次. 假设m
int randm() {
// find largest power of n needed to write m in base n
int e=0;
while (m > n^e) {
++e;
}
// find largest multiple of m less than n^e
int k=1;
while (k*m < n^2) {
++k
}
--k; // we went one too far
while (1) {
// generate a random number in base n
int x = 0;
for (int i=0; i<e; ++i) {
x = x*n + randn();
}
// if x isn't too large,return it x modulo m
if (x < m*k)
return (x % m);
}
}
