Пошаговая разработка алгоритма
Во втором блоке мы используем дополнительные параметры для инициализации графического модуля и для перевода обычных координат в экранные: D, M, GraphErrorCode, для инициализации модуля Graph и для проверки, не возникло ли ошибок при его инициализации, MX, MY, для хранения размеров экрана, xx, yy, для хранения координат, преобразованных в экранные, типа INTEGER; MaxX, MaxY, MinX, MinY, для… Читать ещё >
Пошаговая разработка алгоритма (реферат, курсовая, диплом, контрольная)
Программа создаёт и использует следующие типы данных:
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])).
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).
Перед завершением выполнения программы, закрываем графический модуль.