Метод монте карло треугольник (2 видео) | Курс школьной геометрии

Метод Монте-Карло вычисления площадей фигур и его реализация в среде Delphi

В начале урока рассказываю идею метода. Ребята, сегодня мы рассмотрим интересный метод приближенного вычисления площадей фигур – метод Монте – Карло. Пусть у нас есть какая – нибудь фигура на плоскости, площадь которой ( S_fig ) нам необходимо найти. Ограничим ее другой фигурой, площадь которой ( S_total ) мы можем легко вычислить. Например, прямоугольником АСDB со сторонами, параллельными координатным осям (см. рис. 1). И пусть про любую точку прямоугольника мы можем быстро узнать, попадает эта точка внутрь фигуры, площадь которой мы ищем, или нет.

А теперь начнем опыт – будем бросать на бумагу зерна случайным образом (вообще – то это нелегко сделать, чтобы обеспечить случайность). Когда нам покажется, что зерна почти полностью покрыли бумагу, посчитаем, сколько всего зерен на прямоугольнике (пусть их число N_total ) и сколько из них на фигуре ( N_fig ). Ясно, что число зерен, попавших внутрь фигуры, пропорционально ее площади: больше площадь – больше зерен, меньше площадь – меньше зерен. Поэтому, поделив количество зерен , попавших внутрь фигуры , на количество всех зерен в прямоугольнике, мы сможем найти, какую часть площади прямоугольника занимает фигура:

Промоделируем этот опыт на ЭВМ. Предположим, нам надо найти площадь фигуры ограниченной сверху кривой Y = F(X), а снизу – осью абсцисс. Пусть Y = cos(X), а Х I [– p /2, p /2] (см. рис. 2). Ограничим нашу фигуру прямоугольником АСDB, его площадь равна p .

Из чего должен состоять алгоритм:

1. Бросание зерна – бросание случайной точки, координаты X и Y которой случайны, причем Х должна меняться от – p /2 до p /2, а Y – от 0 до 1. И в этих интервалах X и Y должны появляться с одинаковой вероятностью в любой точке этих отрезков, т.е. X и Y должны быть равномерно распределены по осям. Тут надо напомнить ребятам, как получить равномерно распределенное случайное вещественное число на интервале [А, В]:

Х = random* ( B – A) + A

2. Надо определить, куда попала точка – под кривую или выше нее. И вести подсчет N_fig. Условие попадания точки под кривую: Y ? sin (X).

3. Повторить пп.1 и 2 столько раз, чтобы получить желаемую точность результатов.

Дети без труда напишут программу по данному алгоритму (на практическом занятии). И после этого наступает момент разочарования. Сухие цифры.

Предложение учителя: давайте создадим проект в Delphi, который наглядно демонстрировал бы работу метода Монте – Карло. Разработаем интерфейс программы. Тут ребята сами предлагают несколько вариантов оформления проекта, один из которых представлен на рис. 3.

Разместим на форме следующие компоненты:

Edit – окно редактирования для ввода общего количества испытаний (бросков зерен) – N_total;

Button – кнопка для запуска работы метода Монте – Карло;

Panel – панель для вывода посчитанной площади фигуры;

(все вышеперечисленные компоненты расположены на вкладке Standart Палитры компонентов)

Image – для вывода точек, попавших в искомую область (компонент расположен на вкладке Additional Палитры компонентов).

Если необходимо, надо напомнить ребятам некоторые свойства и методы выбранных компонентов (это может быть и домашним заданием предыдущего урока, чтобы не терять время на “воспоминания”) .

Свойство Text – содержит текст, который пользователь набирает в окне Edit. Этот текст надо преобразовать в число N_total. Для этого в Delphi есть необходимая функция StrToInt:

N_total = StrToInt (Edit1.Text).

Свойство Caption – содержит текст, который выводится на панель. Чтобы вывести полученное число S_fig на панель, мы должны преобразовать его в строку S с помощью процедуры Str:

а потом вывести эту строку на панель следующим образом:

Panel1.Caption := ‘Площадь фигуры = ‘ + S

Свойства Height и Width – соответственно высота и ширина компонента;

Свойство Canvas – отводит канву (место) для рисования на компоненте Image;

FillRect(ClientRect) – закрашивает область клиента компонента Image каким – либо цветом

(по – умолчанию – белым), т.е. стирает предыдущую картинку;

MoveTo(X, Y) – перемещает перо в точку с координатами X, Y без проведения линии (координаты задаются в пикселях);

