| 每日一题做题记录,参考官方和三叶的题解 |
- 题目要求
- 思路一:模拟(计算分布函数)
- Java
- C++
- STL mt19937
- STL uniform_real_distribution
- 思路二:拒绝采样
- Java
- C++
- Rust
- 总结
- 用 l e n len len和 a n g ang ang两个值来标记每个随机点,其中 l e n len len表示到圆心的距离, a n g ang ang表示与 x x x轴正向的夹角。
- 若直接在
[
0
,
r
]
[0,r]
[0,r]的范围内生成
l
e
n
len
len以及
[
0
,
2
π
)
[0,2pi)
[0,2π)的范围内生成
a
n
g
ang
ang,得到的点是不均匀的。
- 【这里是我对本题的误解】
- 在单位圆内随机生成一个点,因为
l
e
n
与
r
的
比
例
len与r的比例
len与r的比例不等价于
以
l
e
n
为
半
径
的
圆
面
积
与
总
面
积
的
比
例
以len为半径的圆面积与总面积的比例
以len为半径的圆面积与总面积的比例,所以不能直接在
[
0
,
r
]
[0,r]
[0,r]内随机。
- 具体推导过程需要
概
率
密
度
函
数
P
D
F
概率密度函数PDF
概率密度函数PDF和
累
计
分
布
函
数
C
D
F
累计分布函数CDF
累计分布函数CDF,因为
概率论忘差不多了比较难理解就不写了。 - 概括来说,可以在 [ 0 , r 2 ] [0,r^2] [0,r2]范围内随机再开方,从而确保距离与面积比例一致。
- 具体推导过程需要
概
率
密
度
函
数
P
D
F
概率密度函数PDF
概率密度函数PDF和
累
计
分
布
函
数
C
D
F
累计分布函数CDF
累计分布函数CDF,因为
class Solution {
double r, x, y;
Random ran = new Random();
public Solution(double radius, double x_center, double y_center) {
r = radius;
x = x_center;
y = y_center;
}
public double[] randPoint() {
double len = Math.sqrt(ran.nextDouble(r * r)), ang = ran.nextDouble(2 * Math.PI);
double rx = x + len * Math.cos(ang), ry = y + len * Math.sin(ang);
return new double[]{rx, ry};
}
}
- 时间复杂度: O ( 1 ) O(1) O(1)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
double r, x, y;
mt19937 gen{random_device{}()};
uniform_real_distribution dis;
public:
Solution(double radius, double x_center, double y_center) : dis(0, 1), r(radius), x(x_center), y(y_center) {}
vector randPoint() {
double len = sqrt(dis(gen)), ang = dis(gen) * 2 * acos(-1.0);
double rx = x + len * cos(ang) * r, ry = y + len * sin(ang) * r;
return {rx, ry};
}
};
- 时间复杂度: O ( 1 ) O(1) O(1)
- 空间复杂度: O ( 1 ) O(1) O(1)
- 学习参考链接
- 一个伪随机数产生器,返回无符号整数(unsigned int)。
- 学习参考链接
- 连续均匀分布类模板,定义了一个默认返回double型浮点数的连续分布,返回值半开放(不含上界)。
- 类似的还有uniform_int_distribution。
- 就是先在一个简单的范围(如矩形范围)内生成随机数,然后判断拒绝掉不在题设范围内的数;
- 本题就在边长为 2 R 2R 2R的正方形内生成随机数,然后拒绝四个角角上的那一点。
Java由于正方形的面积为 ( 2 R ) 2 = 4 R 2 (2R)^2=4R^2 (2R)2=4R2,圆的面积为 π R 2 pi R^2 πR2,因此在正方形中随机生成的点落在圆内的概率为 P r ( ⋅ ) = π R 2 4 R 2 ≈ 0.785 Pr(cdot)=frac{pi R^2}{4R^2}approx0.785 Pr(⋅)=4R2πR2≈0.785,期望的生成次数为 E ( ⋅ ) = 1 0.785 ≈ 1.274 = O ( 1 ) E(cdot)=frac{1}{0.785}approx1.274=O(1) E(⋅)=0.7851≈1.274=O(1)。
class Solution {
Random ran = new Random();
double r, x, y;
public Solution(double radius, double x_center, double y_center) {
r = radius;
x = x_center;
y = y_center;
}
public double[] randPoint() {
while(true) {
double rx = ran.nextDouble() * (2 * r) - r;
double ry = ran.nextDouble() * (2 * r) - r;
if(rx * rx + ry * ry <= r * r) {
return new double[]{x + rx, y + ry};
}
}
}
}
- 时间复杂度:期望时间复杂度为 O ( 1 ) O(1) O(1)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
double r, x, y;
mt19937 gen{random_device{}()};
uniform_real_distribution dis;
public:
Solution(double radius, double x_center, double y_center) : dis(-radius, radius), r(radius), x(x_center), y(y_center) {}
vector randPoint() {
while (true) {
double rx = dis(gen), ry = dis(gen);
if(rx * rx + ry * ry <= r * r) {
return {x + rx, y + ry};
}
}
}
};
- 时间复杂度:期望时间复杂度为 O ( 1 ) O(1) O(1)
- 空间复杂度: O ( 1 ) O(1) O(1)
struct Solution {
r:f64,
x:f64,
y:f64,
rr:f64,
}
impl Solution {
fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
Solution {r:radius, x:x_center, y:y_center, rr:radius * radius}
}
fn rand_point(&self) -> Vec {
use rand::{thread_rng, Rng};
let mut rng = thread_rng();
let (rx,ry) = loop {
let (rx,ry) = (rng.gen_range(-self.r, self.r), rng.gen_range(-self.r, self.r));
if rx * rx + ry * ry <= self.rr {
break (rx,ry);
}
};
vec![rx + self.x, ry + self.y]
}
}
- 时间复杂度:期望时间复杂度为 O ( 1 ) O(1) O(1)
- 空间复杂度: O ( 1 ) O(1) O(1)
本来以为是个简单模拟题,结果题解一波分析很是高深,仿佛回到了高数课堂。倒是学习了C++的随机浮点数生成,前几天生套rand()通不过的问题得到了解答。
| 欢迎指正与讨论! |



