Уфимский государственный авиационный технический университет
Кафедра _________ «Вычислительная техника и зашита информации»_____________
Разработка прикладного алгоритма
Подп. и дата
Подп. и дата
Взаим. инв. №
Инв.№ подл.
Инв.№ дубл.
на языке программирования С++___
________________________________________
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту по____МП и ПА_____
130.7.017.000.000
(обозначение документа)
Группа ЗИ -239
Фамилия И.О.
Подпись
Дата
Оценка
Студент
Арестов М.М.
Консультант
Селиванова М.В
Принял
Селиванова М.В
Уфа – 2011
Уфимский государственный авиационный технический университет
Кафедра ___ВТиЗИ___________________факультет____ИРТ______________________
Задание
на курсовое проектирование по дисциплине ___Методы программирования и прикладные алгоритмы________________________________________________________________________
на тему Разработка прикладного алгоритма и его реализация на языке С++___________
выдано 8 октября 2011г. студенту второго курса____________________________________
________________________________________________________________ЗИ-239 группы
Использование среды программирования Visual C++ для разработки программ на языке программирования C++___________________________________________________________
1. Страуструп Б. Язык программирования С++. Специальное издание. Пер. с англ. –М.: Издательство Бином, 2011. – 1136 с. : ил.
Селиванова М.В. Методические указания к курсовой работе по дисциплине «Методы программирования и прикладные алгоритмы»/ Уфимск. гос. авиац. тех. ун-т. Сост. Селиванова М.В. – Уфа, 2008. – 31 с.
3. Седжвик, Р. Алгоритмы на C++.: Пер. с англ. – М.: ООО "И.Д. Вильямс", 2011 - 1056 с.
4. Страуструп Б. Программирование: принципы и практика использования C++, испр. изд.: Пер. с англ. –М.:ООО "И.Д. Вильямс", 2011. – 1248с.
Кнут Д. Искусство программирования. Т.3 Сортировка и поиск. М.: Вильямс, 2000. – 832 с.
Зав. кафедрой _В.И.Васильев__ Руководитель проекта _М.В. Селиванова
Содержание
1 Постановка задачи и описание исходных данных……………...……………5
2 Математическое обеспечение………………………………………………….6
3 О-сложность алгоритма…………………………………………….…………...7
4 Разработка алгоритма программы в виде блок-схемы……………..………….8
5 Описание работы программы………………………………………………….14
Вывод……………………………………………………………………………16
Список используемой литературы………………………………….…………17
Приложение А………………………………………………………..…………19
Приложение В………………………………………………………..…………30
Постановка задачи и описание исходных данных
Разработать программу для расчета площади фигуры, ограниченной осью ОХ, функцией у=ах2+в и прямыми х=к, х=m, методом Монте-Карло (имитационное моделирование). Построить график функции с осями координат, графики прямых и закрасить вычисляемую площадь. Значения а, в, к, m задаются пользователем. Определить О-сложность алгоритма.
Математическое обеспечение
Суть метода
Нахождение площади фигуры, ограниченной параболой вида y(x)=ax2+b и прямыми y=k и y=m производится следующим образом: строится прямоугольная область (далее - контейнер), содержащий целиком область фигуры, площадь которой необходимо найти, генерируется заданное пользователем количество случайных точек, координаты которых принадлежат области построенного контейнера; подсчитывается количество точек, принадлежащих области искомой фигуры. Далее, по формуле Sи=Sк *k/r (где Sк - площадь контейнера, k - количество точек, принадлежащих искомой области, r - общее число точек) определяется площадь искомой области (Sи).
Реализация. Анализ исходных данных
Очевидно, что график y(x)=ax2+b при всех возможных значениях будет представлять собой параболу, смещенную от начала координат по оси Y на значение b. Растяжение по оси X будет определяться коэффициентом a при аргументе x2 . Функции y=k и y=m представляют собой прямые, параллельные Y.
Определение координат для построения контейнера
Для определения границ контейнера по оси Y необходимо вычислить значение координаты вершины параболы (b), пересечения параболы и прямых k и m (P1=ak2+b и P2=am2+b). Границы контейнера будут определятся максимальным абсолютным значением найденных точек, т.е.: GY1=max(|b|,|P1|, |P2|)и GY2=0.
Для определения границ контейнера по оси X необходимо вычислить точки пересечения ветвей параболы с осью X (если есть). Для этого решим квадратное уравнение ax2+b=0. Обозначим найденные действительные значения корней через X1 и X2. Границы контейнера будут определяться минимальным и максимальным найденными значениями, с учетом прямых k и m, т.е.: GX1=min(X1,X2, k,m)и GX2=max(X1,X2, k,m). Итак, полученный контейнер имеет координаты (GX1, GY1, GX2, GY2).