说明

本示例中基于 Java ，其他语言也有类似的 API

解决的问题

问题1

Java 中 Math.random() 函数是等概率返回区间 [0,1) 中的任意一个小数。

即 x < 1 情况下， [0,x) 中的数出现的的概率是 x ，

如果我们要将

x < 1 情况下， [0,x) 中的数出现的的概率调整成 x^2 ，应该如何做？

问题1思路

由于 [0,x) 的概率是 x ，那么调用两次 Math.random() ，如果较大的那个值也要在 [0,x) 区间内，那么两次调用都必须在 [0,x) 区间内（因为任意一次在 [x,1) 都会导致返回值不在 [0,x) 上），即概率是 x^2 ，代码如下

 package snippet;

public class Code_0004_ rand ToPow2 {
    // 将`[0,x)`中的数出现的的概率调整成`x^2`
    public  static  double randToPow2() {
        return Math.max(Math.random(), Math.random());
    }
}  

我们可以通过如下测试代码来验证问题1的解法：

 package snippet;

public class Code_0004_RandToPow2 {
    // 将`[0,x)`中的数出现的的概率调整成`x^2`
    public static double randToPow2() {
        return Math.max(Math.random(), Math.random());
    }

    //  测试用例 
    public static  void  main(String[] args) {
        int count = 0;
        int testTimes = 10000000;
        double x = 0.17;
        for (int i = 0; i < testTimes; i++) {
            if (randToPow2() < x) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);
        System.out.println(Math.pow(x, 2));
    }
}  

打印的结果如下

 0.0288603
0.028900000000000006  

接近目标要求。

问题2

假设我们有一个 随机函数 f() ，这个函数可以等概率返回 [1,5] 中的一个数，如何 只利用 f() 函数 而不引入其他随机函数，得到一个等概率返回 [1,7] 中任意一个数的函数 g() 。

思路

由于目标是求 [1,7] 等概率返回一个，如果我们能加工得到一个 x() 函数，这个函数是等概率返回 [0,6] 范围内的任意一个数，那么目标函数 g() 只需要调用这个 x() 函数再加上1，即是 g() 函数要求

 public static int g() {
    return x() + 1;
}  

要得到 [0,6] 等概率返回一个数，我们 需要先得到一个0和1等概率返回的随机函数 m() ，我们可以通过 f() 函数来得到，即

 // 通过[0,5]等概率返回的随机函数f()
// 加工出等概率得到0和1
// 1,2,3,4,5 五个数
// 得到1，2的时候，返回0
// 得到4，5的时候，返回1
// 得到3的时候，弃而不用，再次尝试
    public static int m() {
        int ans = 0;
        do {
            ans = f();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }  

有了等概率返回 0 和 1 的随机函数 m() ， 我们可以很方便的生成 [0,6] 随机等概率返回一个数的方法，因为 [0,6] 需要三个 二进制 数表示，那么我们可以调用三次 m() 函数，可以等概率得到 [0,7] 范围内任意一个数，我们可以在得到 7 的时候，重试上述过程，只有结果在 [0,6] 才返回，这样就加工出了 x() 函数。

 // 等概率返回0~6
    public static int x() {
        int ans = 0;
        do {
            ans = (m() << 2) + (m() << 1) + m();
        } while (ans == 7);
        return ans;
    }  

最后，目标函数 f() 通过如下方式

 // 等概率返回1~7
    public static int g() {
        return x() + 1;
    }  

即可得到。完整代码如下

 package snippet;

public class Code_0005_Rand5ToRand7 {

    // 此函数只能用，不能修改
    // 等概率返回1~5
    public static int f() {
        return (int) (Math.random() * 5) + 1;
    }

    // 通过[0,5]等概率返回的随机函数f()
// 加工出等概率得到0和1
// 1,2,3,4,5 五个数
// 得到1，2的时候，返回0
// 得到4，5的时候，返回1
// 得到3的时候，弃而不用，再次尝试
    public static int m() {
        int ans = 0;
        do {
            ans = f();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

    // 等概率返回0~6
    public static int x() {
        int ans = 0;
        do {
            ans = (m() << 2) + (m() << 1) + m();
        } while (ans == 7);
        return ans;
    }

    // 等概率返回1~7
    public static int g() {
        return x() + 1;
    }

    
}  

问题3

见： LeetCode 470. Implement Rand10() Using Rand7()

和问题2思路一致，核心都是 要先实现一个等概率返回 0 和 1 的随机函数 m() 。 ，然后看目标函数区间需要几个二进制位，来决定调用几次 m() 函数，不赘述，完整代码见

 /**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a  random   integer  in the range 1 to 7
 */class Solution  extends  SolBase {
    public int rand10() {
        return rand(10);
    }

    public int rand(int N) {
        int bit = 1;
        int base = 2;
        while (base <= N) {
            base = 2 << bit;
            bit++;
        }
        int v = build(bit);
        while (v < 1 || v > N) {
            v = build(bit);
        }
        return v;
    }

     private  int build(int bit) {
        int v = 0;
        for (int i = 0; i < bit; i++) {
            v += (m() << i);
        }
        return v;
    }

    // 核心：生成 0 和 1 等概率返回的随机函数
    public int m() {
        int i = rand7();
        while (i == 7) {
            i = rand7();
        }
        return (i == 1 || i == 2 || i == 3) ? 0 : 1;
    }
}  

问题4

有一个函数 f() ，不等概率（但是是固定概率）返回0和1，如何只通过 f() 函数，得到等概率返回 0 和 1 的随机函数 g() ，

思路，

调用两次 f() 函数，可以得到如下情况

当两次都是0，或者两次都是1的时候，舍弃，虽然 0 和 1 的概率不一样，但是

概率一定一样

所以得到 0 1 就返回 0 ，得到 1 0 就返回1，即 g() 函数

完整代码如下

 package snippet;

// 不等概率随机函数变成等概率随机函数
public class Code_0005_EqualProbabilityRandom {

    // 不等概率函数，
    // 内部内容不可见
    public static int f() {
        return Math.random() < 0.8 ? 0 : 1;
    }

    // 等概率返回0和1
    public static int g() {
        int first;
        do {
            first = f(); // 0 1
        } while (first == f());
        return first;
    }

}