470.用 Rand7() 实现 Rand10()

题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:

输入: 1
输出: [7]

示例 2:

输入: 2
输出: [8,4]

示例 3:

输入: 3
输出: [8,1,10]

提示:

1. rand7 已定义。
2. 传入参数: n 表示 rand10 的调用次数。

进阶:

1. rand7()调用次数的 期望值 是多少 ?
2. 你能否尽量少调用 rand7() ?

   思路

3. 重复调用10次rand7(),这样能够生成1~70的随机数，接着对10取余即可。
4. 基于公式
   $$(randX()-1)*randY()+randY()$$
   生成1~X*Y之内的随机数。

• 为了减少对rand7()的调用，需要对不同的1~X*Y之内的随机数进行判断。
  • 首先生成1~49之间的数，如果在1~40之间，直接对10取余即可。
  • 如果在41~49之间，减去40后就是一个1~9之间的随机数，仍然调用以上公式，生成1~63之间的随机数。
    • 如果在1~60之间，直接对10取余即可。
    • 如果在61~63之间，减去60后就是一个1~3之间的随机数，仍然调用上述公式，生成一个1~21之间的随机数……
      到这里，如果想要继续嵌套可以，但是此时还没有生成的概率已经很小了。如果还没有生成直接在大循环中重新生成也可以。

3. 其他思考
   我尝试将两种概率分布都转化为正态分布，
   $$\frac{(rand7()-mean(rand7())}{std(rand7()))}=\frac{(rand10()-mean(rand10())}{std(rand10())}$$
   之后移项的方式来进行生成，但是不知道为什么一直不对：
   $$\frac{(rand7()-mean(rand7())*std(rand10())}{std(rand7())}+mean(rand10()))=rand10()$$

代码

1. 暴力法

   // The rand7() API is already defined for you.
   // int rand7();
   // @return a random integer in the range 1 to 7
   
   class Solution {
   public:
   int rand10() {
       int n = 0;
       for(int i=0;i<10;i++) n+=rand7();
       return n%10+1;
   }
   };

2. 公式法

   // The rand7() API is already defined for you.
   // int rand7();
   // @return a random integer in the range 1 to 7
   
   class Solution {
   public:
       int rand10() {
           while(true){
               int num = (rand7()-1)*7+rand7();
               if(num<=40) return 1+num%10;
               num = (num-40-1)*rand7()+rand7();
               if(num<=60) return 1+num%10;
               num = (num-60-1)*rand7()+rand7();
               if(num<=20) return 1+num%10;
           }
           return -1;
       }
   };