Rand7生成Rand10

数学原理

数学定律：$(randX() - 1) * Y + randY()$ 可以生成等概率的$[1, X * Y]$范围内的随机数

证明：由于$randX()$可以生成$[1, X]$之间的等概率随机数， $randY()$可以生成$[1, Y]$之间的等概率随机数

那么$(randX() - 1)*Y$可以在 $[0, Y, 2Y, 3Y, ..., (X - 1)Y]$ 中随机采样 ，

因此$(randX() - 1) * Y + randY()$所构成的联合概率表为：

$$\begin{matrix} & 0 & Y & 2Y & 3Y & ... & (X - 1)Y\\ 1 & 1 & Y+1 & 2Y+1 & 3Y+1 &...& (X- 1)Y + 1\\ 2 & 2 & Y+2 & 2Y+2 & 3Y+2 & ... & (X - 1)Y +2\\ 3 & 3 & Y+3 & 2Y+3 & 3Y+3 & ... & (X - 1)Y +3\\ ...& ...&...&...&...&...&...\\ Y & Y & 2Y & 3Y & 4Y & ... & XY\\ \end{matrix}$$

所以，从表中可以看到，能够均匀采样出$[1, XY]$之间的随机数

代码

根据上面公式，如果想通过$rand7$生成$rand10$, 可以先构造出$(rand7 - 1) * 7 + rand7$, 这样就做到了在$[1, 49]$之间均匀随机采样

代码如下:

using namespace std;





int main() {


    while(1) {


        int rand_value = (rand7() - 1) * 7 + rand7();


        if(rand_value >= 1 && rand_value <= 10){


            cout << rand_value<< endl;


            break;


        }


    }


    return 0;


}

但是这种方法的效率偏低，因为只有采样到$[1, 10]$之间才结束，而$[11, 49]$之间的数都会被抛弃

进一步优化，$[1, 40]$之间都能够进行均匀随机采样，使用模除可以放缩到$[1, 10]$

using namespace std;





int main() {


    while(1) {


        int rand_value = (rand7() - 1) * 7 + rand7();


        if(rand_value >= 1 && rand_value <= 40){


            cout << rand_value % 10 << endl;


            break;


        }


    }


}

这样就只有$[41, 49]$之间的数被抛弃，效率会教上者更高

进制解法

上面的解法在于数学公式的证明和实用，另外一种解法是从进制的角度来思考

首先来看，如果给定$rand1()$, 只能生成 $[0, 1]$之间的均匀随机数，如何构造$[a, b]$的均匀随机数 ，这种情况就无法直接套上面的公式。

如果从二进制的角度来看，可以很容易生成$[0, b - a]$之间的均匀随机数，因为可以对二进制的每一位采用$rand1()$随机函数。那么就可以很容易生成$[a, b]$之间的均匀随机数

现在将题目改成给定$rand7()$, 希望生成$[1, 10]$的均匀随机数，那么这就是用7进制来随机生成$[0, 10]$之间的数