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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«Санкт-Петербургский государственный политехнический университет»

Институт менеджмента и информационных технологий

Санкт-Петербургского государственного политехнического университета в г.Череповце

КУРСОВОЙ ПРОЕКТ

Дисциплина: Высокоуровневые методы информатики и программирования

Тема: Задача о красных и синих точках

Специальность: 080801 Прикладная информатика (в экономике)

Выполнил студент гр. О.581 Марунова Ю.Д.,

Никитин А.Ю.

2009 год

Содержание

• 1.Введение
• 2. Теоретическая часть
• 2.1 Техническое задание
• 2.2 Характеристика программы
• 3. Практическая часть
• 3.1 Структура программы
• 3.2 Описание используемых типов данных
• 3.3 Описание основных алгоритмов
• 4.Резюме
• 4.1 Выводы
• 4.2 Возможные модернизации
• 5. Литература
• 6. Приложение
• 6.1 Текст программы

1. Введение

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

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

2. Теоретическая часть

2.1 Техническое задание

1.Введение.

Программа предназначена для определения возможности построения n отрезков с разноцветными концами, суммарная длина которых будет минимальна (из точки может выходить только один отрезок).

2. Основание для разработки.

Выполнение курсовой работы по дисциплине «Высокоуровневые методы информатики и программирования ».

3. Назначение разработки.

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

4. Требования к программе.

4.1. Требования к функциональным характеристикам.

В состав программы входят функции

- построить n отрезков.

Входные данные - указание размеров a и n.

Выходные данные - графическая информация, выводимая на экран.

4.2. Требования к надежности.

Надежное функционирование программы обеспечивается за счёт ограниченного множества функций программы.

4.3. Требования к составу и параметрам технических средств ЭВМ, внешние устройства, их характеристики.

Для функционирования программы требуется компьютер со следующими минимальными требованиями:

CPU -8086

RAM-640 KB

VGA- монитор

Прочие внешние устройства для работы программы не требуются.

4.4. Требования к информационной и программной совместимости ОС, система программирования, используемые программные средства, методы решения, информационные структуры и т.п.

Для функционирования программы требуется ОС MS-DOS версии 3.30 или выше, от 64 килобайт свободной оперативной памяти. Программа разработана в интегрированной среде Borland Delphi версии 7.0.

5. Требования к программной документации.

Пояснительная записка, техническое задание, руководство пользователя.

6. Технико-экономические показатели. Ориентировочная экономическая эффективность, преимущества по сравнению с аналогами.

7. Стадии и этапы работ (примерный план)

Стадии и этапы работ	Содержание работ	Сроки	Исполнители
ТЗ	Постановка задачи, определение требований, структуры данных, метода решения и т.д.	20.04.2009	Марунова Ю.Д.
Технический проект	Разработка алгоритма, определение формы представления данных, структуры программы. Проектирование интерфейса Пояснительная записка.	20.05.2009	Марунова Ю.Д.
Рабочий проект	Программирование и реализация В том числе - Реализация интерфейса - Реализация основных графических функций - Реализация остальных функций - Испытание и тестирование программы. - Разработка документации.	27.05.2009	Марунова Ю.Д.
Защита проекта	Завершение пояснительной записки Получение допуска к защите	Не позднее, чем за 2 дня до даты защиты	Марунова Ю.Д.

2.2 Характеристика программы

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

2.3 Общий вид программы

Программа, рассчитывающая минимальную суммарную длину отрезков с концами разного цвета, выглядит следующим образом:

· Большое поле (В нем пользователь определяет местоположение точек. После введения равного количества точек 2 цветов здесь эти точки соединяются таким образом, что отрезок получается с концами разных цветов. А сумма этих отрезков минимальна )

· Определение количества точек, введенных пользователем с описанием их цвета.

· 3 режима, выбираемых пользователем:

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

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

