Rand7实现Rand10

发表于 更新于 本文字数： 268 阅读时长 ≈ 1 分钟

470 用 Rand7() 实现 Rand10()

1. 拒绝采样

在解LC-470前先介绍一道拒绝采样的经典问题：利用频率近似概率的方式求出 $\pi$ 的值。在 $1\times1$ 的方块内随机坐标采样，记录落入以原点为圆心，半径为1的 $\frac{1}{4}$ 圆内的次数。

由 $\frac{1}{4}\pi r^2 = \frac{cnt}{N}$ 可得 $\pi = \frac{4\times cnt}{N\times r^2}$ ，由于 $r=1$ ，所以 $\pi = \frac{4\times cnt}{N}$

1
2
3
4
5
6
7
8
9
10
11
int main() {
    srand((unsigned)time(0)); // time(0)表示从1970到现在的秒数
    int N = (int)1e7, cnt = 0;
    for (int i = 0; i < N; i++) {
        double a = (1.0 * rand() / RAND_MAX); // 除以RAND_MAX归一化0~1
        double b = (1.0 * rand() / RAND_MAX);
        if (a * a + b * b < 1.0) cnt++; // 落入1/4圆则加一
    }
    printf("%lf", (4.0 * cnt) / N);
    return 0;
}

2. LC-470 Rand7生成Rand10

力扣高赞题解

(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int rand10() {
        while(true){
            // 等概率生成[1,49]范围的随机数
            int num = (rand7()-1)*7 + rand7();
            // 拒绝采样，并返回[1,10]范围的随机数
            if(num <= 40) return num % 10 + 1;
        }
    }
};