问题：假设您有一个随机数生成器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();
}
}@H_404_5@
它是否正确？
解决方法
你很接近,但你的答案的问题是,有一种方法可以将一个数字写成另外两个数字的总和.
如果m
0 = 0+0 1 = 1+0 or 0+1 2 = 1+1@H_404_5@所以你方法的概率分布是
P(0)=1/4 P(1)=1/2 P(2)=1/4@H_404_5@哪个不统一.
要解决此问题,您可以使用唯一分解.在基数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); } }@H_404_5@