3. Ручной режим. Данный режим позволяет пользователю самому как ввести точки так и провести между ними отрезок с разными концами соответственно.

· Кнопка «Очистить» (Полностью очищает оба поля от точек и их координат, а так же сбрасывает счетчики количества точек.)

· Кнопка «Рассчитать» (Даная кнопка действует только после ввода равного количества точек 2 цветов. После ее нажатия программа “расчерчивает” такие отрезки с концами разных цветов, сумма которых минимальна. Ниже Малого поля компьютер показывает размер этой суммы.)

· Кнопка «Шаг». При каждом ее нажатии программа показывает и рассчитывает разные варианты соединения точек.

2.4 Алгоритм работы с программой

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

1. Выбираем один из режимов ввода точек: Режим ввода красных

точек / Режим ввода синих точек.

2. Расставляем в произвольном порядке на Большом поле точки

определенного цвета.

3. Меняем режим на ввод точек следующего цвета и так же расставляем

их на поле в совершенно произвольном порядке.

4. Выбираем ручной или автоматический режим работы.

5. Количество точек разных цветов должно быть одинаковым. В ином случае кнопка «Рассчитать» не активируется.

6. При выполнении условия из пункта №5, активируется кнопка «Рассчитать». Теперь, при ее нажатии, на Большом поле появляются вышеописанные отрезки, а ниже высвечивается их min сумма.

7. Теперь, после получения окончательного результата, пользователь может очистить Большое и Малое поля с помощью кнопки «Очистить».

8. После того, как пользователь расставил все точки, при каждом нажатии кнопки «Шаг» программа показывает и рассчитывает новые варианты соединения точек.

9. Еще один, ручной режим, пользователь реализует соответственно сам. То есть, после того, как пользователь расставил все точки, при нажатии кнопки «Курсор» он может сам соединять точки в том порядке, в котором захочет, при этом в Малом поле автоматически отображается сумма получившихся отрезков. После “отжатия” этой же кнопки нужно нажать кнопку «Шаг» и тогда программа покажет правильный вариант, т.е. вариант с минимальной суммой отрезков.

2.5 Некоторые особенности данной программы

a. Кнопка «Расчитать» загорается только при равном количестве точек обоих цветов. Это объясняется математически.

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

b. Кнопкой «Очистить» можно воспользоваться в любой момент процесса выполнения алгоритма, что наиболее удобно для пользователя в случае какой-либо ошибки. Но очищается полностью все поле в любом из режимов.

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

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

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

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

Решение:

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

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

AЇB = v(x2 - x1)2 + (y2 - y1)2 (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.

Поиск минимальной суммы длин отрезков

Данная задача является классическим примером динамического программирования. Полный перебор, как легко доказать, требует экспоненциального времени, что для алгоритма не есть хорошо, применение же динамического программирования упрощает эту задачу и как далее будет видно сложность этого алгоритма есть O(x^3).

Изобразим работу алгоритма графически:



Рис. 1

Код процедуры, реализующей данный алгоритм:

procedure FindLines;

Var

i,j,start: integer;

P,P2,PMin,Pz: PPnt;

Min,Sum: double;

begin

for start:= 0 to pList.Count-1 do

begin

Sum:=0;

tmpList.Clear;

for i:= 0 to pList.Count-1 do

begin

Pz := pList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

tmpList.Add(P);

end;

for i:= start to tmpList.Count-2 do

begin

P := tmpList.Items[i];

if not P^.Linked then

begin

Min := MaxInt;

for j := 0 to tmpList.Count - 1 do

if i<>j then

begin

P2 := tmpList.Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then

begin

if sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y)) < Min then

begin

Min := sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

for i := 0 to start-1 do

begin

P := tmpList.Items[i];

if not P^.Linked then

begin

Min := MaxInt;

for j := 0 to tmpList.Count - 1 do

if i<>j then

begin

P2 := tmpList.Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then

begin

if sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y)) < Min then

begin

Min := sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

if start=0 then

