04-05 17:22 已编辑 KCP地球市民日本语学校数学类

关注

经典面试问题:用 randX() 实现 randY()

在牛牛空间上看面经的时候经常会看到这样一个问题，就是现在有 randX()可以等概率给出 $1\sim X$ 范围内的随机数，现在要根据这个来实现 randY()

1. 当 $X > Y$ 时

其实很容易想到，当用大随机数生成小随机数时可以直接舍弃掉超出范围内的结果，只保留 $1\sim Y$ 范围内的结果，显然生成结果是等概率的，为了使算法更快，我们可以只舍弃掉最后的 $X \bmod Y$ 个数

int randY(int Y) {
    int res;
    do {
        res = randX();
    } while(res > X - X % Y);
    return (res % Y) + 1;
}

期望次数为( ${m:= X - X \bmod Y}$ )

$\begin{align*}\lim_{n\to \infty}S_n = \lim_{n\to\infty}(\frac{m}{X}+(\frac{m}{X})^2+\cdots +(\frac{m}{X})^n) = \frac{m}{X-m}\end{align*}$

2. 当 $X < Y$ 时

现在忘掉原问题，改为: 现在有一个 randX() 和 randY() 如何等概率地生成 $1\sim X\times Y$ 内的数呢？其实很简单，可以把它想象为一个有 $X$ 和 $Y$ 列的矩阵，如何将这个二维矩阵映射到一维的 $1\sim X\times Y$ 范围内，对于位置 $(i, j)$ (从1开始) ，只需要构造映射函数为 $(i - 1)\times Y + j$ 即可。自然地: 可以使用 (randX() - 1) * Y + randY() 来等概率地生成 $1\sim X\times Y$ 内的数了。

接下来，考虑 3 维矩阵映射到 1 维，即现在有 randX()、randY() 和 randZ() 要映射到 $1\sim X\times Y\times Z$ ，可以通过 (randX - 1) * (Y * Z) + (randY - 1) * Z + randZ() 来实现

得出一般性的结论，一个 $n$ 维矩阵，矩阵维度分别为 $d_1\times d_2\times \cdots d_n$ ，而 $(i_1,i_2,\cdots,i_n)$ 表示元素的 $n$ 维坐标，则一维映射公式可以表示为(令 $d_{n+1} = 1$ )

$\begin{align*}\mathrm{index} = \sum_{k = 1}^n (i_k - 1)\times (\prod_{j = k+1}^{n+1} d_j) + 1\end{align*}$

映射函数只需要将公式里的 $i_k$ 分别替换为对应的 Rand() 函数即可。

现在回到问题，怎么通过 randX() 来实现 randY() 呢？

很简单，我们只需要进行多次采样，假设每次采样的结果为 $1\sim d_i(d_i\le X)$ ，然后通过 $d_i$ 的组合

$\begin{align*}d_1\times d_2\times \cdots d_n \ge Y\end{align*}$

通过之前构造的映射函数，我们实现了 $1\sim d_1\times d_2\times \cdots d_n$ 的 rand() 方法，获取 randY() 就只需要像情况1一样把多余的部分舍弃掉就好了。至于怎么通过 randX() 来获取 randd_i 呢？还是和情况1一样。

理论上来说，我们可以随意的按照想要的方式对采样方式进行组合，只要满足 $d_1\times d_2\times \cdots d_n \ge Y$ 就行了，但是不同的组合方式在性能上却不同，我们总是想要找出一种最优的组合方式。

其实现在的问题就转化成为了，需要找一个最大质因子不超过 $X$ 的数 $m(m\ge Y)$ ，然后对 $m$ 进行质因数分解，如此就能知道需要进行多少组采样，而在具体操作中，可以将一些较小的 $d_i$ 进行合并，以减少采样次数，比如 $X = 7$ ， $d_1 = 2$ ， $d_2 = 3$ ，就不需要进行两次采样，而是进行 $d' = d_1\times d_2 = 6$ 一次采样。

例: 用 rand7() 构造 rand100()

100 分解质因数后为 $2\times 2\times 5\times 5$ ，其中 $2\times 2$ 可以合并为 $4(4<7)$ ，所以可以按照 $d = \{4, 5, 5\}$ 进行 3 次采样，映射函数如上可以写为

$(rand4 - 1)\times 25 + (rand5 - 1)\times 5 + (rand5 - 1) + 1$

代码如下

// Big to Small, randX->randY
int randB2S(int Y) {
    int res;
    do {
        res = randX();
    } while(res > X - X % Y);
    return (res % Y) + 1;
}

int rand100() {
    int first = randB2S(4);
    int second = randB2S(5);
    int third = randB2S(5);
    return (first - 1) * 25 + (second - 1) * 5 + third;
}

最后: 关于上面的最少采样次数是很难通过一个统一的方法去找到它对应的解，只能根据具体的情况去找，所以是无法设计一个统一的 rand(int Y) 算法并且满足对 $Y$ 最优的。

#面经##春招##暑期实习##计算机##算法#