【LeetCode】用 Rand7() 实现 Rand10()
rand7表示可生成 1 到 7 范围内的均匀随机数，rand10生成 1 到 10 范围内的均匀随机整数。
如果使用rand10去实现rand7，这个就很容易，我们只要舍弃掉大于 7 的数就可以了。
那么反过来怎么搞呢？
首先我们要能表示出来 1 到 10 这几个数，当rand7生成的最大数为 7 ，此时使用 7 表示8-14就如下所示：
7 + 1 = 8 7 + 2 = 9 7 + 3 = 10 7 + 4 = 11 7 + 5 = 12 7 + 6 = 13 7 + 7 = 14
对于上面的计算，我们可以表示在一个 7 的基础上，加上一个随机的1-7，表示8-14的随机数，抽象公式为：7 + rand7()
如果还需要知道15 - 21，那就是在两个 7 的基础上，加上一个1-7的随机数，接下来我们看看下面这个式子：
0 * 7 + rand7() => [1,7] 1 * 7 + rand7() => [8,14] 2 * 7 + rand7() => [15,21] 3 * 7 + rand7() => [22,28]
关于上面的式子，如果我们使用公式表示为：a * Y + rand_Y()，此时表示的是在 Y 的基础上，随机出现比它更大的一个范围的数，如果我们要把这些[1,7],[8,14],[15,21]小范围串起来，并保证[1,21]这些数的出现的几率一样，那么此时就要保证a出现的数字概率是一样的。此时公式就可以变为(rand_X() - 1) * Y + rand_Y()。这个式子表示可以等概率的生成[1, X * Y]范围的随机数。
(rand_X() - 1) * Y + rand_Y() => [1, X * Y]
看完公式的由来，接着看这道题，这里只有rand7()，直接把它套进公式，它能表示的范围是[1,49]，我们可以使用生成的数除以 10 ，然后取余数，最后加上 1 ，表示随机生成 1-10
10 % 10 = 0 => 0 + 1 = 1 11 % 10 = 1 => 1 + 1 = 2 …… 19 % 10 = 9 => 9 + 1 = 10
因为这个只能到 49，而不是到 50，所以导致最后的生成 2-10的概率要比 1高一些，所以这时候我们要用到“拒绝采样”了，这就是表示如果采样的数值不在要求范围之内，我们就要舍弃掉。然后我们就要把大于40的数舍弃掉。
public int rand10() { int num = (rand7() - 1) * 7 + rand7(); while (num > 40) { num = (rand7() - 1) * 7 + rand7(); } return num % 10 + 1; }
当然也可以做一些优化，尽量减少要舍弃的数值，提高命中率。
public int rand10() { int num = (rand7() - 1) * 7 + rand7(); while (num > 40) { // 生成的数在41-49之间，再操作一遍就在 1-63 之间了 num = (num - 40 - 1) * 7 + rand7(); if (num <= 60) return num % 10 + 1; // 生成的数在61-63之间，再操作一遍就在 1-21 之间了 num = (num - 60 - 1) * 7 + rand7(); if (num <= 20) return num % 10 + 1; // 重新生成随机数 num = (rand7() - 1) * 7 + rand7(); } return num % 10 + 1; }
