Leetcode题解（6）：用Rand7实现Rand10
在解决这道题之前，我们可以先查看一个反过来的情况——用 $Rand10()$ 实现 $Rand7()$ ，可以直接发现实现方式就是不断用 $Rand10()$ 生成随机数，直到生成的数字处于 $1 \sim 7$ 之间即可。也就是说，如果可以生成的数字范围要大于待生成的数字范围，可以通过不断循环直到获取落在生成范围里面的数字的方式实现。
利用上述思想，我们可以很容易的想出这道题的解法——利用 $Rand7()$ 构造一个生成的数字范围大于 $1 \sim 10$ 的随机数生成器即可。要想构造这样的生成器，我们可以再观察下 $Rand10()$ 。如果我们想要用 $Rand10()$ 构造一个生成数字范围在 $1 \sim 99$ 之间的随机数生成器，可以使用如下算法 $(Rand10() - 1) * 10 + Rand10()$ ，也就是生成两次，一个作为十位一个作为个位。可以很容易发现这种算法生成的数字是随机均匀分布的。
使用 $Rand10()$ 的例子生成的是 $10$ 进制二位数，利用同样的思想我们也可以生成 $7$ 进制二位数，即 $(Rand7() - 1) * 7 + Rand7()$ ，使用这种方式生成的数字也是随机均匀分布的。将其转为 $10$ 进制后，数字范围落在 $1 \sim 49$ 之间，如果直接抛弃 $11 \sim 49$ 之间的数字，那么可能需要重复调用很多次。因此我们可以只抛弃 $41 \sim 49$ 之间的数字，对剩余的数字采用取模运算，实现方式如下：
class Solution extends SolBase {
public int rand10() {
int num;
do {
num = (rand7() - 1) * 7 + rand7();
} while (num > 40);
return num % 10 + 1;
}
}
上述的实现方式是抛弃了 $41 \sim 49$ 之间的数字，抛弃了 $9$ 个数字的实现方式还是有点多的。从我们之前的讲解来看，可以不局限于生成两位数，三位数、四位数也是可以的，因此我们也可以这样实现：首先生成 $7$ 进制两位数，如果不大于 $40$ ，返回，否则利用两位数再次生成 $3$ 位数、$4$ 位数。对于 $Rand7()$ ，我们只需要生成到 $7$ 进制 $4$ 位数就行了，因为 $7^3=243$ ，$7^4=1701$ ，也就是 $4$ 位数最多只需要抛弃 $1$ 个数字，而如果是 $5$ 位数，则又要抛弃 $7$ 个数字才行。
我们也可以利用取模 $10$ 这个点来进一步简化算法。如果生成的数字在 $41 \sim 49$ 之间，没有必要直接用该数字进行计算，因为 $40$ 在取模这一步会被消掉，无论乘以哪个数字，所以我们可以将生成的数字减去 $40$ 再进行计算。减去 $40$ 后生成的数字范围在 $1 \sim 63$ 之间，同样的，如果生成了 $61 \sim 63$ 之间的数字，也可以减去 $60$ 后再计算。实现方式如下：
class Solution extends SolBase {
public int rand10() {
int num;
while (true) {
num = (rand7() - 1) * 7 + rand7();
if (num <= 40) break;
num = (num - 40 - 1) * 7 + rand7();
if (num <= 60) break;
num = (num - 60 - 1) * 7 + rand7();
if (num <= 20) break;
}
return num % 10 + 1;
}
}