1 Постановка задачи и описание исходных данных

Разработать программу для расчета площади фигуры, ограниченной осью ОХ, функцией у=ах2+в и прямыми х=к, х=m, методом Монте-Карло (имитационное моделирование). Построить график функции с осями координат, графики прямых и закрасить вычисляемую площадь. Значения а, в, к, m задаются пользователем. Определить О-сложность алгоритма.

2 Математическое обеспечение

Суть метода

Нахождение площади фигуры, ограниченной параболой вида y(x)=ax²+b и прямыми y=k и y=m производится следующим образом: строится прямоугольная область (далее - контейнер), содержащий целиком область фигуры, площадь которой необходимо найти, генерируется заданное пользователем количество случайных точек, координаты которых принадлежат области построенного контейнера; подсчитывается количество точек, принадлежащих области искомой фигуры. Далее, по формуле S_и=S_к *k/r (где S_к - площадь контейнера, k - количество точек, принадлежащих искомой области, r - общее число точек) определяется площадь искомой области (S_и).

Реализация. Анализ исходных данных

Очевидно, что график y(x)=ax²+b при всех возможных значениях будет представлять собой параболу, смещенную от начала координат по оси Y на значение b. Растяжение по оси X будет определяться коэффициентом a при аргументе x² . Функции y=k и y=m представляют собой прямые, параллельные Y.

Определение координат для построения контейнера

Для определения границ контейнера по оси Y необходимо вычислить значение координаты вершины параболы (b), пересечения параболы и прямых k и m (P₁=ak²+b и P₂=am²+b). Границы контейнера будут определятся максимальным абсолютным значением найденных точек, т.е.: G_Y1=max(|b|,|P₁|, |P₂|) и G_Y2=0.

Для определения границ контейнера по оси X необходимо вычислить точки пересечения ветвей параболы с осью X (если есть). Для этого решим квадратное уравнение ax²+b=0. Обозначим найденные действительные значения корней через X₁ и X₂. Границы контейнера будут определяться минимальным и максимальным найденными значениями, с учетом прямых k и m, т.е.: G_X1=min(X₁,X₂, k,m) и G_X2=max(X₁,X₂, k,m). Итак, полученный контейнер имеет координаты (G_X1, G_Y1, G_X2, G_Y2).

Проверка принадлежности точки области искомой фигуры

Пусть определена точка С(С_X,C_Y), причем координаты точки принадлежат области контейнера. Точка будет принадлежать области, площадь которой нужно найти, если |C_Y|<F(|С_X|). Иными словами, если: |C_Y|<a С²_X+b.

Проверка правильности результата и подсчет относительной (приведенной) погрешности измерений

Площадь криволинейной трапеции можно определить интегральным методом. Первообразная функции f(x)= ax²+b имеет вид F(x)= (ax²)/3+bx. По формуле Ньютона-Лейбница имеем: S= (a G_X2²)/3+b G_X2 - (a G_X1²)/3-b G_X1.

За абсолютную величину примем площадь, найденную интегральным методом. Тогда: ∂=100((|S- S_и |)/S), где S_и - площадь, вычисленная методом Монте-Карло.

3 О-сложность алгоритма Приведем фрагмент кода, который реализует метод Монте-Карло:

for (int c2=0;c2<precision;c2++)

{

xr=(rand()%int(diax*10000)*0.0001)+interval_x_min; - Операторы А

yr=(rand()%int(diay*10000)*0.0001)+interval_y_min; - Операторы B

if (fabs(yr)<fabs(a*xr*xr+b)) cnt_points++; - Операторы C

}

Группы операторов А, B и С имеют константную О-сложность, т.е. О(С)), так как значения всегда вычисляются по заданной формуле. Итоговая О-сложность приведенного выше кода линейная О(n), т.е. сложность итогового алгоритма зависит только от количества итераций цикла.