前言

LeetCode死磕系列十二： 数学基础

说实话，其实都是刷题都是数学的实现，不过感觉有些题目更加偏向数学应用，譬如蓄水池，等概率抽样…。

题目

470 用rand7()实现Rand10()

从最基础的讲起如何做到均匀的生成随机数

从上述的文章可以得出：

已知: $randN()$可以==等概率==生成$[1, N]$范围的数字
那么: $(randN()-1) \times Y + randY()$可以==等概率==生成$[1, Y \times N]$ 范围的数字

即：实现了$randNY()$

以$[(rand9() - 1) \times 7 + rand7()]$为例子

rand9()-1\rand7 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
1 8 9 10 11 12 13 14
2 15 16 17 18 19 20 21
3 22 23 24 25 26 27 28
4 29 30 31 32 33 34 35
5 36 37 38 39 40 41 42
6 43 44 45 46 47 48 49
7 50 51 52 53 54 55 56
8 57 58 59 60 61 62 63

是不是很神奇，数学证明不会

那么想到通过rand4()来实现rand2()呢？这个就很简单了，已知rand4()会均匀产生[1,4]的随机数，通过取余，再加1就可以了。如下所示，结果也是等概率的。

rand4() % 2 + 1 = ?
   1 % 2    + 1 = 2
   2 % 2    + 1 = 1
   3 % 2    + 1 = 2
   4 % 2    + 1 = 1

事实上，只要rand_N()中N是2的倍数，就都可以用来实现rand2()，反之，若N不是2的倍数，则产生的结果不是等概率的。比如：

rand6() % 2 + 1 = ?
   1 % 2    + 1 = 2
   2 % 2    + 1 = 1
   3 % 2    + 1 = 2
   4 % 2    + 1 = 1
   5 % 2    + 1 = 2
   6 % 2    + 1 = 1

rand5() % 2 + 1 = ?
   1 % 2    + 1 = 2
   2 % 2    + 1 = 1
   3 % 2    + 1 = 2
   4 % 2    + 1 = 1
   5 % 2    + 1 = 2

通用一些的

如果需要实现$randX()$

  1. 先实现$randN()$
    1. $N$为$X$的倍数（$N>X$）
  2. 再通过 $randN() \% X + 1$即可
public int rand10() {
        // rand 49
        while (true) {
            int num = (rand7() - 1) * 7 + rand7();  // rand49
            if (num <= 40) { // 使用拒绝采样，得到rand40
                return num % 10 + 1;  // rand10
            }
        }
    }

优化

class Solution extends SolBase {
      // 上述拒绝了9个数字，
    // 优化之后，减少丢弃值，提高命中率
    public int rand10() {
        while(true) {
            int a = rand7();
            int b = rand7();
            int num = (a-1)*7 + b; // rand 49
            if(num <= 40) return num % 10 + 1; // 拒绝采样

            a = num - 40; // rand 9
            b = rand7();
            num = (a-1)*7 + b; // rand 63
            if(num <= 60) return num % 10 + 1;

            a = num - 60; // rand 3
            b = rand7();
            num = (a-1)*7 + b; // rand 21
            if(num <= 20) return num % 10 + 1;
        }
    }
}