0028 원 내 랜 덤 생 성 점
8575 단어 매일 하나의 알고리즘 문제
번호: 0028
시험 문제 출처: leetcode 나의 블 로그: Something
제목 설명
원 의 반지름 과 원심 의
x
과 y
좌 표를 정 하고 원 에서 균일 한 랜 덤 점 을 만 드 는 함수 randPoint
를 쓴다.설명:
randPoint
무 작위 점 을 포함 하 는 x
좌표 와 y
좌표 의 크기 가 2 인 배열 풀이 알고리즘
사고의 방향 을 풀다.
이 문 제 는 두 가지 풀이 방향 이 있 는데 첫 번 째 는 샘플링 을 거부 하 는 것 이다. 바로 무 작위 로 생 성 되 기 쉬 운 도형 을 선택 하 는 것 이다. 예 를 들 어 정사각형 을 선택 하여 변 의 길 이 를 반지름 으로 만 들 면 정사각형 에서 무 작위 로 점 을 만 든 다음 에 이 점 이 원 안에 있 는 지 판단 하면 된다.
정사각형 중 무 작위 생 성 점
double x = r * (double)rand() / RAND_MAX; // rand() RAND_MAX, 0~1
double y = r * (double)rand() / RNAD_MAX;
이 점 이 원 안에 있 는 지 아 닌 지 를 판단 하 다.
while(x * x + y * y > r * r)//
또 다른 방법 은 극좌 표 의 사고방식 으로 원 안에서 무 작위 로 점 을 찍 는 것 이다.
여기 서 우 리 는 먼저 각도
theta
를 취하 고 반경 tmpR
을 취 하 는 방법 을 선택한다.우선 각도
theta
, 각도 360, 선 택 된 것 등 가능 한 것 을 먼저 취하 기 때문에 간단하게 랜 덤 수 를 취하 면 됩 니 다.double theta = 360 * (double)rand() / RAND_MAX;
그리고 반경
tmpR
을 선택 하면 여기에 구덩이 가 하나 있다.나 는 처음에 모든 반지름 도 가능 하 다 고 생각 했 지만 사실은 그렇지 않 았 다.수학의 공식 으로 알 수 있 듯 이 면적 은 8747 ° 2 * 8727 ° p i * 8727 ° x \ int 2 * pi * x * 8747 ° 2 * 8727 ° pi * 8727 ° x 이 고 확률 밀도 공식 을 구 할 수 있 으 면 f (x) = 2 * 8727 ° x f (x) = 2 * x f (x) = 2 * 8727 ° x x 이 며 여 기 는 pi \ pi pi 를 무시 합 니 다. 아무런 영향 이 없 기 때 문 입 니 다.그 다음 에 알 수 있 듯 이 임의의 한 변 의 길이 에 대해 점 이 이 변 의 길 이 를 반지름 으로 하 는 원 안에 떨 어 질 확률 은 F (x) = x 2 F (x) = x ^ 2 F (x) = x2 이 고 이런 확률 은 균일 하 게 분포 되 어야 하기 때문에 모든 확률 이 하나의 반지름 에 대응 할 수 있 기 때문에 우 리 는
double tmpR = r * sqrt((double)rand() / RAND_MAX); // sqrt x2
그리고 이 두 개의 양 으로 정확 한 결 과 를 구 할 수 있 습 니 다.
코드 구현
class Solution {
private:
double r;
double x;
double y;
public:
Solution(double radius, double x_center, double y_center) {
srand((unsigned) time(NULL));
r = radius;
x = x_center;
y = y_center;
}
vector<double> randPoint() {
double theta = 2 * M_PI * (double)rand() / RAND_MAX;
double tmpR = r * sqrt((double)rand() / RAND_MAX);
vector<double> result;
result.push_back(x + tmpR * cos(theta));
result.push_back(y + tmpR * sin(theta));
return result;
}
};