Rand7 实现 Rand10

Posted on Edited on Symbols count in article: 811 Reading time ≈ 1 mins.

470 用 Rand7 () 实现 Rand10 ()

1. 拒绝采样

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

由 可得 ，由于 ，所以 

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;
        }
    }
};