Вычисления площадей геометрических фигур. Метод Монте-Карло.

Раздел: Моделирование

Различные способы вычисления

площадей геометрических

фигур

Автор: Розова Е.Е., учитель информатики МОУ гимназии№3 им. А.Н.Островского г. Кинешма, Ивановской обл.

Тема:

Цель работы: освоить понятие метода Монте-Карло, как основного метода создания вероятностных моделей;

Задачи:

• Научиться вычислять площади нестандартных фигур используя среду программирования Pascal и электронные таблицы Excel;
• уметь записывать предикат для фигуры, площадь которой необходимо найти
• Сравнить полученные результаты;

Математический способ определения площади фигуры ( домашнее задание )

Метод Монте-Карло

• Вписываем сложную фигуру в другую фигуру, для которой легко вычислить площадь(обычно квадрат или прямоугольник).
• Равномерно разбрасываем N точек со случайными координатами, которые попадают в данный квадрат(прямоугольник).
• Подсчитываем количество точек, попавших на фигуру: M (записать предикат для точек с координатами (x, y), которые лежат внутри фигуры).

• Вычисляем площадь:

Чем больше число испытаний N , тем величина

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

= 3x-4 – нижняя левая граница, линейная функция; y = –x+12 – нижняя правая граница, линейная функция; (x-4) 2 +(y-8) 2 Точка с координатами (x, y) лежит в заштрихованной области, если она принадлежит 1-й или 2-й части и 3-й. Искомый предикат имеет вид: F(x, y) = (( y = 3x-4 )  ( y = –x+12 )) & ( (x-4) 2 +(y-8) 2 )." width="640"

Решение задачи

Фигура ограничена тремя границами:

• y = 3x-4 – нижняя левая граница, линейная функция;
• y = –x+12 – нижняя правая граница, линейная функция;
• (x-4) 2 +(y-8) 2

Точка с координатами (x, y) лежит в заштрихованной области, если она принадлежит 1-й или 2-й части и 3-й.

Искомый предикат имеет вид:

F(x, y) = (( y = 3x-4 )  ( y = –x+12 )) &

( (x-4) 2 +(y-8) 2 ).

начало

Алгоритм

решения задачи (блок-схема)

Ввод N,x1,x2,y1,y2

M=0; i=1

Нет

i

Да

X=RND*(x2-x1)+x1

S=S0*M/N

Y=RND*(y2-y1)+y1

т(x;y) попадает?

Нет

Да

Вывод S

M=M+1

конец

i=i+1

Реализация

метода Монте-Карло в Pascal

Решение задачи в Excel

• В Excel с помощью функции СЛЧИС( ) можно получать равномерно распределенные случайные числа в диапазоне от 0 до 1. Для получения значений x и y в нужном нам диапазоне следует вводить формулы:
• для x: =Xmin+(Xmax-Xmin)*СЛЧИС().

( в нашем случае Xmin=1, Xmax=7)

• для y: =Ymin+(Ymax-Ymin)*СЛЧИС().

( в нашем случае Ymin=7, Ymax=11)

Решение задачи в Excel

• Число точек, попавших внутрь фигуры или на её стороны, можно подсчитать, использовать функцию ЕСЛИ. Если координаты x и y таковы, что одновременно (( y = 3x-4 ) или( y = –x+12 )) и
• ( (x-4) 2 +(y-8) 2 ) , тогда функция будет возвращать 1, иначе 0. Тогда число m в формуле для вычисления площади фигуры определится как сумма всех значений, возвращаемых функцией ЕСЛИ, а число n равно числу испытаний, которое можно подсчитать с помощью функции СЧЕТ.

=-a3+12)));1;0) =1+6*СЛЧИС() … … =7+4*СЛЧИС() =если(и(((a102-4)^2+(b102-8)^2=3*a102-4);(b102=-a102+12)));1;0)" width="640"

Решение задачи в Excel

• нужными формулами необходимо заполнить сразу большое число строк, например 100. Так будет выглядеть электронная таблица в режиме отображения формул:

A

1

Площадь=

B

2

3

C

=36*С1/C2

x

=1+6*СЛЧИС()

=СУММ(С3:С102)

…

y

=СЧЁТ(С3:С102)

102

=7+4*СЛЧИС()

…

=если(и(((a3-4)^2+(b3-8)^2=3*a3-4);(b3=-a3+12)));1;0)

=1+6*СЛЧИС()

…

…

=7+4*СЛЧИС()

=если(и(((a102-4)^2+(b102-8)^2=3*a102-4);(b102=-a102+12)));1;0)

Реализация метода

Монте-Карло в Excel

Выводы:

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

Практическая работа

Задание : вычислите площади заштрихованных фигур

Источники информации:

• А.Г. Гейн, В.Г.Житомирский, Е.В.Линецкий, М.В.Сапир, «Основы информатики и вычислительной техники» Москва, «Просвещение», 1993г;

3 . Ермаков С.М. «Методы Монте-Карло и смежные вопросы», Москва, Наука, 1971г;

4. Математика. Большой Энциклопедический Словарь гл. редактор Ю.В.Прохоров, Москва, Большая Российская Энциклопедия