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

Размещено на http://www.allbest.ru/

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

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

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

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

Факультет Математики и компьютерных наук

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

КУРСОВАЯ РАБОТА

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

Работу выполнил

Шеин Евгений Максимович

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

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

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

Краснодар 2013

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Проведем через пары точек две прямые. Первая линия пусть проходит через P1 и P2, а прямая b - через P2 и P3.

Уравнения этих прямых будут:

;

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

;

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

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



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

2. Пошаговая разработка алгоритма

Программа создаёт и использует следующие типы данных:

Point=Array[1..2] of REAL;

Points=ARRAY[1..100] of Point;

Circle=RECORD

o:Point;

r:real;

END;

Алгоритм решения разделим на три основные части: ввод данных, решение задачи и вывод результата. Так же, в программе используем вспомогательные процедуры и функции.

Процедура Circles вычисляет параметры окружности проходящей через три точки. Входные параметры:

t1: Point - координаты точки t1;

t2: Point - координаты точки t2;

t3: Point - координаты точки t3;

Исходящие параметры:

ok: Circle - параметры окружности.

PROCEDURE Circles(t1,t2,t3:Point; VAR ok: Circle);

VAR a,b,x,y,k0,k1,k2,m0,m1,m2:REAL;

BEGIN

k0:=SQR(t1[1])-SQR(t2[1])+SQR(t1[2])-SQR(t2[2]);

k1:=2*(t1[2]-t2[2]);

k2:=2*(t1[1]-t2[1]);

m0:=SQR(t1[1])-SQR(t3[1])+SQR(t1[2])-SQR(t3[2]);

m1:=2*(t1[2]-t3[2]);

m2:=2*(t1[1]-t3[1]);

a:=k2*m0-k0*m2;

b:=k2*m1-k1*m2;

IF b=0 THEN EXIT;

y:=a/b;

ok.o[2]:=y;

IF abs(m2) > e THEN x:=(m0-y*m1)/m2

ELSE IF abs(k2) > e THEN x:=(k0-y*k1)/k2

ELSE EXIT;

ok.o[1]:=x;

ok.r:=sqrt(sqr(t1[1]-x)+sqr(t1[2]-y));

END;

Функция Accessory определяет принадлежность точки окружности.

Входные параметры:

a: Point - координаты точки a;

ok: Circle - координаты точки b;

Значение функции:

Accessory:INTEGER - принадлежность точки окружности( 1 - вне окружности, ?1 - внутри окружности, 0 - лежит на окружности).

FUNCTION Accessory(a:Point;ok:Circle):INTEGER;

BEGIN

IF (SQR(a[1]-ok.o[1])+SQR(a[2]-ok.o[2]))>SQR(ok.r)+e

THEN Accessory:=1

ELSE

IF (SQR(a[1]-ok.o[1])+SQR(a[2]-ok.o[2]))<SQR(ok.r)-e

THEN Accessory:=-1

ELSE Accessory:=0;

END;

В программе будем использовать следующие глобальные параметры: n, для хранения количества точек, i, j, k, l, для перебора всех возможных вариантов троек точек, k1, k2, difference, для подсчета количества точек внутри и вне окружности и разности между этими количествами, типа INTEGER; f, для связи физического файла, в котором хранятся координаты точке, с логическим файлом, f_answer, для связи с файлом, в который будет записан ответ, типа TEXT; xc, для чтения координат точек из файла, типа REAL; t, для хранения координат точек во время решения задачи, типа MassP; c, для хранения параметров текущей окружности, ca, для хранения параметров искомой окружности, типа Circle.

Заранее не известно, сколько будет задано точек, поэтому считаем все координаты из файла и запишем их количество в переменную n. Так как задача рассматривается на плоскости и у каждой точки две координаты, мы делим полученное значение на два. Затем записываем пары координат точек в массив, на экран и в файл. (С. 1)

Перебор троек точек осуществляется с помощью трех последовательных вложенных циклов FOR:

FOR i:=1 TO n-2 DO

FOR j:=i+1 TO n-1 DO

FOR k:=j+1 TO n DO

BEGIN

…

END;

Во время перебора точек, мы строим окружность и подсчитываем разность количества точек внутри и вне нее. (С. 2)

Далее мы сравниваем это количество с наименьшим количеством. При нахождении окружности с меньшей разностью мы запоминаем эту разность и параметры окружности. И так до конца перебора. (С. 3)

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

Дальнейшей задачей является организация вывода полученных данных на экран, в текстовый файл и в виде графического изображения. Этот блок, для удобства, разбит на две части: 1. Вывод на экран и в текстовый файл; 2. Вывод графического изображения. Текстовый файл берем с именем answer.

В первом блоке выводимая информация зависит от значения параметра ca.r, отвечающего за радиус искомой окружности. При значении параметра равном нулю( что означает что окружность не найдена), на экран и в файл выводится сообщение о том, что по точкам множества невозможно построить окружность. (С. 4а, С. 4б)

