Здравствуйте! Помогите решить задачу на геометрию. На форуме говорится что нужно использовать рандомные числа? Причем здесь рандомность? Можно по подробнее?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Здравствуйте! Помогите решить задачу на геометрию. На форуме говорится что нужно использовать рандомные числа? Причем здесь рандомность? Можно по подробнее?
Название |
---|
Гуглить "метод монте карло площадь"
Спасибо, помогло.
Допустимая погрешность в процент очень высока, потому решение простое, просто берем 10^6 случайных точек в квадрате и проверяем каждую на то вошла ли она хоть в 1 круг, и выводим количество вошедших / общее. Разумеется можно (и нужно для получения детерминированного решения), брать не случайные точки а (0;0), (0;0,001), (0;0,002), ... ,(0;1), (0,001;0), (0,001;0,001), (0,001;0,002), ... ,(0,001;1), .... Доказать что при таком выборе погрешность не превышает 1% при том что у нас не более 10 кругов не составляет труда, но решение со случайными проще пишется и тоже спокойно заходит
Скажите, а где можно узнать про вычисление погрешности в задачах?
Хм. В первом случае где мы берем рандомизированно это можно сделать с помощью теории вероятностей. У нас есть величина p равная ответу, и мы проводим 10^6 измерений. Каждый раз мы с вероятностью p получаем 1 и с вероятностью 1-p 0. Тогда за 10^6 измерений матожидание очевидно равно 10^6 * p, а дисперсия = 10^6 * p * (1-p), отсюда среднеквадратичное отклонение порядка 10^3. А нас просят ответить с точностью до 0.01, что при 10^6 измерениях означает отклонение в 10^4 от матожидания, что в 10 раз больше среднеквадратичного. Разумеется все очень грубо но примерно так. А насчет второго способа нужно порисовать на листике)
Понял. Большое спасибо!