begin

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList.Count-1 do

begin

Pz := tmpList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

oList.Add(P);

end;

end

else if sum<minsum then

begin

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList.Count-1 do

begin

Pz := tmpList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

oList.Add(P);

end;

end;

end;

pList.Clear;

for i:= 0 to oList.Count-1 do

begin

Pz := oList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

pList.Add(P);

end;

Form1.Label3.Caption := 'Минимальная сумма отрезков: ' + FloatToStr(minSum);

end;

Данный алгоритм содержит несколько циклов: один глобальный цикл и два вложенных, которые в свою очередь включают в себя ещё по одному вложенному циклу. Параметром для внешнего глобального цикла является переменная start, которая делит данный список как бы на два сегмента. Потом внутренние циклы последовательно перебирают переменные в первом и втором сегментах. Данные переменные берутся в предположении, что они являются началом отрезка, а концы отрезков перебираются ещё одним циклом по всему списку. В итоге складывается картина того, что начала отрезков берутся в разных сегментах, размеры которых меняются в процессе прогона глобального цикла, а концы - из всего списка. Данный способ перебора элементов позволяет перебрать все отрезки, выбрать из них минимальные и найти их минимальные суммы. Суммирование в предварительную минимальную сумму для каждого набора отрезков происходит, если расстояние от данной точки (начала отрезка) до перебираемой точки (конца отрезка) меньше, чем расстояния от данной точки до всех остальных. В итоге мы получаем суммы длин наборов отрезков, из которых запоминаем в свою очередь минимальную сумму.

Ниже приведена общая блок-схема алгоритма:



4. Резюме

4.1 Выводы

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

К достоинствам программы можно отнести:

- простой интерфейс без излишних сложностей;

- процесс работы программы визуализируется;

К недостаткам можно отнести следующее:

- невозможность более детального анализа алгоритма;

4.2 Возможные модернизации

программа задача алгоритм

1. Доработать программу и дать возможность пользователю более детального анализа алгоритма.

5. Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритмы: построение и анализ».

2. В.В. Фаронов «Delphi - программирование на языке высокого уровня».

3. Ю.С. Избачков, В.Н. Петров «Информационные системы», второе издание

6. Приложение

6.1 Текст программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ComCtrls, Menus, ToolWin, ExtCtrls, StdCtrls, ImgList, Grids,

ValEdit, ShellAPI;

type

TForm1 = class(TForm)

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

Panel1: TPanel;

ToolBar1: TToolBar;

ToolButton1: TToolButton;

ToolButton2: TToolButton;

Image1: TImage;

Button1: TButton;

Button2: TButton;

ImageList1: TImageList;

ToolButton3: TToolButton;

N3: TMenuItem;

N4: TMenuItem;

ScrollBox1: TScrollBox;

Image2: TImage;

GroupBox1: TGroupBox;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Button3: TButton;

StringGrid1: TStringGrid;

Panel2: TPanel;

procedure ToolButton1Click(Sender: TObject);

procedure ToolButton3Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Image1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure ToolButton2Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

PPnt = ^TPnt;

TPnt = record

X,Y: integer;

rColor: byte;

num: integer;

Linked: boolean;

end;

var

Form1: TForm1;

rColor: byte;

pList, tmpList, oList, rList: TList;

tCount, redCount, blueCount: integer;

cWidth, cHeight: integer;

minSum: double;

start_sh: integer;

i_1, j_1, i_2, j_2: integer;

i,j, start: integer;

P,P2,PMin,Pz: PPnt;

Min,Sum: double;

x,y: integer;

fl:Boolean;

i_col,ip1,ip2:integer;

implementation

{$R *.dfm}

procedure ClearGrid;

Var rRect: TRect;

begin

rRect.Left := cWidth + 1;

rRect.Right := Form1.Image2.Width;

rRect.Top := 0;

rRect.Bottom := Form1.Image2.Height;

