题目

题目来源：力扣（LeetCode）

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。


示例 1:

输入: 1
输出: [7]

示例 2:

输入: 2
输出: [8,4]

示例 3:

输入: 3
输出: [8,1,10]

提示:

rand7 已定义。
传入参数: n 表示 rand10 的调用次数。

思路分析

定理：若 rand_n() 能等概率生成1到n的随机整数，则有(rand_n() - 1) n + rand_n() 能等概率生成 1 到 n n 的随机整数。

解释：rand()7能等概率生成{1, 2, 3, 4, 5, 6, 7}
　　　rand7() - 1能等概率生成{0, 1, 2, 3, 4, 5, 6},
　　　(rand7() - 1) 7能等概率生成{0, 7, 14, 21, 28, 35, 42},
　　　(rand7() - 1) 7 + rand7()能等概率生成1~49。

拒绝采样：在拒绝采样中，如果生成的随机数满足要求，那么久返回该随机数，否则会不断生成直到一个满足要求的随机数为止

  1. /**
  2.  * The rand7() API is already defined for you.
  3.  * var rand7 = function() {}
  4.  * @return {number} a random integer in the range 1 to 7
  5.  */
  6. /**
  7.  * 思路：
  8.  *  
  9.  * （1）由大的随机数 生成小的随机数是方便的，如 rand10 -> rand7
  10.  *      只需要用 rand10 生成等概率的 1 ~ 10 ，然后判断生成的随机数 num ，如果 num <= 7 ，则返回即可
  11.  *      
  12.  * （2）如何由小的随机数生成大的随机数呢？
  13.  *      考虑这样一个事实：
  14.  *      randX() 生成的随机数范围是 [1...X]
  15.  *      (randX - 1) * Y + randY() 可以等概率的生成的随机数范围是 [1, X*Y]
  16.  *     因此， 可以通过 (rand7 - 1) * 7 + rand7() 等概率的生成 [1...49]的随机数
  17.  *     我们可以选择在 [1...10] 范围内的随机数返回。
  18.  *  
  19.  * （3）上面生成 [1...49] 而 我们需要 [1...10]，[11...49]都要被过滤掉，效率有些低
  20.  *      可以通过减小过滤掉数的范围来提高效率。
  21.  *      比如我们保留 [1...40]， 剩下 [41...49]
  22.  *      为什么保留 [1...40] 呢？ 因为对于要生成 [1...10]的随机数，那么 
  23.  *      可以等概率的转换为 1 + num % 10 , suject to num <= 40
  24.  *      因为 1 ... 40 可以等概率的映射到 [1...10]
  25.  *      那么如果生成的数在 41...49 怎么办呢？，这些数因为也是等概率的。
  26.  *      我们可以重新把 41 ... 49 通过 num - 40 映射到 1 ... 9，可以把 1...9 重新看成一个
  27.  *      通过 rand9 生成 rand10 的过程。
  28.  *      (num - 40 - 1) * 7 + rand7() -> [1 ... 63]
  29.  *      if(num <= 60) return num % 10 + 1;
  30.  *      
  31.  *      类似的，[1...63] 可以 划分为 [1....60] and [61...63]
  32.  *      [1...60] 可以通过 1 + num % 10 等概率映射到 [1...10]
  33.  *      而 [61...63] 又可以重新重复上述过程，先映射到 [1...3]
  34.  *      然后看作 rand3 生成 rand10
  35.  *      
  36.  *      (num - 60 - 1) * 7 + rand7() -> [1 ... 21]
  37.  *      if( num <= 20) return num % 10 + 1;
  38.  *      
  39.  *      注意：这个映射的范围需要根据 待生成随机数的大小而定的。
  40.  *      比如我要用 rand7 生成 rand9
  41.  *      (rand7() - 1) * 7 + rand7() -> [1...49]
  42.  *      则等概率映射范围调整为 [1...45]， 1 + num % 9
  43.  *      if(num <= 45) return num % 9 + 1;
  44.  */
  45. var rand10 = function() {
  46.   while(true) {
  48.     let x = rand7()
  49.     let num = (rand7() - 1) * 7 + rand7() // rand7() 每次调用的值都不同，故不要用变量来存
  50.     if (num <= 40) return num % 10 + 1;   // 大于 40 的数，拒绝采样
  52.     x = num - 40;                         // 此时 x = rand9()
  53.     num = (x - 1) * 7 + rand7();          // rand63
  54.     if (num <= 60) return num % 10 + 1;   // 大于 60 的数，拒绝采样
  56.     x = num - 60;                         // 此时 x = rand3()
  57.     num = (x - 1) * 7 + rand7();          // rand21
  58.     if (num <= 20) return num % 10 + 1    // 大于 20 的数，拒绝采样
  59.   }
  61. };

推荐阅读：从最基础的讲起如何做到均匀的生成随机数