LineTo(X, Y) – проводит линию из текущей точки в точку с координатами X, Y;

Pixels[I, J] – содержит цвет точки с координатами I, J.

У кнопки (компонент Button) мы будем обрабатывать событие onClick (событие нажатие кнопки). Т.е. вышеописанный алгоритм мы программируем в процедуре Button1Click.

Тут учитель задает вопрос классу: “ Какая проблема возникает при выводе точки на экран (на компонент Image)?” Ответ: расчетные координаты очень малы (0 ? Y ? 1,меньше пикселя, -p /2 ? X ? p /2); а если взять другую кривую Y = F(X), они могут оказаться слишком большими (больше размера компонента Image). Поэтому, при выводе значений функций (графиков) на экран монитора, необходимо преобразовывать расчетные координаты в графические с учетом дискретности растровой сетки монитора, а также предусмотреть возможность автоматического масштабирования функции (графика) по осям координат. Для этого желательно создать отдельную подпрограмму.

Для полного размещения функции (графика) в расчетной области (это область компонента Image) необходимо определить X_min, X_max, Y_min, Y_max – минимальные и максимальные значения по X и по Y соответственно. X_min =А, X_max = В. Как найти Y_min, Y_max.

Коллективно обсуждается следующий алгоритм:

1. Разобьем интервал [А, В] по Х на N равных частей и определим массивы значений аргумента и функции X[i] и Y[i] = F(X[i]), где I = 1..N;
2. Определяем наибольшее Y_max и наименьшее Y_min значения функции в заданном интервале изменения аргумента;
3. Находим коэффициенты масштабирования Kx, Ky при построении графика в заданной области;
4. Т.к. коэффициенты масштабирования Kx, Ky могут отличаться, то выводимый график может искажаться. Устраняем искажения графика;
5. Преобразуем расчетные координаты точки X, Y в графические Xg, Yg. С учетом того, необходимости “переворота” оси Y, которая в координатах монитора направлена сверху вниз.

Листинг программы, реализующей данные алгоритмы представлен в конце статьи. Результат работы программы при разном количестве испытаний представлен на рис. 3, 4.

Задания для самостоятельной работы:

1. Применить метод Монте – Карло для приближенного вычисления площади фигуры, ограниченной сверху кривой Y = sin (X), при Х I [ 0, p ];
2. Применить метод Монте – Карло для приближенного вычисления числа p . Подсказка: рассмотреть круг единичного радиуса с центром в т. (1, 1). Его площадь и будет равна p .
3. Применить метод Монте – Карло для приближенного вычисления площади фигуры, ограниченной сверху кривой Y = sin (X), при Х I [ 0, 2p ];
4. Применить метод Монте – Карло для приближенного вычисления площадей фигур, представленных на рис. 5 – 7.

5. Доработать проект:

а) организавать проверку правильности ввода информации в поле Edit (чтобы вводились только целые числа);
б) разметить оси и подписать числовые значения.

На последующих уроках, на которых предполагается изучение тем “Вычисление площадей (интегралов) методом трапеций и методом прямоугольников”, можно предложить ребятам доработать проект, поместив на форму дополнительные компоненты Image, Button, Edit, Panel (для каждого численного метода – свои). В окно компонента Edit пользователь будет вводить количество разбиений интервала [А, В] по Х. Таким образом, ребята смогут сравнить и наглядно увидеть работу всех трех численных методов.

unit Monte;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls, Buttons;
type
TForm1 = class(TForm)
Panel1: TPanel;
BitBtn1: TBitBtn;
Edit1: TEdit;
Label1: TLabel;
Image1: TImage;

const A = -Pi/2.0; B = pi/2.0; n = 1000;

var
Form1: TForm1;
N_total:longint;
implementation

Function FUNC(x:real):real;
begin
Func:=Cos(x);
end;

Procedure Graphic( var right, down: integer;
var X_min, X_max, Y_min, Y_max, Kx, Ky: real);
type arr=array[1..n] of real;
var
X, Y: arr; dx: real;
i: integer;
begin
dx:=(B-A)/(n-1);
for i:=1 to n do begin X[i]:=A+dx*(i-1);
Y[i]:=FUNC(X[i]);
end;

X_max:=B; X_min:=A;
Y_max:=Y[1]; Y_min:=Y[1];
for i:=2 to n do begin
if Y_max Y[i] then Y_min:=Y[i];
end;

Содержание