Form1.Image2.Canvas.Brush.Color := clWhite;

Form1.Image2.Canvas.FillRect(rREct);

end;

procedure FindLines;

Var

i,j,start: integer;

P,P2,PMin,Pz: PPnt;

Min,Sum: double;

begin

for start:= 0 to pList.Count-1 do

begin

Sum:=0;

tmpList.Clear;

for i:= 0 to pList.Count-1 do

begin

Pz := pList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

tmpList.Add(P);

end;

for i:= start to tmpList.Count-2 do

begin

P := tmpList.Items[i];

if not P^.Linked then

begin

Min := MaxInt;

for j := 0 to tmpList.Count - 1 do

if i<>j then

begin

P2 := tmpList.Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then

begin

if sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y)) < Min then

begin

Min := sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

for i := 0 to start-1 do

begin

P := tmpList.Items[i];

if not P^.Linked then

begin

Min := MaxInt;

for j := 0 to tmpList.Count - 1 do

if i<>j then

begin

P2 := tmpList.Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then

begin

if sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y)) < Min then

begin

Min := sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

if start=0 then

begin

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList.Count-1 do

begin

Pz := tmpList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

oList.Add(P);

end;

end

else if sum<minsum then

begin

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList.Count-1 do

begin

Pz := tmpList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

oList.Add(P);

end;

end;

end;

pList.Clear;

for i:= 0 to oList.Count-1 do

begin

Pz := oList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

pList.Add(P);

end;

Form1.Label3.Caption := 'Минимальная сумма отрезков: ' + FloatToStr(minSum);

end;

procedure DrawGrid(vList: TList);

Var i,j: integer;

rREct: TRect;

p: PPnt;

begin

for j:=1 to vList.Count do

begin

Form1.Image2.Canvas.Pen.Color := clBlack;

rRect.Left := cWidth * j;

rRect.Top := 0;

rRect.Right := cWidth * (j+1);

rRect.Bottom := cHeight;

Form1.Image2.Canvas.FillRect(rRect);

Form1.Image2.Canvas.Brush.Color := clInactiveCaption;

Form1.Image2.Canvas.FillRect(rRect);

Form1.Image2.Canvas.Font.Style := [fsBold];

Form1.Image2.Canvas.TextOut(j * cWidth + round(cWidth/2)-3, 1, IntToStr(j));

for i:=0 to 5 do

begin

Form1.Image2.Canvas.MoveTo(cWidth*j, i*cHeight);

Form1.Image2.Canvas.LineTo(cWidth*(j + 1), i*cHeight);

end;

for i:= j to j + 1 do

begin

Form1.Image2.Canvas.MoveTo(i*cWidth,0);

Form1.Image2.Canvas.LineTo(i*cWidth,cHeight*5 + 1);

end;

Form1.Image2.Canvas.Font.Style := [];

Form1.Image2.Canvas.Brush.Color := clWhite;

p := vList.Items[j-1];

Form1.Image2.Canvas.TextOut((j+1)*cWidth - round(cWidth/2) - 8, cHeight + 1, IntToStr(p^.X));

Form1.Image2.Canvas.TextOut((j+1)*cWidth - round(cWidth/2) - 8, 2*cHeight + 1, IntToStr(p^.Y));

Form1.Image2.Canvas.TextOut((j+1)*cWidth - round(cWidth/2) - 2, 3*cHeight + 1, IntToStr(p^.num));

if p^.rColor = 1 then

begin

