Решение задачи прикладного содержания с применением программирования на языке высокого уровня
Введение
радиус окружность
алгоритм программирование
Цель работы - решение поставленной задачи:
определить радиус и центр такой окружности, проходящей хотя бы через три
различные точки заданного множества точек на плоскости, что минимальна разность
количеств точек, лежащих внутри и вне окружности.
Цель работы определила следующие задачи
исследования:
1. Провести анализ условия задачи и
выработать подход к ее решению.
2. Выбрать наиболее подходящие
представления для входных, выходных и промежуточных данных.
. На основе выбранного подхода
разработать алгоритм.
. Описать алгоритм на языке
программирования.
. Составить тестовые примеры для отладки
и демонстрации возможностей программы.
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 в
уравнение одного из перпендикуляров. Радиус найти элементарно. Например, P1
лежит на окружности и мы знаем центр. Радиус будет равен длине ОP1.
Знаменатель (mb - ma) равен
нулю, когда прямые параллельны. В этом случае они совпадают, то есть круга не
существует.
В конце организуем вывод параметром
окружности и минимальную разность количеств точек.
2. Пошаговая разработка алгоритма
Программа создаёт и использует следующие типы
данных:
Point=Array[1..2] of
REAL;=ARRAY[1..100] of Point;=RECORD:Point;:real;;
Алгоритм решения разделим на три основные части:
ввод данных, решение задачи и вывод результата. Так же, в программе используем
вспомогательные процедуры и функции.
Процедура Circles
вычисляет
параметры окружности проходящей через три точки. Входные параметры: t1:
Point - координаты точки
t1; t2:
Point - координаты точки
t2; t3:
Point - координаты точки
t3; Исходящие
параметры: ok: Circle
- параметры окружности.
PROCEDURE Circles(t1,t2,t3:Point;
VAR ok: Circle);a,b,x,y,k0,k1,k2,m0,m1,m2:REAL;
BEGIN:=SQR(t1[1])-SQR(t2[1])+SQR(t1[2])-SQR(t2[2]);:=2*(t1[2]-t2[2]);:=2*(t1[1]-t2[1]);:=SQR(t1[1])-SQR(t3[1])+SQR(t1[2])-SQR(t3[2]);:=2*(t1[2]-t3[2]);:=2*(t1[1]-t3[1]);:=k2*m0-k0*m2;
b:=k2*m1-k1*m2;b=0 THEN
EXIT;:=a/b;.o[2]:=y;abs(m2) > e THEN x:=(m0-y*m1)/m2IF abs(k2) > e THEN
x:=(k0-y*k1)/k2EXIT;.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;(SQR(a[1]-ok.o[1])+SQR(a[2]-ok.o[2]))>SQR(ok.r)+eAccessory:=1(SQR(a[1]-ok.o[1])+SQR(a[2]-ok.o[2]))<SQR(ok.r)-eAccessory:=-1Accessory:=0;;
В программе будем использовать следующие
глобальные параметры: 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 DOj:=i+1 TO n-1
DOk:=j+1 TO n DO;
Во время перебора точек, мы строим окружность и
подсчитываем разность количества точек внутри и вне нее. (С. 2)
И так до конца перебора точек. В итоге мы найдем
окружность с наименьшей разностью количества точек внутри и вне неё.
Дальнейшей задачей является организация вывода
полученных данных на экран, в текстовый файл и в виде графического изображения.
Этот блок, для удобства, разбит на две части: 1. Вывод на экран и в текстовый
файл; 2. Вывод графического изображения. Текстовый файл берем с именем answer.
В первом блоке выводимая информация зависит от
значения параметра ca.r,
отвечающего за радиус искомой окружности. При значении параметра равном нулю(
что означает что окружность не найдена), на экран и в файл выводится сообщение
о том, что по точкам множества невозможно построить окружность. (С. 4а, С. 4б)
При ненулевом значении параметра, на экран и в
файл выводится информация о параметрах окружности и значение наименьшей
разности. (С. 5)
По завершении вывода ответа, закрываем текстовый
файл.
Во втором блоке мы используем дополнительные
параметры для инициализации графического модуля и для перевода обычных
координат в экранные: 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б)
Пример 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б)
Тесты функций
) Входные параметры: a(3,0),
o(0,0), r
= 2; Значение функции: Accessory
= 1;
) Входные параметры: 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;
) Входные параметры: t1(1,1),
t2(2,2), t3(3,3);
Исходящие параметры: o(0,0),
r = 0.
Заключение
В процессе проведения исследования был проведен
анализ условия поставленной задачи, выработан подход к ее решению, разработан
алгоритм решения задачи и описан на языке программирования. Так же были
составлены тестовые примеры для отладки и демонстрации возможностей программы.
Таким образом, была полностью решены задачи поставленные задачи исследования и
достигнута его цель - разработана программа, позволяющая определить радиус и
центр такой окружности, проходящей хотя бы через три различные точки заданного
множества точек а плоскости, что минимальна разность количеств точек, лежащих
внутри и вне окружности.
Разработанная программа считывает координаты
точек множества из файла, задаваемого пользователем, ответ выводится на экран и
сохраняется в файле answer.
В случае если по точкам заданного множества нельзя построить окружность, то
программа выдаст сообщение о том, что по точкам множества невозможно построить
окружность. Для корректной работы программы в файле, задающем множество точек
их координаты должны быть записаны подряд через пробел.
Приложение
Содержание прилагаемого диска.
Каталог Procedure
and function
Tests - содержит
тестовые примеры процедур и функций встроенных в модуль программы.
Каталог Test
Cases - содержит
каталоги TEST1, TEST2,
TEST3 в которых
содержатся примеры работы готовой программы.
Файлы Kurs_Mod(
с расширениями .o, .pas,
.ppu) - файлы модуля,
содержащего типы данных, значение переменной ε
и функции, используемые в программе.
Файлы Kurs_Work(
с расширениями .exe,
.o, .pas)
- файлы программы курсовой работы.
Файл coordinates.pas
- файл с основным примером работы программы.
Файл answer.pas
- файл с ответом к основному примеру работы программы.
Файл Курсовая работа.doc
- документ, содержащий курсовую работу в текстовом виде.
Список использованных источников
.Абрамян
М. Э., Михалкович С. С. Основы программирования на языке Паскаль: Скалярные
типы данных, управляющие операторы, процедуры и функции. - Ростов-на-Дону. -
ООО «ЦВВР». - 2004.
.Абрамян
М. Э. Практикум по программированию на языке Паскаль: Массивы, строки, файлы,
рекурсия, указатели. - Ростов-на-Дону. - ООО «ЦВВР». - 2004.
.Выгодский
М. Я. Справочник по высшей математике. - АСТ. Астрель. - 2006.