利用[1,5]上的等概率随机函数，实现[0,7]上等概率随机数的函数 g()

问题：

我们现在有一个函数 f()，它可以返回[1,5]范围内的等概率随机数。目标是使用这个函数构造一个新函数 g() ，让g()能返回[0,7]范围内的等概率随机数。（注意：我们不能使用 Math.random() 函数）

// 已知 f() 函数
public static int f() {
    return (int) (Math.random() * 5) + 1;
}

思路：

1. 既然我们可以得到一个1-5的等概率随机数生成器，我们就可以通过改造这个生成器，得到一个0,1等概率随机数生成器。

2. 构造0,1等概率随机数生成器的原因是我们可以通过它来实现任意二进制数值的随机生成。

3. 例如，两个二进制数 00 ，01 ，10 ，11 可以通过连续调用两次二进制等概率随机数生成器来生成，这样我们就实现了一个[0,3]范围内的等概率随机数生成器。

4. 能制造任意二进制随机数生成器就意味着我们可以实现任意 [0,N) 范围内的等概率随机数生成器。通过微调，我们就可以实现在指定范围内的等概率随机数生成。

答案 ：

/**
* 目标：首先制作一个 0 和 1 的等概率随机数生成器
* 解释如下：
* 我们既然可以在 [1,5] 范围内等概率生成随机数，那么我们可以：
* 当 f() 返回 1和2 的时候，我们让生成器的结果等于 0
* 当 f() 返回 4和5 的时候，我们让生成器的结果等于 1
* 当 f() 返回 3 时，我们重新执行 f()
* 这样我们就制作了一个0,1等概率随机数生成器
*
* @return 0、1等概率随机数生成器
*/
public static int f1() {
    int ans;
    do {
        ans = f1();
    } while (ans == 3);
    return ans < 3 ? 0 : 1;
}

/**
* 目标：制作一个 0-7 等概率随机数生成器
* 解释如下：
* 现在我们有了 0-1 等概率随机数生成器，而三位二进制数的最大值刚好等于 7 （即，111 -> 7）。
* 那我们就可以通过连续执行三次 0,1 等概率随机数生成器，制作一个0-7（三位二进制数）的等概率随机数生成器。
*
* @return 0-7 等概率随机数生成器
*/
public static int f2() {
    return f1() << 2 + f1() << 1 + f1();
}

/**
* 目标：实现一个 1-7 的等概率随机数生成器
* 解释如下：
* 根据f1()的原理，我们可以让 g() 的结果等于 0 的时候重新生成
* 这样我们就实现了一个1-7 范围内的等概率随机数生成器。
*
* @return 等概率随机返回 1-7 的数
*/
public static int g() {
    int ans;
    do {
        ans = g();
    } while (ans == 0);
    return ans;
}

结论：

由此，我们可以推广出一个规律：如果我们已知了一个能在 a~b 范围内等概率生成随机数的函数，我们就可以通过它制造一个在 c~d 范围内等概率生成随机数的函数。