Математическое обоснование.

 

 

Для математического обоснования данной задачи мне потребуется изучение темы «Вектора» и соответственно основные формулы: «Длина вектора» или «Расстояние между 2 точками».

 

Задача(условно): Дано N точек синего цвета и N точек красного цвета, координаты их известны. Нужно соединить их так, чтобы расстояние от точки одного цвета до точки другого цвета было минимальным из возможных вариантов. Далее рассчитать сумму их длин.

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

 

Решение:

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

Для расчета длины используем формулу длины вектора:

 

A¯B = √(x₂ – x₁)² + (y₂ – y₁)² (1)

 

II. После того, как выбраны нужные (минимальные) варианты длин отрезков, нужно просто суммировать эти длины, в результате, задача решена, получен нужный ответ.

 

 

3. Практическая часть.

3.1. Структура программы.

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

 

 

Рассмотрим некоторые блоки, встречающиеся в программе.

Интерфейс - этот блок осуществляет взаимодействие пользователя и программы. Взаимодействие осуществляется с помощью монитора, клавиатуры и мыши.

Ввод синих и красных точек – в этом блоке запоминаются данные о синих и красных точек и размещаются на поле пользователем.

Построение отрезков – блок, который производит построение отрезков из красных и синих точек.

Отображение хода работы алгоритма – в таблице отражаются отрезки и их суммарная длина.

Визуализация результатов - отображение изменений происходящих в программе.

Справка – производная интерфейса, служит для получения сведений по эксплуатации программы.

 

 

3.2. Описание используемых типов данных.

 

В ходе реализации программы использовались как стандартные структуры данных, так и собственные, созданные непосредственно при проектировании алгоритма.

Для хранения данных о красных и синих точках используется спиcок pList типа TList. Число точек хранится в переменной tCount, число красных точек – в redCount, число синих точек – в blueCount.

Также был создан тип данных TPnt для хранения структуры данных о точке имеющий следующий вид:

 

PPnt = ^TPnt;

TPnt = record

X,Y: integer;

rColor: byte;

num: integer;

Linked: boolean;

end;

 

Как видно он основан на указателях (PPnt ссылается на адресное пространство типа TPnt), и использование этого типа подразумевает хранение следующей информации о точке:

· Координаты X и Y

· Цвет точки (1 – красный, 2 - синий)

· Связана ли точка (Linked = true/false)

· Номер точки, с которой связана данная точка, если она связана (num)

3.3. Описание основных алгоритмов.

 

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

Подробное описание автоматического и ручного алгоритмов было приведено ранее, в пункте 2.4.