Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Кубанский государственный университет»

Факультет МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК

Кафедра вычислительной математики и информатики

Курсовая работа Решение задачи с прикладным содержанием с применением программирования на языке высокого уровня

Работу выполнил ___________________ Шеин Евгений Максимович

Группа 26Г₄ факультет математики и компьютерных наук

Направление 010300.62 – математика, компьютерные науки

Научный руководитель В.З. Цалюк

Краснодар 2013

Содержание

Введение

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

Цель работы определила следующие задачи исследования:

1. Провести анализ условия задачи и выработать подход к ее решению.

2. Выбрать наиболее подходящие представления для входных, выходных и промежуточных данных.

3. На основе выбранного подхода разработать алгоритм.

4. Описать алгоритм на языке программирования.

5. Составить тестовые примеры для отладки и демонстрации возможностей программы.

1. Анализ условия задачи и выработка подхода к ее решению

По условию задачи исходными параметрами являются количество точек и их координаты в двумерном пространстве. В первую очередь необходимо организовать перебор троек точек из заданного множества. Порядок точек не важен, но чтобы сократить количество рассчитываемых наборов и не учитывать повторяющиеся наборы, упорядочим точки. Перебор для первой точки возможен только с 1 до n−2 (если n−2 точка является первой точкой набора, тогда n−1 - второй, а n - третьей), для второй точки перебор возможен со следующей координаты после выбранной в качестве первой до n−1, для третьей точки – со следующей координаты после выбранной в качестве после второй до n. Таким образом, мы сможем перебрать все возможные не повторяющиеся наборы из трех точек заданного множества.

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

Окружность строим по следующему принципу:

Проведем через пары точек две прямые. Первая линия пусть проходит через P₁ и P₂, а прямая b - через P₂ и P₃.  Уравнения этих прямых будут:

;

где m - коэффициент наклона линии, получаемый из

;

Центр круга - находится на пересечении двух перпендикулярных прямых, проходящих через середины отрезков P₁P₂ и P₂ P₃. Легко доказать, что прямая, перпендикулярная к линии с коэффициентом наклона m имеет коэффициент наклона -1/m, значит уравнения прямых, перпендикулярных a и b и проходящих через середины P₁P₂ и P₂P₃ будут

Они пересекаются в центре, и решение относительно x дает

Значение у вычислим подстановкой x в уравнение одного из перпендикуляров. Радиус найти элементарно. Например, P₁ лежит на окружности и мы знаем центр. Радиус будет равен длине ОP₁. Знаменатель (mb - ma) равен нулю, когда прямые параллельны. В этом случае они совпадают, то есть круга не существует.

В конце организуем вывод параметром окружности и минимальную разность количеств точек.