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()的解法

1. 就是我上面的解法，先生成均等概率的0和1，然后通过移位来产生1—Y

2. 当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} \]

3. 当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;
           }
       }
   };