算法描述
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
进阶:
rand7()调用次数的 期望值 是多少 ?- 你能否尽量少调用
rand7()?
示例：
输入: 3 输出: [8,1,10] 提示: rand7 已定义。 传入参数: n 表示 rand10 的调用次数。
算法流程
part1：正向公式推导
假设已知rand2()可以均匀的生成[1,2]的随机数，现在想均匀的生成[1,4]的随机数，该如何考虑？
// 很可能首先会考虑相加 rand2() + rand2() = ? ==> [2,4] 1 + 1 = 2 1 + 2 = 3 2 + 1 = 3 2 + 2 = 4 // 为了把生成随机数的范围规约成[1,n]，于是在上一步的结果后减1 (rand2()-1) + rand2() = ? ==> [1,3] 0 + 1 = 1 0 + 2 = 2 1 + 1 = 2 1 + 2 = 3 // 显然生成的结果不是等概率的，由于值的多种组合导致，必然造成这种结果，尝试如下改动： (rand2()-1) × 2 + rand2() = ? ==> [1,3] 0 + 1 = 1 0 + 2 = 2 2 + 1 = 3 2 + 2 = 4
神奇的事情发生了，奇怪的知识增加了。通过这样的处理，得到的结果恰是[1,4]的范围，并且每个数都是等概率取到的。因此，使用这种方法，可以通过rand2()实现rand4()。
也许这么处理只是我运气好，而不具有普适性？那就多来尝试几个例子。比如：
(rand9()-1) × 7 + rand7() = result a b
总结一下：
已知 rand_N() 可以等概率的生成[1, N]范围的随机数 那么： (rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数 即实现了 rand_XY()
part2：反向实现
那么想到通过rand4()来实现rand2()呢？这个就很简单了，已知rand4()会均匀产生[1,4]的随机数，通过取余，再加1就可以了。如下所示，结果也是等概率的。
rand4() % 2 + 1 = ? 1 % 2 + 1 = 2 2 % 2 + 1 = 1 3 % 2 + 1 = 2 4 % 2 + 1 = 1 //事实上，只要rand_N()中N是2的倍数，就都可以用来实现rand2()，反之，若N不是2的倍数，则产生的结果不是等概率的。比如： rand6() % 2 + 1 = ? 1 % 2 + 1 = 2 2 % 2 + 1 = 1 3 % 2 + 1 = 2 4 % 2 + 1 = 1 5 % 2 + 1 = 2 6 % 2 + 1 = 1 rand5() % 2 + 1 = ? 1 % 2 + 1 = 2 2 % 2 + 1 = 1 3 % 2 + 1 = 2 4 % 2 + 1 = 1 5 % 2 + 1 = 2
part3：本题实现（拒绝采样）
有了前面的分析，要实现rand10()，就需要先实现rand_N()，并且保证N大于10且是10的倍数。这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。
而实现rand_N()，我们可以通过part 1中所讲的方法对rand7()进行改造，如下：
(rand7()-1) × 7 + rand7() ==> rand49()
但是这样实现的N不是10的倍数啊！这该怎么处理？这里就涉及到了“拒绝采样”的知识了，也就是说，如果某个采样结果不在要求的范围内，则丢弃它。基于上面的这些分析，再回头看下面的代码，想必是不难理解了。
class Solution extends SolBase { public int rand10() { while(true) { int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数 if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数 } } }
part4：优化方案
这部分具体的代码是参考官方题解的，不过是我自己在理解了part 1和part 2之后才看懂的，一开始看真不知道为什么（/(ㄒoㄒ)/~~...
根据part 1的分析，我们已经知道(rand7() - 1) * 7 + rand7() 等概率生成[1,49]范围的随机数。而由于我们需要的是10的倍数，因此，不得不舍弃掉[41, 49]这9个数。优化的点就始于——我们能否利用这些范围外的数字，以减少丢弃的值，提高命中率总而提高随机数生成效率。
代码实现
/** * 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 extends SolBase { public int rand10() { while (true) { int a = rand7(); int b = rand7(); int num = (a - 1) * 7 + b; // rand49 if (num <= 40) return num % 10 + 1; a = num - 40; // rand9 b = rand7(); num = (a - 1) * 7 + b; // rand63 if (num <= 60) return num % 10 + 1; a = num - 60; // rand3 b = rand7(); num = (a - 1) * 7 + b; //rand21 if (num <= 20) return num % 10 + 1; } } }
总结
本题实现的关键：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数 即实现了 rand_XY()
优化的关键：减少丢弃值的数量，利用拒绝采样，不断更新rand_X()。