rRect.Left := cWidth * j + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (j+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clRed;

Form1.Image2.Canvas.FillRect(rRect);

end;

if p^.rColor = 2 then

begin

rRect.Left := cWidth * j + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (j+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clBlue;

Form1.Image2.Canvas.FillRect(rRect);

end;

end;

end;

procedure DeletePoints(vList: TList);

Var p: PPnt;

begin

while vList.Count > 0 do

begin

P := vList.Items[0];

Dispose(P);

vList.Delete(0);

end;

tCount := 0;

RedCount := 0;

BlueCount := 0;

end;

procedure DrawPoints(vList: TList);

Var i,j: integer;

p, p2: PPnt;

begin

for i := 0 to vList.Count-1 do

begin

p:= vList.Items[i];

if p^.rColor = 1 then

Form1.Image1.Canvas.Brush.Color := clRed;

if p^.rColor = 2 then

Form1.Image1.Canvas.Brush.Color := clBlue;

Form1.Image1.Canvas.Pen.Color := clBlack;

Form1.Image1.Canvas.Ellipse(p^.X-4,p^.Y-4,p^.X+4,p^.Y+4);

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.TextOut(p^.X-20, p^.Y-5, IntToStr(i+1));

for j:=i+1 to vList.Count - 1 do

begin

p2 := vList.Items[j];

if p^.num = p2^.num then

begin

Form1.Image1.Canvas.MoveTo(p^.X, p^.Y);

if p^.rColor = 1 then Form1.Image1.Canvas.Pen.Color := clRed;

if p^.rColor = 2 then Form1.Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo(round((P^.X+P2^.X)/2),round((P^.Y+P2^.Y)/2));

if p2^.rColor = 1 then Form1.Image1.Canvas.Pen.Color := clRed;

if p2^.rColor = 2 then Form1.Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo(P2^.X,P2^.Y);

end;

end;

end;

end;

procedure AddDrawPoint(vList: TList; X,Y: integer);

Var p: PPnt;

begin

Inc(tCount);

Form1.Image1.Canvas.Pen.Color := clBlack;

if rColor = 1 then

begin

Inc(RedCount);

Form1.Image1.Canvas.Brush.Color := clRed;

Form1.Image1.Canvas.Ellipse(X-4,Y-4,X+4,Y+4);

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.TextOut(X-20, Y-5, IntToStr(tCount));

New(p);

p^.X := X;

p^.Y := Y;

p^.rColor := 1;

p^.Linked := false;

p^.num := tCount;

pList.Add(p);

end;

if rColor = 2 then

begin

Inc(BlueCount);

Form1.Image1.Canvas.Brush.Color := clBlue;

Form1.Image1.Canvas.Ellipse(X-4,Y-4,X+4,Y+4);

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.TextOut(X-20, Y-5, IntToStr(tCount));

New(p);

p^.X := X;

p^.Y := Y;

p^.rColor := 2;

p^.Linked := false;

p^.num := tCount;

pList.Add(p);

end;

end;

procedure AddGridPoint(vList: TList);

Var rRect: TRect;

i: integer;

p: PPnt;

begin

if rColor = 0 then exit;

cWidth := 50;

cHeight := 15;

rRect.Left := cWidth * vList.Count;

rRect.Top := 0;

rRect.Right := cWidth * (vList.Count+1);

rRect.Bottom := cHeight;

Form1.Image2.Canvas.FillRect(rRect);

Form1.Image2.Canvas.Brush.Color := clInactiveCaption;

Form1.Image2.Canvas.FillRect(rRect);

Form1.Image2.Canvas.Font.Style := [fsBold];

Form1.Image2.Canvas.TextOut(vList.Count * cWidth + round(cWidth/2)-3, 1, IntToStr(vList.Count));

for i:=0 to 5 do

begin

Form1.Image2.Canvas.MoveTo(cWidth*vList.Count, i*cHeight);

Form1.Image2.Canvas.LineTo(cWidth*(vList.Count + 1), i*cHeight);

end;

for i:= pList.Count to pList.Count + 1 do

begin

Form1.Image2.Canvas.MoveTo(i*cWidth,0);

Form1.Image2.Canvas.LineTo(i*cWidth,cHeight*5 + 1);

end;

Form1.Image2.Canvas.Font.Style := [];

Form1.Image2.Canvas.Brush.Color := clWhite;

p := vList.Items[vList.Count-1];

Form1.Image2.Canvas.TextOut((vList.Count+1)*cWidth - round(cWidth/2) - 8, cHeight + 1, IntToStr(p^.X));

Form1.Image2.Canvas.TextOut((vList.Count+1)*cWidth - round(cWidth/2) - 8, 2*cHeight + 1, IntToStr(p^.Y));

//if p^.Linked

//then

Form1.Image2.Canvas.TextOut((vList.Count+1)*cWidth - round(cWidth/2) - 2, 3*cHeight + 1, IntToStr(p^.num));

//else

//Form1.Image2.Canvas.TextOut((vList.Count+1)*cWidth - round(cWidth/2) - 2, 3*cHeight + 1, '-');

if p^.rColor = 1 then

begin

rRect.Left := cWidth * vList.Count + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (vList.Count+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clRed;

Form1.Image2.Canvas.FillRect(rRect);

end;

if p^.rColor = 2 then

begin

rRect.Left := cWidth * vList.Count + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (vList.Count+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clBlue;

Form1.Image2.Canvas.FillRect(rRect);

end;

end;

procedure pointsDraw;

Var i: integer;

p: PPnt;

begin

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.FillRect(Form1.Image1.Canvas.ClipRect);

Form1.Image1.Canvas.Rectangle(Form1.Image1.Canvas.ClipRect);

for i:=0 to pList.Count - 1 do

begin

p := pList.Items[i];

if p^.rColor = 1 then

begin

Form1.Image1.Canvas.Brush.Color := clRed;

Form1.Image1.Canvas.Ellipse(p^.X-4,p^.Y-4,p^.X+4,p^.Y+4);

end;

if p^.rColor = 2 then

begin

Form1.Image1.Canvas.Brush.Color := clBlue;

Form1.Image1.Canvas.Ellipse(p^.X-4,p^.Y-4,p^.X+4,p^.Y+4);

end;

end;

end;

procedure TForm1.ToolButton1Click(Sender: TObject);

begin

Screen.Cursor := crCross;

rColor := 1;

end;

procedure TForm1.ToolButton3Click(Sender: TObject);

var i:Integer;

begin

if (fl=false) then //кнопка нажата первый раз. включено ручное черчение

begin

sum:=0;

i_col:=0;

fl:=true;

Screen.Cursor := crCross;

rColor := 0;

Button2.Enabled:=false;

Button3.Enabled:=false;

start:=1;

StringGrid1.RowCount := 2; //отрисовка таблицы вывода результата

StringGrid1.ColCount := round(pList.Count/2)+2;

StringGrid1.Cells[StringGrid1.ColCount-1,0] := 'Сумма';

end

else //выход из режима черчения

begin //возврат связей в исходное состояние

for i:= 0 to pList.Count-1 do

PPnt(pList.Items[i])^.Linked:=false;

start := 0;

Screen.Cursor := crDefault;

fl:=false;

Button2.Enabled:=true;

Button3.Enabled:=true;

end;

end;

procedure TForm1.FormCreate(Sender: TObject);

Var

rRect: TRect;

i: integer;

begin //пераоночальное присваивание переменных

fl:=false;

start := 0;

i_1 := start_sh;

j_1 := 0;

i_2 := 0;

j_2 := 0;

tCount := 0;

redCount := 0;

blueCount := 0;

cWidth := 50;

cHeight := 15;

rRect.Left := 0;

rRect.Top := 0;

rRect.Right := Image1.Width;

rRect.Bottom := Image1.Height;

Image1.Canvas.FillRect(rRect);

Image1.Canvas.Rectangle(rREct);

rRect.Left := 0;

rRect.Top := 0;

rRect.Right := Image2.Width;

rRect.Bottom := Image2.Height;

Image2.Canvas.FillRect(rRect);

rRect.Right := cWidth;

rRect.Bottom := cHeight*5;

Image2.Canvas.Brush.Color := clInactiveCaption;

Image2.Canvas.FillRect(rRect);

Image2.Canvas.Font.Style := [fsBold];

for i:=0 to 5 do

begin

Image2.Canvas.MoveTo(0, i*cHeight);

Image2.Canvas.LineTo(cWidth, i*cHeight);

end;

for i:= 0 to 1 do

begin

Image2.Canvas.MoveTo(i*cWidth,0);

Image2.Canvas.LineTo(i*cWidth,cHeight*5 + 1);

end;

Image2.Canvas.TextOut(round(cWidth/2)-2, cHeight + 1, 'X');

Image2.Canvas.TextOut(round(cWidth/2)-2, 2*cHeight + 1, 'Y');

Image2.Canvas.TextOut(round(cWidth/2)-14, 3*cHeight + 1, 'Связь');

Image2.Canvas.TextOut(round(cWidth/2)-14, 4*cHeight + 1, 'Цвет');

rColor := 0;

pList := TList.Create;

tmpList := TList.Create;

oList := TList.Create;

rList := TList.Create;

end;

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

Var p: PPnt;

p1, p2: PPnt;

i:Integer;

minn,mint:Real;

begin

if fl then

begin

minn:=-1; //переменная расстояния между точками. -1 означает что еще не вычислялась

if (i_col=1)then //поиск второй точки, максимально близкой к месту нажатия

begin

for i:= 0 to pList.Count-1 do //перебор всех точек

begin

p:= pList.Items[i]; //данные i-й точки

if (p^.Linked=false)and(p^.rColor<>PPnt(pList.Items[ip1])^.rColor) //если точка не связана и противоположного цвета тогда

then

begin

mint:=sqrt(sqr(P^.X - X) + sqr(P^.Y - Y)); //вычисление расстояния

if(minn<0)then //первоночальное присваивание

begin

ip2:=i; //запомнить позиции точки из списка

minn:=mint

end;

if(mint<minn)then //поиск очередного минимума

begin

ip2:=i;

minn:=mint

end;

end;

end;

inc(i_col); //переход к друнгомк режиму обработки

PPnt(pList.Items[ip2])^.Linked:=true;

end;

if (i_col=0)then //поиск первой точки, максимально близкой к месту нажатия

begin

for i:= 0 to pList.Count-1 do //поиск первой точки

begin

p:= pList.Items[i];

if (p^.Linked=false)

then

begin

mint:=sqrt(sqr(P^.X - X) + sqr(P^.Y - Y));

if(minn<0)then //первоночальное присваивание

begin

ip1:=i;

minn:=mint

end;

if(mint<minn)then

begin

ip1:=i;

minn:=mint

end;

end;

end;

inc(i_col);

PPnt(pList.Items[ip1])^.Linked:=true;

end;

if (i_col=2) then //2 точки отобраны?

begin //отрисовка линии

p1 := pList.Items[ip1];

p2 := pList.Items[ip2];

sum:=sum+sqrt(sqr(P1^.X - P2^.X) + sqr(P1^.Y -P2^.Y));

Form1.Image1.Canvas.MoveTo(p1^.X, p1^.Y);

if p1^.rColor = 1 then Form1.Image1.Canvas.Pen.Color := clRed;

if p1^.rColor = 2 then Form1.Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo(round((P1^.X+P2^.X)/2),round((P1^.Y+P2^.Y)/2));

if p2^.rColor = 1 then Form1.Image1.Canvas.Pen.Color := clRed;

if p2^.rColor = 2 then Form1.Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo(P2^.X,P2^.Y);

//отображение цифр в таблице

StringGrid1.Cells[start,1] := IntToStr(P1^.num)+'-'+IntToStr(P2^.num);

StringGrid1.Cells[StringGrid1.ColCount-1,1] := IntToStr(round(Sum));

inc(start);

i_col:=0;

end;

end

else

begin

AddDrawPoint(pList, X,Y);

AddGridPoint(pList);

Label1.Caption := 'Красные точки: ' + IntToStr(redCount);

Label2.Caption := 'Синие точки: ' + ' ' + IntToStr(blueCount);

if redCount = blueCount then Button2.Enabled := true else Button2.Enabled := false;

end;

end;

procedure TForm1.ToolButton2Click(Sender: TObject);

begin

rColor := 2;

Screen.Cursor := crCross;

end;

procedure TForm1.Button1Click(Sender: TObject);

Var i: integer;

p: PPnt;

begin

Start := 0;

start_sh := 0;

i_1 := Start_sh;

i_2 := 0;

j_1 := 0;

j_2 := 0;

DeletePoints(pList);

Image1.Canvas.Pen.Color := clBlack;

Image1.Canvas.Brush.Color := clWhite;

Image1.Canvas.Rectangle(Image1.Canvas.ClipRect);

ClearGrid;

end;

procedure TForm1.Button2Click(Sender: TObject);

Var rRect: TRect;

i: integer;

begin

FindLines;

DrawPoints(pList);

ClearGrid;

DrawGrid(pList);

end;

procedure TForm1.Button3Click(Sender: TObject);

Var rRect: TRect;

begin

if Start = pList.Count then //перебор точек по нажатию кнопки "Шаг" завершено

begin

Label3.Caption := 'Минимальная сумма отрезков: ' + FloatToStr(minSum);

exit;

end;

Sum:=0;

tmpList.Clear;

for i:= 0 to pList.Count-1 do //передача всех точек во временный список

begin

Pz := pList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

tmpList.Add(P);

end;

for i:= start to tmpList.Count-2 do //

begin

P := tmpList.Items[i];

if not P^.Linked then

begin

Min := MaxInt;

for j := 0 to tmpList.Count - 1 do

if i<>j then

begin

P2 := tmpList.Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then

begin

if sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y)) < Min then

begin

Min := sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

for i := 0 to start-1 do

begin

P := tmpList.Items[i];

if not P^.Linked then

begin

Min := MaxInt;

for j := 0 to tmpList.Count - 1 do

if i<>j then

begin

P2 := tmpList.Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then

begin

if sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y)) < Min then

