1. Цель работы
Целью работы является изучение метода статистических испытаний (ме- тода Монте-Карло) на примере вычисления площади фигуры и получение навы- ков в использовании встроенных функций генерации случайных чисел на Пас- кале.
2. Метод Монте-Карло
Метод Монте-Карло - численный метод, основанный на воспроизведении большого числа реализаций случайного процесса, специально построенного по условиям задачи. В настоящее время этот метод применяется при исследовании функционирования сложных систем, к которым относятся разнообразные произ- водственные и информационные системы, автоматизированные системы управ- ления, многопроцессорные вычислительные системы, некоторые биологические, экономические системы.
При решении подобных задач ранее, без применения ЭВМ, источником случайных чисел служили различные эксперименты: бросание монеты или ку- бика, верчение рулетки и т.п. С именем города в княжестве Монако, известного своими игорными домами, связано происхождение названия метода.
3. Алгоритм вычисления площади фигуры методом Монте-Карло Рассмотрим задачу определения площади фигуры, например, представлен-
ной на рис.1. Фигура может быть любой, но обязательно должны быть известны:
а) границы фигуры в виде аналитического выраже- ния или совокупности таких выражений и логических условий;
б) площадь в виде пря- моугольника, часть которой занимает исследуемая фигура.
В нашем примере гра-
ница фигуры определяется уравнениями:
у=sin(x); y=1;
x=0; x=3.14...
Неизвестная пока нам площадь этой фигуры составляет часть прямоуголь- ника площадью S = 1 x 3.14 = 3.14 = PI.
Алгоритм решения задачи.
1) Генерируем случайное число х1 в диапазоне от 0 до РI, а также случайное число у1 в диапазоне от 0 до 1. Получаем случайную точку внутри прямоуголь- ника с координатами (х1, у1). Эта точка может попасть в исследуемую фигуру,а может и не попасть.
2) Проверка принадлежности точки (х1, у1) к исследуемой фигуре. Если попадания нет, т.е. у1 > sin (х1), то переходим к п.1 и снова генерируем случай- ную точку с координатами (х2, у2).
Если попадание есть, т.е. у1 < sin (х1), то необходимо зафиксировать, за- помнить это попадание и снова перейти к п.1. В итоге мы должны считать число попаданий.
Примечание: попадание точки точно на границу фигуры у1 = sin (х1) можно отнести как к одному, так и к другому исходу - это воля экспериментатора и ав- тора программы.
3) Пункт 1 следует повторить достаточно большое число раз, от этого, в конечном итоге, зависит точность вычислений. Для данной задачи число повто- ров N= 1000 - 3000.
4) После проведения N повторов имеем несложную пропорцию: общее число опытов соответствует всей площади прямоугольника, равной PI, а число попаданий Р будет соответствовать неизвестной площади S исследуемой фи- гуры. Отсюда:
S = (P * PI) / N.
Укрупненная блок-схема алгоритма приведена на рис. 2.
3. Генерация случайных чисел на Паскале
1) Генерация случайных вещественных чисел (тип REAL) в диапазоне от 0 до 1 осуществляется с помощью функции RANDPOM:
х:= RANDOM; (1)
Если необходимо генерировать случайные числа в другом диапазоне, то необходимо преобразовать выражение (1) с помощью операций смещения и мас- штабирования. Например, для того, чтобы получить случайное число в диапа- зоне от 10 до 12, необходимо использовать выражение:
х:= 10 + 2 * RANDOM; (2)
2) Для генерации целых (тип INTEGER) случайных чисел в диапазоне от 0 до N используется функция с аргументом:
х:= RANDOM(N);
3) Для смены базы генерации случайных чисел (чтобы при каждом новом прогоне программы числа были другие) используется процедура RANDOMIZE. Обращение к этой процедуре идет до обращения к функциям RANDOM, напри- мер:
VAR.......; begin RANDOMIZE;....
for i:= 1 to 1000 do begin x:= RANDOM; y:= RANDOM;...
End;....... end.
Программа на ПАСКАЛЕ для вычисления числа Рi;
Надо подобрать такое значение N, при котором Pi= 3.1415