题目见Leetcode470. 用 Rand7() 实现 Rand10()

大化小

https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/xiang-xi-si-lu-ji-you-hua-si-lu-fen-xi-zhu-xing-ji/

如果要求rand10()得到rand7(),那么直接调用rand10(),直到所得数字落在$[1, 7]$,证明略去。

小化大

rand7() 生成 rand10() 为例。

万能构造法:独立随机事件+古典概型

转自 https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/mo-neng-gou-zao-fa-du-li-sui-ji-shi-jian-9xpz/

任意的 randX() 都可以用以下方法构造:

  1. 构造 $n$ 次相互独立的采样,其中第 $i$ 次采样有 $m_i$ 种结果,且第 $i$ 次采样中每种结果的概率是 $\frac{1}{m_i} $。$n$ 要满足 $m_1 * m_2 * \cdots * m_n \ge X$ ,即把所有采样结果组合起来,最终的结果数量不少于 $X$,保证可以映射到 $[1,X]$ 的每一个元素。这样做的好处是,我们构造了 $m_1*m_2*\cdots*m_n $个结果,并且每个结果的概率都是 $\frac{1}{m_1*m_2*\cdots*m_n} $
  2. 从 $m_1*m_2*\cdots*m_n$ 个结果中取 $X$ 个,映射到 $[1,X]$ 区间,我们就得到了一个均匀分布在 $[1,X]$ 的随机数发生器。

第二步中的映射是 1:1 映射,实际运用中,第二步可以取 $k*X$ 个结果来做 $k:1$ 映射,以减少调用 rand7() 次数的期望。

class Solution {
public: 
  int rand10() {
    int first, second;
    while ((first = rand7()) > 6);
    while ((second = rand7()) > 5);
    return (first&1) == 1 ? second : 5+second;
  }
};

多次拒绝采样

来自https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/jin-dao-iudai-ni-jie-jue-sui-ji-hua-suan-68xw/

扩展随机数范围

为了能够生成连续递增的分布,我们可以通过加减乘除操作改变rand7生成的范围,如下:

rand7 - 1 = [0, 1, 2, 3, 4, 5, 6]

单独的加减操作可以生成均匀随机整数范围,相当于对生成的范围进行平移。

7 * rand7 = [7, 14, 21, 28, 35, 42, 49]

单独的乘除操作也可以生成均匀随机整数范围,但不是连续递增的。

(7 * rand7) - (rand7 - 1) = [1, ..., 49]

如下图所示,把加减操作和乘除操作结合起来可以生成1...49的均匀分布,每一个数字出现的概率都是1/49。

yn8Ty.png

这样取1-40,然后根据个位数就能确定本次生成的随机数。

这样一来就要丢掉9个数(41-49),我们认为有点多,既然有了41-49,相当于rand9(),那么根据上面的方法再来一轮:

7 * rand9() - rand7() + 1

可以生成1-63的随机数,那么这次只需抛弃3个数,相当于rand3(),同理:

7 * rand3() - rand7() + 1

生成1-21,只需抛弃一个数,到这儿就足够了。综合代码:

class Solution {
public:
    int rand10() {
        while(1){
            int num = rand7() * 7 -rand7() + 1;
            if (num < 41) return num % 10 + 1;
            num = (num - 40) * 7 - rand7() + 1;
            if (num < 61) return num % 10 + 1;
            num = (num - 60) * 7 - rand7() + 1;
            if (num < 21) return num % 10 + 1;
        }
    }
};

K进制

另一种想法是把调用k次rand7()等同于一个k位的7进制数,例如两次调用就是两位7进制数,转化成十进制就是49种取值(1-49或者0-48,看算式的表达)。这种思路从抛硬币(相当于二进制数)转化而来。参考https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/cong-pao-ying-bi-kai-shi-xun-xu-jian-jin-ba-zhe-da/

/**
 * 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 {
public:
    int rand10() {
        while (true) {
            int n = 7 * (rand7() - 1) + (rand7() - 1);
            if (n >= 1 && n <= 40) {
                return n % 10 + 1;
            }
        }
    }
}
// https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/jin-dao-iudai-ni-jie-jue-sui-ji-hua-suan-68xw/
最后修改:2022 年 03 月 01 日
如果觉得我的文章对你有用,请随意赞赏