:::warning 💡随机数生成的题目是已有的随机数函数randX可以等概率的生成1至X的整数，现在需要通过randX实现随机数函数randY :::

一、大随机数生成小随机数

如果X大于Y，例如通过rand7()实现rand5()，rand7可以等概率的生成1-7，这里面包含了1到5。我们可以直接舍弃6和7来实现随机生成1至5（如下代码），那么有一个问题，这样的rand5生成的每个数是等概率的吗？

int rand5() {
    while (true) {
        int a=rand7();
        if (a<=5) return a;
    }
}

从上述的代码可以看出，rand7产生的每个数的概率是1/7，如果产生6，7这两个数就会重新随机。那么在rand5中每个数的随机可能是第一次产生的，也有可能是舍弃6和7的第二次，第三次，第n次产生的，那么以1为例，可以计算出它的概率如下：

上述计算说明rand5是等概率地生成1,2,3,4,5的(1/5的概率)。而且， 我们可以得到一个一般的结论，如果X > Y，那么一定可以用randX去实现randY。这个通用的代码如下。

int randY() {
    while (true) {
        int a=randX();
        if (a<=X) return a;
    }
}

二、小随机数生成大随机数

上一节证明了通过舍弃的方法通过rand7得到rand5，如果反过来就不可行了，因为rand5没有办法产生6和7。那么可不可以通过两个rand5，相乘或者相加来得到大于5的数呢？

相乘

首先尝试一下相乘的方法，{1，2，3，4，5}*{1，2，3，4，5}可以得到

可以分别计算概率，找到7个等概率的数进行组合，但是这种方法不够灵活，而且调用了太多次rand5。

相加

为了简化过程，以rand2产生rand4为例。首先看直接相加的过程，无法同时得到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减一之后乘以2再相加，可以惊奇的发现，可以等概率的生成1，2，3，4.

(rand2()-1) × 2 + rand2() = ? ==> [1,3]
   0            +   1     = 1
   0            +   2     = 2
   2            +   1     = 3
   2            +   2     = 4

不知道是不是巧合，再拿rand3试试

可以看出rand3可以等概率的生成1至9。这里可以记住这个结论 :::warning (randX() - 1) Y + randY() 可以等概率的生成[1, X Y]范围的随机数 ::: 有了这个结论，我们就可以将问题简化成上一节的场景，即大随机数生成小随机数。
那么rand5可以先得到rand25，再实现rand7，但是从25到7也舍弃掉太多了，其实这里可以通过取余再加一的方式，把7的倍数内的数也用上。以rand4产生rand2为例：

rand4() % 2 + 1 = ?
1 % 2    + 1 = 2
2 % 2    + 1 = 1
3 % 2    + 1 = 2
4 % 2    + 1 = 1

其中加1是为了避免产生0，可以看出对2取余之后生成两组1，2，他们都是等概率的。这里rand4刚好是2的整数倍，如果不是整数倍，可以直接将多余的余数丢弃即可。

实战

以leetcode题目为例
470. 用 Rand7() 实现 Rand10()
可以通过产生rand49，对于大于40的进行拒绝采样，小于40的再取余加一即可。代码如下：

int rand10() {
    while (true) {
        int a=rand7();
        int b=rand7();
        int num = (a-1)*7+b;
        if (num<=40) return num%10+1;
    }
}

上述代码，丢弃了9个数，这9个数也是等概率的，可以进一步优化，通过rand9和rand7产生rand63，这样只需要丢弃3个数。

int rand10() {
    while (true) {
        int a=rand7();
        int b=rand7();
        int num = (a-1)*7+b;
        if (num<=40) return num%10+1;
        num -= 40;
        num = (num-1)*7+rand7();
        if (num<=60) return num%10+1;
    }
}

继续优化丢弃的三个数，3*7得21，这次只需要丢弃一个数。

int rand10() {
    while (true) {
        int a=rand7();
        int b=rand7();
        int num = (a-1)*7+b;
        if (num<=40) return num%10+1;

        num -= 40;
        num = (num-1)*7+rand7();
        if (num<=60) return num%10+1;

        num -= 60;
        num = (num-1)*7+rand7();
        if (num<=20) return num%10+1;
    }
}

参考：
https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/cong-zui-ji-chu-de-jiang-qi-ru-he-zuo-dao-jun-yun-/