随机：拒绝采样

0470. 用 Rand7() 实现 Rand10() (opens new window)

题目

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

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

解析

定理

已知 $\rm{rand}_N()$ 可以等概率的生成 $[1, N]$ 范围的随机数，那么：

$(\rm{rand}_X() - 1) \times Y + \rm{rand}_Y()$

可以等概率的生成 $[1, X \times Y]$ 范围的随机数，即实现了 $\rm{rand}_{XY}()$。

本题基于上述定理，因此我们可以通过 $(\rm{rand}_{7}() - 1) \times 7 + \rm{rand}_{7}()$ 生成 $\rm{rand}_{49}()$。

但是这样实现的 N 不是 10 的倍数，这里就涉及到了“拒绝采样”的知识了，如果某个采样结果不在要求的范围内，则丢弃它。

代码

// 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 ans = 40;
        while (ans >= 40) {
            ans = 7 * (rand7() - 1) + rand7() - 1;
        }
        return ans % 10 + 1;
    }
};

0478. 在圆内随机生成点 (opens new window)

题目

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

说明:

• 输入值和输出值都将是浮点数。
• 圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
• 圆周上的点也认为是在圆中。
• randPoint 返回一个包含随机点的x坐标和y坐标的大小为2的数组。

解析

拒绝采样，在以给定圆作为内切圆的正方形中随机采样，直到随机点在圆内返回。

代码

class Solution {
    double x_center, y_center, radius;
public:
    Solution(double radius, double x_center, double y_center) {
        this->radius = radius;
        this->x_center = x_center;
        this->y_center = y_center;
    }
    
    vector<double> randPoint() {
        while (true) {
            double x = x_center - radius + 2 * radius * ((double)rand() / RAND_MAX);
            double y = y_center - radius + 2 * radius * ((double)rand() / RAND_MAX);
            if (pow(x - x_center, 2) + pow(y - y_center, 2) <= pow(radius, 2)) {
                return vector<double>{x, y};
            }
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */