问题：假设您有一个随机数生成器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);
- }
- }