begin

Min := sqrt(sqr(P^.X - P2^.X) + sqr(P^.Y - P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

if start=0 then

begin

minsum:=sum;

oList.Clear;

i_1 := 0;

for i:= 0 to tmpList.Count-1 do

begin

Pz := tmpList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

oList.Add(P);

end;

end

else if sum<minsum then

begin

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList.Count-1 do

begin

Pz := tmpList.Items[i];

New(P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz.Linked;

P^.Num := Pz.Num;

oList.Add(P);

end;

end;

i_1 := 0;

StringGrid1.RowCount := start+2;

StringGrid1.ColCount := REdCount+2;

for i:= 0 to oList.Count-1 do

begin

p := oList.Items[i];

if P^.num <> i+1 then

begin

Inc(i_1);

StringGrid1.Cells[i_1,start+1]:= IntToStr(i+1) + '-' + IntToStr(p^.num);

StringGrid1.Cells[StringGrid1.ColCount-1,start+1] := FloatToStr(round(minSum));

StringGrid1.Cells[i_1,0]:= IntToStr(i_1);

StringGrid1.Cells[StringGrid1.ColCount-1,0] := 'Сумма';

end;

end;

StringGrid1.Cells[0,start+1]:= IntToStr(start+1);

DrawGrid(oList);

Image1.Canvas.FillRect(Image1.Canvas.ClipRect);

DrawPoints(oList);

inc(start);

end;

procedure TForm1.N4Click(Sender: TObject);

begin

ShellExecute(Handle, 'open','index.chm',nil , Nil, SW_ShowNormal);

end;

procedure TForm1.N3Click(Sender: TObject);

begin

Form1.Close;

end;

end.

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