Метод Монте-Карло – имитационное моделирование, алгоритм
Что такое метод Монте-Карло
Использование метода Монте Карло для вычисления площади фигуры
Алгоритм вычисления площади фигуры с помощью метода Монте Карло
Статистическое моделирование (метод Монте-Карло)
Введение
Общая схема метода
📹 Видео

Видео:Метод Монте-КарлоСкачать

Метод Монте-Карло – имитационное моделирование, алгоритм

Одним из инструментов в области имитационного моделирования является способ решения задач с использованием эксперимента со случайными числами, который носит название метода Монте-Карло. Область применения этого метода и его алгоритм описаны в данной статье.

Видео:Метод Монте-КарлоСкачать

Что такое метод Монте-Карло

Метод Монте-Карло относится к группе численных методов решения задач, в условиях которых присутствует элемент неопределенности. Он позволяет получить приближенные результаты на множестве входных значений, которые подбираются произвольно путем генерации случайных чисел.

Название этого метода выбрано в честь города Монте-Карло, известного своими казино. Рулетка в казино – это своего рода генератор случайных чисел. Этот метод впервые был описан в 1949 году в совместной работе математиков Николаса Метрополиса и Станислава Улама. Известно, что название придумал Н. Метрополис в честь одного из своих родственников, который был азартным игроком и частым посетителем казино.

Видео:Что такое метод Монте-Карло (простым языком)Скачать

Использование метода Монте Карло для вычисления площади фигуры

Простым примером иллюстрации применения данного метода является способ определения площади фигуры сложной формы, когда контуры объекта не образуют геометрической формы, для которой существует готовая формула для расчета.

Рис. 2. Фигура сложной формы.

Чтобы вычислить площадь S такой фигуры, ее вписывают в квадрат стороной a. Затем, случайным образом выбирают точки внутри квадрата. Причем точки могут попадать как внутрь исследуемой фигуры сложной формы, так и вне ее.

Чем большую площадь занимает фигура внутри квадрата, тем чаще в нее будут попадать точки. Точки, попавшие внутрь фигуры, обозначают буквой m, а все выбранные точки внутри квадрата – буквой n.

Здесь проявляется закономерность: чем больше точек в эксперименте задействовано, тем с большей вероятностью можно утверждать, что процент точек, содержащихся в исследуемой фигуре стремится к отношению площади фигуры к площади квадрата. Математически это можно записать следующим образом: s=a*a*(m/n).

Таким образом, получен некоторый способ определения площади фигуры произвольной формы с использованием метода статистических испытаний. Модели для вычисления площади различных фигур сложной формы, сформированные этим способом, будут отличаться математическими описаниями фигур.

В теории вероятностей и математической статистике действует закон больших чисел, согласно которому результат эксперимента окажется свободным от случайных воздействий только в случае большого количества случайных факторов, то есть будет прослеживаться устойчивая закономерность. Проще говоря, чем больше число испытаний, тем точнее будет результат.

Видео:Рубцов Алексей - Квантовый метод Монте-КарлоСкачать

Алгоритм вычисления площади фигуры с помощью метода Монте Карло

Определим площадь фигуры, ограниченной уравнениями y = x^2, y = 0 и x = 1.

Составим модель: площадь искомой фигуры впишется в квадрат. Если значения координат x и y принадлежит диапазону [0;1], то точка принадлежит квадрату. Если выполняется система неравенств 0 Что мы узнали?

Одним из способов построения моделей является метод статистических испытаний, носящий название Метода Монте Карло. Важным условием применения статистических методов является проведения большого количества испытаний путем генерации случайных входных параметров. С помощью метода Монте Карло можно вычислить площадь фигуры произвольной формы.

Видео:Как метод "Монте-Карло" может помочь в разработке стратегий?Скачать

Статистическое моделирование (метод Монте-Карло)

Видео:Метод Монте-КарлоСкачать

Введение

Предложена методическая разработка темы с целью продемонстрировать насколько описываемый метод является мощным и универсальным инструментом для решения различных задач во многих областях знаний. Тема моделирования обычно изучается в школе на примере адекватного представления процессов (например, движения) по выбранным приближенным уравнениям. Статистическое моделирование, наоборот, не предполагает изначально знание математических связей и позволяет получить их на основе многократного наблюдения (компьютерной генерации) возможных событий в представленной модели.

Изучение данного материала возможно, например, на занятиях по подготовке к олимпиадам по программированию /1/. С этой целью выбрано часть задач, предложенных на олимпиадах по Ленинградской области.

