Тема: Метод Монте-Карло.

Цель: Oтработка навыков программирования с использо-
ванием функции случайного числа.

Обеспечеие урока: Программы: TURBO.EXE, MKARLO.PAS, TRAPT.PAS.

Содержание нового материала.

Метод Монте-Карло.
1. Математическая модель.

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

Каждому ясно, что во время снегопада количество снежинок, попавших на детскую площадку, пропорционально ее площади. Таким образом, можно сделать допущение: при большом числе точек, наугад выбранных внутри квадрата, доля точек, содержащихся в F, приближенно равна отношению площади F к площади квадрата.
Несложно видеть, что исходными данными являются сторона а квадрата, содержащего фигуру F, и количество точек kw, которые мы будем случайным образом выбирать внутри квадрата. Результатом является площадь S фигуры F. Если через kr обозначить число тех наугад выбранных точек, которые содержаться в фигуре F, то площадь S приближенно равна S=(kr/kw)*а ².
Применим эту модель для приближенного вычисления числа ПИ путем нахождения площади круга радиуса R=1. Формула площади круга известна:

S = ПИ*R
при R=1 площадь S численно равна ПИ. Квадрат для такого круга получается со стороной а=2. Площадь квадрата равна 4. Тогда площадь фигуры F будет равна:
S = (kr/kw)*4,
что можно заменить на
ПИ = (kr/kw)*4.

Выберем за центр окружности и квадрата начало системы координат, тогда выбрать точку - это значит задать ее координаты: для числа X и Y. Точка принадлежит квадрату, если -1<=X<=1 и -1<=Y<=1. Если X*X+Y*Y<=1, то точка попадает в круг F, иначе она лежит вне круга. Это и есть математическое соотношение, позволяющее для каждой точки определять, лежит ли она в F. Математическая модель, выбранная нами для решения задач на
нахождение площадей, отличается от предыдущих тем, что в ней используются случайные числа (такие модели называют вероятностными). В связи с чем при запуске программы для одного и того же количества случайных чисел результаты будут разными. Можно ли доверять результатам вычислений? На этот вопрос отвечает специальный раздел математики - теория вероятностей, в котором имеется строгое математическое доказательство метода Монте-Карло. На самом деле точность результатов зависит не только от того, является модель вероятностной или нет, - это зависит и от точности исходных данных, точности вычислений и в сильной мере
от качества датчика случайных чисел. Именно качество датчика случайных чисел в системе Express Pascal не выдерживает критики. Функция random и random(x) выдают, так называемые, псевдос лучайные числа, которые начиная с определенного значения повторяются и в последовательности чисел обнаруживаются статистические закономерности.
Оценку достоверности полученного результата производим обычным способом т.е. сравнением двух результатов вычислений, один из которых выполнен с заведомо большей точностью, чем другой. Ясно, что при большем числе случайных точек будет повышена точность результата. В системе PASCAL/FAST из-за плохого качества
датчика случайных чисел и медленной работы ЭВМ при работе программы нет смысла увеличивать число случайных точек более 10000, точность вычислений увеличена не будет.

2. Программа на языке Паскаль.

По рассмотренной математической модели программа на языке Паскаль выглядит примерно так:

Program MonteKarlo;
Var x,y:real;
n,kr,kw:integer;
begin
Clrscr; Writeln ('Вычисление ПИ методом МОНТЕ_КАРЛО.');
Writeln;
Write ('Введите количество случайных чисел. n=');
repeat
x:=random;
until keypressed;
Read (n);
GotoXY (20,8); Writeln ('ЖДИТЕ...');
kr:=0; kw:=0;
repeat
x:=(0.5-random)*2; y:=(0.5-random)*2;
kw:=kw+1;
if x*x+y*y<=1 then kr:=kr+1;
until kw>n;

Clrscr;
GotoXY (20,8); Writeln ('n=',n);
GotoXY(20,10); Writeln ('ПИ=',kr/kw*4:2:6);
end.

Рассмотрим назначение отдельных частей программы.

а) Program MonteKarlo;
Var x,y:real;
n,kr,kw:integer;
x,y - координаты случайной точки,
n- количество случайных точек, попавших в квадрат,
kr - количество случайных точек попавших в фигуру (в на-
шем примере в круг),
kw - счетчик точек, по выходе из цикла равен количеству
случайных точек, попавших в квадрат.

б) Clrscr; Writeln ('Вычисление ПИ методом МОНТЕ_КАРЛО.');
Writeln;
Write ('Введите количество случайных чисел. n=');

Печать заголовка и подсказки на ввод количества случайных
точек.

в) repeat
x:=random;
until keypressed;
Read (n);
GotoXY (20,8); Writeln ('ЖДИТЕ...');

Цикл, предназначенный усилить непредсказуемость последо-
вательности случайных чисел. Чтение с клавиатуры количес-
тва случайных точек и вывод в позиции (20,8) указания
ждать конца выполнения программы.

г) kr:=0; kw:=0;
Установление счетчика точек, попавших в квадрат и круг, в
нулевое состояние.

д) repeat
x:=(0.5-random)*2; y:=(0.5-random)*2;
kw:=kw+1;
if x*x+y*y<=1 then kr:=kr+1;
until kw>n;

Основной расчетный цикл в котором команда:
- x:=(0.5-random)*2; y:=(0.5-random)*2 формирует коорди-
наты случайных точек, попавших в квадрат с координатами
-1<=X<=1 и -1<=Y<=1,
- kw:=kw+1 подсчитывает количество сформированных случай-
ных точек.
- if x*x+y*y<=1 then kr:=kr+1 подсчитывает количество
случайных точек попавших внутрь круга.
- until kw>n выход из цикла по достижении количества слу-
чайных точек превосходящих заданное количество n.

е) Clrscr;
GotoXY (20,8); Writeln ('n=',n);
GotoXY(20,10); Writeln ('ПИ=',kr/kw*4:2:6);
Стереть с экрана и вывести на печать в позиции (20,8) ко-
личество случайных точек и результат вычислений в позиции
(20,10), причем для печати целой части числа отвести не
менее 2-х позиций, для печати дробной части числа отвести
6 позиций.

3. Анализ полученных результатов.
а) Время работы программы и результат зависят от количества выбранных точек.

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

3. Практическая работа. Вызвать на редатирование файл MKARLO.PAS, познакомиться с текстом программы, транслировать и запусить на исполнение при разных значениях n.

Домашнее задание. Метод Монте-Карло.