470.用Rand7()实现Rand10()
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。不要使用系统的 Math.random() 方法。
示例 1:
输入: 1
输出: [7]
示例 2:
输入: 2
输出: [8,4]
示例 3:
输入: 3
输出: [8,1,10]
? 看到这题我一开始的想法是先构造等概率的0和1，然后构建0001-1010(二进制的1-10)这样应该是等概率的。
class Solution {
public:
int rand1()
{
int a = rand7();
while(a==4)
{
a = rand7();
}
return a<4?0:1;
}
int rand10() {
int res;
while(true){
res = (rand1()<<3)+(rand1()<<2)+(rand1()<<1)+(rand1());
if(res>0&&res<11) return res;
}
}
};
然后发现速度太慢，打开官方题解一脸懵逼，然后多看了几篇别人的题解慢慢理解了思路。
总结下从RandX()——>RandY()的解法
-
就是我上面的解法，先生成均等概率的0和1，然后通过移位来产生1—Y
-
当X>Y的时候，比较简单，可以不断的调用RandX()直到产生1—Y。具体的概率证明在下：
当第一次命中的时候概率为\(\frac{1}{X}\)???。
如果第二次命中，那么第一次必然没有命中,那概率则为第一次未命中的概率乘上第二次命中的概率\(\frac{Y-X}{X}*\frac{1}{X}\)?
依次类推，
\[\begin{align} & P=\frac{1}{X}+\frac{Y-X}{X}*\frac{1}{X}+(\frac{Y-X}{X})^2*\frac{1}{X}+\cdots+(\frac{Y-X}{X})^n*\frac{1}{X}\& =\frac{1}{X}*(1+\frac{Y-X}{X}+(\frac{Y-X}{X})^2+\cdots+(\frac{Y-X}{X})^n)\& =\frac{1}{X}*(1+\frac{\frac{Y-X}{X}*(1-(\frac{Y-X}{X})^n)}{1-\frac{Y-X}{X}})\& =\frac{1}{X}*(1+\frac{Y-X}{2X-Y})\& =\frac{1}{X}*(\frac{X}{2X-Y})\& =\frac{1}{2X-Y} \end{align} \] -
当X<Y的时候，我们可以用到(RandX()-1)*X+RandX()生成\(1-X^2\)的随机整数
然后通过拒绝采样(当生成的数>Y时重新生成)
以此题为例代码如下
class Solution { public: int rand10() { int a,b,res; do{ a = rand7(); b = rand7(); res = (a-1)*7+b; }while(res>40); return (res-1)%10+1; } };当然这样我们舍弃的数字还是比较多，我们如何进一步的优化利用被舍弃的这些数，当生成的随机数被拒绝的时候我们也同时产生了1-9的随机数，如果在调用一次rand7()，我们就能生成1-63的随机数，我们再拒绝61-63，再调用一次rand7()生成1-21的随机数，拒绝21，此时只剩下随机数1
class Solution { public: int rand10() { while(true){ int a = rand7(); int b = rand7(); int num = (a-1)*7+b; //rand49() if(num<=40) return (num-1)%10+1; a = num - 40; //rand9() b = rand7(); num = (a-1)*7+b; //rand63() if(num<=60) return (num-1)%10+1; a = num - 60; //rand3() b = rand7(); num = (a-1)*7+b; //rand21() if(num<=20) return (num-1)%10+1; } } };