Подборка задач позволяет совместное изучение темы школьниками различных классов, имеет игровой и занимательный характер, рассматривает применение и характеристики метода с различных сторон. В ходе разбора задач указаны некоторые приемы программирования, проводится начальное знакомство с важными понятиями теории вероятности, неразрывно связанной с данным методом. Для освоения темы приводятся задачи для самостоятельного решения с указаниями к получению правильных ответов.

Видео:Управление рисками Метод Монте КарлоСкачать

Общая схема метода

Метод статистического моделирования или метод Монте-Карло назван так в честь столицы княжества Монако, известной своими многочисленными казино, в которых публика растрачивает или увеличивает свои доходы согласно законам распределения случайных величин.

Этот метод позволяет решать задачи, в условиях которых присутствует элемент неопределенности (например, при подбрасывании монеты может выпасть “орел” или “решка”). Пусть требуется найти некоторую величину (например, долю выпадения “орлов”). На ЭВМ с помощью генератора (датчика) случайных чисел (ДСЧ) имитируются ситуации или процессы, возможные по условию задачи, и которые приводят к тем или иным исходам, при этом искомая величина принимает некоторое значение (в нашем примере это 0 – если выпал “орел” и 1 – в противном случае). Все или почти все различные исходы (с учетом, когда монета может упасть на ребро) проявятся, если многократно рассмотреть случайное развитие одного и того же начального состояния (смоделировать некоторое количество историй — N).

Закон больших чисел «разыгрываемых» историй утверждает, что среднее арифметическое полученных в каждом розыгрыше значений исследуемой величины имеет предельное искомое значение (в нашей задаче оно равно 1/2).

Это вероятностная сходимость, т.е. чем больше историй, тем достоверней можно утверждать, что наш результат близок к истинному. Для задач с элементами неопределенности — а в реальном мире все задачи такие — это даже естественно. Погрешность определения предельного значения пропорциональна 1/√N. Таким образом, для увеличения точности результата на один порядок, требуется разыграть в 100 раз больше историй. «Разумно» число историй первоначально задавать порядка 10000.

Следовательно, требуется получать много случайных чисел так, чтобы переход от одного числа к другому определялся простыми правилами, но чтобы сами числа “производили впечатление случайности” (их называют поэтому псевдослучайными числами). Например, для выбора последовательности случайных цифр можно взять дробную часть числа пи (π = 3.14159265358979323846264338327950288 4197169399375105820974944592307816406286208998628034825342117… Представляет интерес обратное утверждение: возможно ли, что для любой конечной, наперед заданной последовательности цифр есть ее вложение в бесконечном представлении числа π ). Данный способ, однако, мало приемлем для программирования. Как правило, при решении задач методом Монте-Карло используются процедуры, которые с помощью рекуррентных формул генерируют случайные числа, равномерно распределенные на промежутке [0, 1]. В Pascal для этого используется стандартная функция RANDOM. Для отладки программы бывает важно уметь воспроизвести псевдослучайные числа, а для генерации другой последовательности случайных чисел используется процедура RANDOMIZE .

Очень полезным для понимания данного метода является моделирование игровых вероятностных ситуаций (бросание монеты или кубика, блуждания). Именно «игровая» или связанная с чем-то знакомым (известным, «бытовым») формулировка задачи помогает лучше усвоить метод, осмыслить понятие вероятности.

Пример 1. (Районная олимпиада 1994).

Три игрока (с номерами 1, 2 и 3), имеющие изначально X , Y и Z жетонов соответственно, играют в следующую игру. В каждом раунде каждый игрок ставит на кон один жетон. Затем бросают кубик, на котором цифры 4, 5, 6 заменены на 1, 2 и 3. При выпадении числа i игрок с номером i забирает с кона все три жетона. Игра заканчивается, когда кто-нибудь из игроков проигрывает все жетоны. Введем функцию f(X, Y, Z), как среднюю длительность игры (среднее количество раундов) при заданных начальных капиталах X, Y, Z. Например, f(2, 2, 2) = 2. Ваша задача состоит в том, чтобы определить эту функцию. Для этого необходимо смоделировать игру на компьютере, накопить экспериментальные результаты, проанализировать их, а затем выдвигать гипотезы о виде функции f, проверять их для разных входных значений, и, отбросив неподходящие, найти решение.

Моделирование игры не вызывает трудности (программа приведена ниже). Также очевидно, что вид функции симметричен относительно порядка задания входных параметров f ( X , Y , Z ) = f ( Y , X , Z ) и т.д. Сложность задачи заключается в нахождении вида функции
f ( X , Y , Z ) = X · Y · Z / (X + Y + Z — 2), так как результаты моделирования определяются не точно.