给定一个等概率随机产生1~M的随机函数rand1ToM如下：

public int rand1ToM(int m) {

    return (int) (Math.random() * m) + 1;

}

除此之外不能使用任何额外的随机机制。有两个输入参数分别为m和n，请用rand1ToM(m)实现等概率随机产生1~n的随机函数rand1ToN。

Solution

在做这道题之前，我们先来看一个例子，由rand1to5如何产生rand1to7？稍加思考，不难发现可以有以下做法：

rand1to5(5) 等概率产生: 1 2 3 4 5

rand1to5(5) – 1 等概率产生: 0 1 2 3 4

(rand1to5(5) – 1) * 5 等概率产生: 0 5 10 15 20

(rand1to5(5) – 1) * 5 + (rand1to5(5) – 1) 等概论产生: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

现在 (rand1to5(5) – 1) * 5 + (rand1to5(5) – 1) 的范围已经超过1-7了，因此不用继续再扩大随机数函数可以生成的范围。

现在的问题是，已有的0-24这5个数中，0-20通过模7可以生成3套0-6，也就是说0-20可以等概率生成0-6，通过加1即可等概率生成1-7。但是，由于21-24的存在，0-24生成0-3的概率会大于4-6（加1后生成1-4的概率会大于5-7），如何解决？如果随机数生成函数生成21-24范围的数，那么直接忽略这次随机数的生成。代码如下：

public int rand1To5() {

    return (int) (Math.random() * 5) + 1;

}

public int rand1To7() {

    int num = 0;

    do {

        num = (rand1To5() - 1) * 5 + rand1To5() - 1;

    } while (num > 20);

    return num % 7 + 1;

}

现在来看，如何解决rand1tom生成rand1ton。其实一句话就可以总结，即以m倍的规模不断扩大随机数范围直到超过1ton的范围，之后使用do while循环筛选掉多余的使得概论不均等的数即可。

进阶

如果预先给定的随机数生成器以p的概论生成0，(1-p)的概率生成1，那么怎么通过该随机数生成器等概率生成的1-n？

无论概率p怎么变化，连续两次生成0 1或者1 0的概率都是p(1-p)，因此我们只要排除掉0 0和1 1的情况就可以等概率生成0 1，如下：

public int rand01p() {

    // you can change p as you like

    double p = 0.83;

    return Math.random() < p ? 0 : 1;

}

public int rand01() {

    int num;

    do {

        num = rand01p();

    } while (num == rand01p());

    return num == 1 ? 1 : 0;

}

而通过0 1 来生成 1-n的方法和之前的是一样的。