При ненулевом значении параметра, на экран и в файл выводится информация о параметрах окружности и значение наименьшей разности.

По завершении вывода ответа, закрываем текстовый файл.

Во втором блоке мы используем дополнительные параметры для инициализации графического модуля и для перевода обычных координат в экранные: D, M, GraphErrorCode, для инициализации модуля Graph и для проверки, не возникло ли ошибок при его инициализации, MX, MY, для хранения размеров экрана, xx, yy, для хранения координат, преобразованных в экранные, типа INTEGER; MaxX, MaxY, MinX, MinY, для хранения области значения точек множества, g, для вычисления масштабирующего параметра, типа REAL.

В первую очередь, найдем область определения множества точек, путем перебора всего множества точек и нахождения минимального и максимального значения по обеим координатам. (С. 6)

Далее, перенесем эту область в область экрана. Параметр g поможет промасштабировать эту область так, чтобы она не вылезала за рамки экрана, при этом не искажая графическое изображение. Этот параметр заключает область в рамку, с пустой сотней пикселей справа и снизу. Далее мы преобразуем координаты точек в экранные, со сдвигом на пятьдесят пикселей вправо и вниз, за счет чего получается, что графический ответ заключен в рамке, по пятьдесят пикселей со всех сторон. (С. 7)

Следующий шаг - вывод точек множества. Точки, для лучшей видимости, будем выводить размером пять на пять пикселей. (С. 8)

И, наконец, вывод ответа. Программа чертит окружность по параметрам полученной искомой окружности, с наименьшей разницей количества точек внутри и вне её. (С. 9)

Перед завершением выполнения программы, закрываем графический модуль.

3. ТЕСТОВЫЕ ПРИМЕРЫ

Тесты основной программы

Пример 1. n = 6, координаты точек: (0,0), (0,1), (-1,0), (1,2), (3,0), (2,1) (Рис. 1а). Ответом являются параметры окружности и наименьшая разность. (Рис. 1б)

 Размещено на http://www.allbest.ru/

Пример 2. n = 5, координаты точек: (1,1), (2,2), (3,3), (4,4), (5,5) (Рис. 2а). Ответом является сообщение о том, что по точкам множества невозможно построить окружность. (Рис. 2б)

Пример 3. n = 3, координаты точек: (0,0), (1,0), (0,1) (Рис. 3а). В ответ выводится параметры единственной возможной окружности. (Рис. 3б)

Тесты функций

Функция Accessory(a:Point;ok:Circle):INTEGER;

Функция Accessory определяет принадлежность точки окружности.

Входные параметры:

a: Point - координаты точки a;

ok: Circle - координаты точки b;

Значение функции:

Accessory:INTEGER - принадлежность точки окружности( 1 - вне окружности, ?1 - внутри окружности, 0 - лежит на окружности).

Тесты:

1) Входные параметры:

a(1,1),

o(0,0), r = 2;

Значение функции:

Accessory = -1;

2) Входные параметры:

a(3,0),

o(0,0), r = 2;

Значение функции:

Accessory = 1;

3) Входные параметры:

a(2,0),

o(0,0), r = 2;

Значение функции:

Accessory = 0;

Процедура Circles(t1,t2,t3:Point; VAR ok: Circle);

Процедура Circles вычисляет параметры окружности проходящей через три точки. Входные параметры:

t1: Point - координаты точки t1;

t2: Point - координаты точки t2;

t3: Point - координаты точки t3;

Исходящие параметры:

ok: Circle - параметры окружности.

Тесты:

1) Входные параметры:

t1(1,0),

t2(0,1),

t3(-1,0);

Исходящие параметры:

o(0,0), r = 1;

2) Входные параметры:

t1(1,1),

t2(2,2),

t3(3,3);

Исходящие параметры:

o(0,0), r = 0.

Заключение

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

Разработанная программа считывает координаты точек множества из файла, задаваемого пользователем, ответ выводится на экран и сохраняется в файле answer. В случае если по точкам заданного множества нельзя построить окружность, то программа выдаст сообщение о том, что по точкам множества невозможно построить окружность. Для корректной работы программы в файле, задающем множество точек их координаты должны быть записаны подряд через пробел.

Список использованных источников

1. Абрамян М. Э., Михалкович С. С. Основы программирования на языке Паскаль: Скалярные типы данных, управляющие операторы, процедуры и функции. - Ростов-на-Дону. - ООО «ЦВВР». - 2004.

2. Абрамян М. Э. Практикум по программированию на языке Паскаль: Массивы, строки, файлы, рекурсия, указатели. - Ростов-на-Дону. - ООО «ЦВВР». - 2004.

3. Выгодский М. Я. Справочник по высшей математике. - АСТ. Астрель. - 2006.

4. Ильин В. А., Позняк Э. Г. Аналитическая геометрия. - М.: ФИЗМАТЛИТ. 2002.

Размещено на Allbest.ur

...