Определение достижимости города в изменяемой системе двусторонних дорог
Содержание
Введение
. Техническое задание
.1 Основания для разработки
.2 Назначение разработки
.3 Рассмотренные альтернативы
.4 Стандарты
.5 Требования пользователя к
программному изделию
. Рабочий проект
.1 Модули и объекты интерфейса
пользователя
.2 Описание подпрограмм модуля Unit
1
.3 Описание подпрограмма модуля Unit
2
.4 Описание подпрограмм модуля Unit
3
.5 Описание подпрограмм модуля Unit
4
.6 Тестовые наборы для отладки
интерфейса пользователя
Заключение
Список использованных источников
Приложения
Введение
Данная курсовая работа реализует такую
актуальную задачу, как определение достижимости города в изменяемой системе
двусторонних дорог.
Эту проблему целесообразно решать через графы.
Сама задача является актуальной как для
общественных предприятий, так и для индивидуальных пользователей, так как
быстро и достоверно находить решение, основываясь на введенных данных. В самой
программе используется создание системы дорог и городов, что дает пользователю
возможность проверки достижимости до любого города, тем самым позволяя
построить свой маршрут заранее.
Данная задача уже имеет ряд решений как с
помощью графов, так и материального моделирования. Но данный продукт имеет ряд
преимуществ, так как понятный даже не осведомленному в программировании пользователю
интерфейс, удобную навигацию и быстроту расчетов.
1. Техническое задание
1.1 Основания для разработки
Основанием для разработки программного продукта
служит задание по курсовой работе по дисциплине "Программирование на
языках высокого уровня".
1.2 Назначение разработки
Даны несколько городов, соединенных между собой
(произвольным образом) двусторонними дорогами. Определить, можно ли построив
какие-нибудь 3 новые дороги, из заданного города А добраться до всех других
городов. Отобразить решение графически, выделив цветом найденный результат.
1.3 Рассмотренные альтернативы
На этапе разработки было предложено 2 среды
разработки:
- C++ Builder 6;
- Borland Delphi 7;
При постановке задачи на разработку данного
программного изделия была выбрана среда разработки Borland
Delphi 7 в силу легкости
проектирования пользовательского интерфейса.
1.4 Стандарты
Разработка программной документации и
программного изделия должна производиться согласно ГОСТ 19.701-90, ГОСТ
2.304-88. Единая система программной документации.
1.5
Требования пользователя к программному изделию
Входные и выходные данные
Входные данные:
система дорог и городов, соединенных
произвольным образом между собой;
файл с расширением *.gph,
содержащий вносимые пользователем данные.
Выходными данными являются:
файл с расширением *.gph,
в котором сохраняются данные,
графическое изображение систем дорог и
городов, соединенных произвольным образом между собой;
матрица смежности и матрица
достижимости;
Информационная совместимость
Форматы хранения данных должны быть разработаны
на основе документов, приведенных 1.5.1 и по своей структуре полностью
соответствовать им.
В качестве входных данных программа должна
использовать файл формата *.ghp,
матрица смежности. Выходными данными должен быть файл формата *.ghp;
графическое изображение систем дорог и городов, соединенных произвольным
образом между собой.
Программные ограничения,
совместимость
Программное изделие должно работать в
операционных системах Windows.
Для переноса программы не должны требоваться специальные программные и
аппаратные средства
Результирующие компоненты изделия
В программное изделие должны входить следующие
компоненты:
хранилище данных (файл с расширением *.gph);
командный файл для запуска приложения;
программная документация на изделие.
Носители информации
Программа должна размещаться в виде файла на
жестком диске компьютера пользователя.
Требования к надежности
Программный продукт должен функционировать на
всех разработанных тестах. Тесты требуется разработать на этапе рабочего
проекта.
Рестарт
В случаях рестарта необходимо запустить на
выполнение программу. Данные при рестарте не сохраняются.
Требования к составу и параметрам
технических средств
Для работы программного модуля необходимо
дисковое пространство не менее 610 Кб, свободная оперативная память в размере
не менее 12 Мб, разрешение экрана не менее 1024*768, также микропроцессор 80486
или выше.
2.
Рабочий проект
2.1 Модули и объекты интерфейса
пользователя
Пользовательский интерфейс включает в себя
следующие компоненты:
набор кнопок управления;
набор счетчиков;
меню программы;
таблица смежности;
таблица достижимости;
Листинг программы представлен в приложении А.
Описание внешнего вида формы предоставлено в
приложении Г.
2.2 Описание подпрограмм модуля
Unit 1
Блок-схемы некоторых главных процедур
предоставлены в приложении Б.
Подпрограмма
procedure TForm1.Button1Click(Sender: TObject)
Входные данные: указатель на вызывающий объект *Sender.
Выходные данные: нет;
Процесс обработки: флажку reb
присваивается значение true,
перу присваивается режим перерисовки, xx
и yy присваивается
значении 0;
Используемые внешние переменные: флажок reb,
который позволяет риcовать ребро
от одной вершины до другой.
Подпрограмма
procedure TForm1.Button2Click(Sender: TObject)
Входные данные: указатель на вызывающий объект *Sender.
Выходные данные: нет;
Процесс обработки: флажку reb
присваивается значение false,
перу присваивается режим перерисовки, xx
и yy присваивается
значении -100, флажку ver
присваивается значение true
;
Используемые внешние переменные: флажок reb,
который позволяет рисовать ребро от одной вершины до другой, если значение true,
флажок ver, который
позволяет рисовать на форме, если значение true;
Подпрограмма
procedure TForm1.Button3Click(Sender: TObject)
Выходные данные: указатель на вызывающий объект
*Sender.
Выходные данные: нет;
Процесс обработки: вызывается форма 3,
вызывается подпрограмма redrow,
которая рисует новые дороги и вызывается подпрограмма Button9.Click,
которая перерисовывает всё.
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.Button4Click(Sender:
TObject)
Входные данные: указатель на вызывающий объект *Sender;
Выходные данные: нет;
Процесс обработки: флажку del_ver
присваивается значение true;
Используемые внешние переменные: флажок del_ver,
который позволяет удалять вершину, если значение true.
Подпрограмма
procedure TForm1.Button5Click(Sender: TObject)
Входные данные: запись ver;
Выходные данные: изображение на Image1;
Процесс обработки: города, расположенные на
компоненте Image1
выстраиваются по окружности. Подпрограмма redrow
перерисовывает изображение.
Используемые внешние переменные: step,
которая позволяет выстроить вершины по окружности;
Подпрограмма
procedure TForm1.Button6Click(Sender: TObject)
Входные данные: запись ver;
Выходных данных: запись ver;
Процесс обработки: через цикл, каждой вершине
присваивается значении 0 и вызывается подпрограмма Button9.Click,
которая задает новые координаты x
и y каждой вершине
через цикл.
Используемые внешние переменные: i-
счетчик, ver[i].x
и ver[i].y
- координаты вершин.
Подпрограмма
procedure TForm1.Button7Click(Sender: TObject)
Входные данные: файл с расширением *.gph;
Выходные данные: данные матрицы смежности;
Процесс обработки: из файла с расширением *.ghp
считываются данные для изображения на компоненте Image1
системы дорог и городов.
Используемые внешние переменные: i,j,k
-счетчики, f - имя файла.
Подпрограмма
procedure TForm1.Button8Click(Sender: TObject)
Входные данные: данные матрица смежности;
Выходные данные: файл с расширением *.gph
и именем f;
Процесс обработки: на диске создается файл с
расширением *.gph, в который
через цикл записывается содержание матрицы смежности.
Используемые внешние переменные: i,j,k
- счетчики, f - имя файла.
Подпрограмма
procedure TForm1.Button9Click(Sender: TObject)
Входные данные: запись ver;
Выходные данные: изображение на Image1;
Процесс обработки: устанавливается step,
присваивается переменной ns
количество городов, если есть города, у которых координаты равны 0 они
изменяются на другие, не нулевые, и вызывается подпрограмма перерисовки.
Используемые внешние переменные: step
- шаг, ns -
количество городов, i - счетчик, vet[i]
- запись вершины с её координатами.
Подпрограмма
procedure TForm1.Button10Click(Sender: TObject)
Входные данные: указатель на вызывающий объект *Sender;
Выходные данные: нет;
Процесс обработки: ячейки матрицы смежности
обнуляются через счетчик, после чего вызывается подпрограмма перерисовки Button9.Click.
Использование внешних переменных: i
- счетчик, n - количество
городов.
Подпрограмма
procedure TForm1.Button11Click(Sender: TObject)
Входные данные: данные с матрицы смежности,
данные с 2-х счетчиков на форме;
Выходные данные: данные матрицы достижимости;
Процесс обработки: через цикл с помощью матрицы
смежности создается матрица достижимости, после чего через цикл идет изменение
матрицы достижимости по алгоритму Флойда. После этого идёт проверка через
условие на достижимость из заданного города А в заданный город В. Результат
выводится на форму в форме текста.
Используемые переменные: i,j,k
- счетчики, dost - двумерный
динамический массив.
Подпрограмма
procedure TForm1.Button12Click(Sender: TObject)
Входные данные: данные с матрицы смежности,
данные с матрицы достижимости, данные с счетчика на форме;
Выходные данные: графическое решение и текстовая
информация, матрица достижимости.
Процесс обработки: вызывается подпрограмма Matrix,
которая составляет матрицу достижимости по матрице смежности. После выполнения
подпрограммы Matrix, переменным
doroga и vver
присваиваются значения, которые показывают количество дорог, которые нужно
достроить. Далее выполняется цикл на проверку матрицы достижимости, если
матрица содержит во всех ячейках 1, то выводится сообщение «Все города
достижимы», после чего начинается цикл, в котором выполняется проверка на
добавление новых дорог.
Используемые переменные: i,j,k-
счетчики, dost - двумерный
динамический массив, dorog,
vver - количества
дорог, result - флажок на
графическое решение.
Подпрограмма function
Matrix;
Входные данные: переменная doroga,
переменная vver, матрица
смежности.
Выходные данные: матрица достижимости,
переменные doroga, vver.
Процесс обработки: подпрограмма обрабатывает
данные с матрицы смежности, подсчитывает количество нужных дорог.
Используемые внешние переменные: doroga,
vver - количество
дорог, dost - двумерный
динамический массив.
Подпрограмма
function findver(x,y,rad:integer):Integer;
Входные данные: x,y,rad;
Выходные данные: findver;
Процесс обработки: подпрограмма находит номер
вершины по координатам x
и y и радиусу, после чего выдает её номер.
Используемые внешние переменные: x,y
- координаты, rad - радиус
окружности.
Подпрограмма procedure
TForm1.redrow;
Входные данные: количество городов, запись ver;
Выходные данные: изображение на компоненте Image1;
Процесс обработки: подпрограмма перерисовывает
изображение на компоненте Image1;
Используемые внешние переменные: i,j
- счетчики;
Подпрограмма
procedure TForm1.FormCreate(Sender: TObject);
Входные данные: указатель на вызывающий объект *Sender;
Выходные данные: количество городов;
Процесс обработки: переменным pos и n
присваивается значение 0;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.Image1MouseMove(Sender:
TObject;
Shift:
TShiftState;
X,Y:
Integer);
Входные данные: координаты xx
и yy, флажки ver,
reb2;
Выходные данные: изображение на компоненте Image1;
Процесс обработки: выполнение подпрограммы
зависит от значений флажков ver
и reb2, если они true,
то подпрограмма по флажку ver
рисует эллипс с координатами х,у на компоненте Image1,
а по флажку reb2 подпрограмма
рисует ребро(дорогу) до заданного города.
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.Image1MouseUp(Sender:
TObject;
Button:
TMouseButton;
Shift:
TShiftState;
X,
Y:
Integer)
Входные данные: флажки del_ver,
reb, reb2,
ver ; координаты клика
x,y;
Выходные данные: изображение на компоненте Image1;
Процесс обработки: выполнение подпрограммы
зависит от значений флажков del_ver,
reb, reb2,
ver.
Если del_ver
true, то подпрограмма
удаляет вершину, с заданными координатами и значение флажков ver,
reb, reb2,
del_ver
изменяет на false, а также
убирает на -1 строчку и столбец в матрице смежности и матрице достижимости,
соответствующие данной вершине.
Если флажок reb
true, то подпрограмма
рисует линию от одной вершины до другой. Если другая вершина указана не
указана, то значение reb
становится false.
Если reb2
true, то reb
false, reb2
false и строится линия
от одной вершины до другой и в матрицу смежности в ячейке ставится значение
«1», указывающее на ребро между этими городами.
Если ver
true, то значение
городов увеличивается на +1, запоминаются координаты в структуру ver
- запись и в матрице смежности и достижимости добавляется строчка и столбец с
соответствующим номером города.
Используемые внешние переменные: xx,yy
- координаты с компонента Image1,
i,j,k,i2
- счетчики;
Подпрограмма
procedure TForm1.N5Click(Sender: TObject)
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: выход из программы;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.N2Click(Sender:
TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: вызов подпрограммы
Button7.Click;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.N3Click(Sender:
TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: вызов подпрограммы
Button8.Click;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.N4Click(Sender:
TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: создание нового графа;
Используемые внешние переменные: i,j - счетчики
;
Подпрограмма
procedure TForm1.StringGrid3KeyPress(Sender: TObject; var Key: Char);
Входные данные: числа;
Выходные данные: нет;
Процесс обработки: подпрограмма запрещает
вводить числа на главной диагонали в матрице достижимости, а так же ограничивает
ввод чисел, кроме 0 и 1 и использование клавиш, кроме Backspace.
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.Edit1Change(Sender:
TObject)
Входные данные: число городов;
Выходные данные: данные матрицы смежности,
изображение на компоненте Image1;
Процесс обработки: создается матрица смежности и
матрица достижимости размером [pos*pos], где pos - количество городов, а также
заполнение ячеек матрицы смежности и матрицы достижимости значением «0».
Используемые внешние переменные: pos, n -
количество городов, i,j-счетчики.
Подпрограмма
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift:
TShiftState; X, Y: Integer);
Входные данные: координаты места клика левой
клавишей мыши X и Y
;
Выходные данные: изображение контекстного меню
на компоненте Image1;
Процесс обработки: если нажата не левая клавиша
мыши, то показать контекстное меню.
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.N7Click(Sender:
TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: вызов подпрограммы
Button2.Click;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.N8Click(Sender:
TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: вызов подпрограммы
Button1.Click;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.N9Click(Sender:
TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: вызов подпрограммы
Button4.Click;
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.StringGrid3KeyUp(Sender:
TObject;
var
Key:
Word;
Shift:
TShiftState);
Входные данные: данные с матрицы смежности;
Входные данные; изображение на компоненте
Image1;
Процесс обработки: подпрограмма вызывает
подпрограмму redrow.
Используемые внешние переменные: нет;
Подпрограмма procedure
TForm1.vvChange(Sender:
TObject);
Входные данные: данные с счетчика vv.Value;
Входные данные: нет;
Процесс обработки: подпрограмма делает
ограничение на ввод в счетчик vv.Value значение больше значения количества
городов.
Используемые внешние переменные: pos -
количество городов.
Подпрограмма
procedure TForm1.IsvChange(Sender: TObject);
Входные данные: данные с счетчика Isv.Value;
Входные данные: нет;
Процесс обработки: подпрограмма делает
ограничение на ввод в счетчик Isv.Value значение больше значения количества
городов.
Используемые внешние переменные: pos -
количество городов.
Подпрограмма
procedure TForm1.IzverChange(Sender: TObject);
Входные данные: данные с счетчика Izver.Value;
Входные данные: нет;
Процесс обработки: подпрограмма делает
ограничение на ввод в счетчик Izver.Value
значение больше значения количества городов.
Используемые внешние переменные: pos
- количество городов.
Подпрограмма
procedure TForm1.N6Click(Sender: TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: вызов формы 2;
Используемые внешние переменные: нет;
Подпрограмма
procedure redrow_result_true;
Входные данные: количество городов, запись ver;
Выходные данные: изображение на компоненте Image1;
Процесс обработки: аналогичен подпрограмме redrow
за исключением выделения ответа другим цветом. В данном случае зеленым, который
показывает достижимость всех городов из заданного города А.
Используемые внешние переменные: i,j
- счетчики.
Подпрограмма
procedure redrow_result_false;
Входные данные: количество городов, запись ver;
Выходные данные: изображение на компоненте Image1;
Процесс обработки: аналогичен подпрограмме redrow
за исключением выделения ответа другим цветом. В данном случае синим, который
показывает не достижимость некоторых городов из заданного города А.
Используемые внешние переменные: i,j
- счетчики.
Подпрограмма
procedure TForm1.StringGrid3Set(Sender: TObject; ACol, ARow: Integer; const
Value: String);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: подпрограмма выполняет
заполнение матрицы смежности симметрично относительно главной диагонали.
Используемые внешние переменные: нет;
Подпрограмма procedure
Dostizhimost(izver:integer);
Входные данные: номер города;
Выходные данные: текстовое сообщение о достижимости
или не достижимости до всех городов из заданного города А;
Процесс обработки: подпрограмма строит матрицу
достижимости по матрице смежности, делает проверку на достижимость до всех
городов из заданного города А через цикл и выводит сообщение с соответствующим
результатом.
Используемые внешние переменные: dost
- двумерный динамический массив, или матрица достижимости; i,j,k
- счетчики.
2.3 Описание подпрограмма модуля
Unit 2
Подпрограмма
procedure TForm2.Label1Click(Sender: TObject)
Входных данных: нет;
Выходных данных: нет;
Процесс обработки: подпрограмма выполняет
закрытие формы 2 по клику на содержимое формы;
Используемые внешние переменные:
нет;
2.4 Описание подпрограмм модуля
Unit 3
Подпрограмма
procedure TForm3.Button1Click(Sender: TObject);
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: закрытие формы;
Используемые внешние переменные: нет;
2.5 Описание подпрограмм модуля
Unit 4
Подпрограмма
procedure TForm4.Button1Click(Sender: TObject)
Входные данные: нет;
Выходные данные: нет;
Процесс обработки: подпрограмма выполняет
закрытие заставочной формы при нажатии на клавишу «ОК».
Используемые внешние переменные:
нет.
2.6 Тестовые наборы для отладки
интерфейса пользователя
Для отладки интерфейса разработаны следующие
тестовые наборы:
1. Случай использования: запуск
программы.
Предусловие: открыта заставочная форма.
Тестовый случай: нажатие пользователем на кнопку
«ОК»;
Ожидаемый результат: закрытие заставочной формы,
появление окна главной формы. (Приложение В, рисунок 1)
2. Случай использования:
добавление нового города на компонент Image1.
Предусловие: открыта главная форма;
Тестовый случай: нажатие пользователем на кнопку
«Разместить город 1» и нажатие левой клавишей мыши на область компонента Image1;
Ожидаемый результат: на компоненте Image1
появится эллипс с номером города в центре желтого цвета. (Приложение Г, рисунок
2)
3. Случай использования:
добавление дороги между городами;
Предусловие: открыта головная форма, имеются 2
города, не соединенных между собой дорогой.
Тестовый случай: нажатие пользователем на кнопку
«Добавить дорогу» на главной форме или же в контекстном меню, после последующее
нажатие на город 1 и город 2.
Ожидаемый результат: на компоненте Image1
между двумя городами появится линия, на концах который расположено по 4 красных
маленьких эллипса разного диаметра. (Приложение Г, рисунок 3)
4. Случай использования:
удаление города.
Предусловие: открыта головная форма, имеется
хотя бы 2 города на компоненте Image1.
Тестовый случай: нажатие пользователем на кнопку
«Удалить город» на главной форме или же через контекстное меню.
Ожидаемый результат: на компоненте Image1
исчезнет изображение города, на который было произведено нажатие левой клавишей
мыши, также уменьшение матрицы смежности и достижимости на -1 строку и столбец
и удаление дорог, если они были от этого города. (Приложение Г, рисунок 4)
5. Случай использования:
просмотр задания;
Предусловие: открыта главная форма;
Тестовый случай: нажатие пользователем на кнопку
«Задание»;
Ожидаемый результат: появление формы, с
содержанием задания, которое выполняет данная программа. (Приложение Г, рисунок
5)
6. Случай использования:
проверка на достижимость из заданного города А в заданный город В;
Предусловие: задана система дорог и координат,
указан начальный и конечный город проверки.
Тестовый случай: нажатие пользователем на
клавишу «Проверить достижимость»;
Ожидаемый результат: вывод сообщения на главную
форму о достижимости или не достижимости из указанного города А в указанный
город В. (Приложение Г, рисунок 6)
7. Случай использования:
достижимости до всех городов из заданного города А.
Предусловие: задана система дорог и городов,
заданный город А.
Тестовый случай: нажатие пользователя на кнопку
«Проверить достижимость»;
Ожидаемый результат: вывод результата на главную
форму в виде графического решения с цветом дорог:
если дороги зеленые - все города
достижимы из города А;
если дороги желтые - не все города
достижимы из города А; (Приложение Г, рисунок 7(а,б))
8. Случай использования:
задание определенного количества городов через счетчик.
Предусловие: на компоненте Image1 имеется хотя
бы 1 город.
Тестовый случай: увеличение или уменьшение
счетчика количества городов.
Ожидаемый результат: на компоненте Image1
появится заданное количество город. (Приложение Г, рисунок 8)
9. Случай использования:
загрузка графа из файла.
Предусловие: имеется файл формата *.gph с
данными матрицы смежности.
Тестовый случай: нажатие пользователя на кнопку
«Загрузить файл графа с файла» и указание файла через проводник.
Ожидаемый результат: заполнение матрицы
смежности по данным из файла и графическое отображение городов на компоненте
Image1. (Приложение Г, рисунок 9)
10. Случай использования:
сохранения текущего графа в файл.
Предусловие: имеется система дорог и городов.
Тестовый случай: нажатие пользователя на кнопку
«Сохранить текущий граф в файл», указание места сохранения через проводник и
имя файла.
Ожидаемый результат: на диске появится файл с
именем, который задал пользователь и форматом *.gph, содержащий данные матрицы
смежности. (Приложение Г, рисунок 10)
11. Случай использования:
удаление всех дорог;
Предусловие: имеется система дорог и городов.
Тестовый случай: нажатие пользователя на кнопку
«Удалить все дороги»;
Ожидаемый результат: в имеющейся системе дорог и
городов будут удалены все дороги. (Приложение Г, рисунок 11)
Заключение
Таким образом, данный программный продукт
полностью реализует поставленную задачу. Программа предоставляет возможность
для создания системы дорог и городов, а так же быстро и точно определяет
достижимость до всех других городов и изменяемой системе дорог. Также проект
содержит понятный пользователю интерфейс, на котором предоставляется решение
задачи в виде системы дорог и городов и полученных в результате решения данных.
Список использованных источников
1. Круз
Р.Л. Структуры данных и проектирование программ / Р.Л. Круз; пер.с англ. - М.:
БИНОМ. Лаборатория знаний, 2008 - 765 с.: ил. - (Программисту).
2. Кузнецов
А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое
программирование. - Минск: Высшая школа, 2010 г.- С.792.
. Оре
О. Теория Графов. - М.: Наука, 2010 г.
. Белов.
Теория Графов. - М.: Наука, 2011 г.
. Нефедов
В.Н., Осипова В.А. Курс дискретной математики. - М.: МАИ, 2010 г.
Приложение А
Листинг программы
дорога город достижимость интерфейс
unit Unit1; // модуль формы 1 «Проверка
достижимости из города А до всех других дорог в изменяемой системе дорог»
interface// стандартные
модули,
Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls,
Grids, ExtCtrls, ComCtrls, Menus, ExtDlgs, Spin, XPMan;
type= class(TForm) // типы объектов графического
интерфейса и процедуры модуля
Image1: TImage;: TMainMenu;:
TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;
OpenDialog1: TOpenDialog;: TSaveDialog;:
TMenuItem;
PopupMenu1: TPopupMenu;: TMenuItem;:
TMenuItem;: TMenuItem;: TGroupBox;: TPageControl;: TTabSheet;: TButton;:
TButton;: TButton;: TButton;: TGroupBox;: TButton;: TButton;: TButton;:
TXPManifest;: TGroupBox;: TLabel;: TLabel;: TSpinEdit;: TLabel;: TSpinEdit;:
TButton;: TMenuItem;: TLabel;: TTabSheet;: TStringGrid;: TButton;: TButton;:
TSpinEdit;: TLabel;: TTabSheet;: TLabel;: TStringGrid;: TSpinEdit;: TButton;:
TButton;FormCreate(Sender: TObject);Button2Click(Sender: TObject);Image1MouseMove(Sender:
TObject; Shift: TShiftState; X,: Integer);Image1MouseUp(Sender: TObject;
Button: TMouseButton;: TShiftState; X, Y: Integer);redrow;Button1Click(Sender:
TObject);Button9Click(Sender: TObject);Button5Click(Sender:
TObject);Button4Click(Sender: TObject);Button10Click(Sender:
TObject);N5Click(Sender: TObject);N2Click(Sender: TObject);N3Click(Sender:
TObject);N4Click(Sender: TObject);StringGrid3KeyPress(Sender: TObject; var Key:
Char);Edit1Change(Sender: TObject);Image1MouseDown(Sender: TObject; Button:
TMouseButton;: TShiftState; X, Y: Integer);N7Click(Sender:
TObject);N8Click(Sender: TObject);N9Click(Sender: TObject);Button6Click(Sender:
TObject);Button7Click(Sender: TObject);Button8Click(Sender:
TObject);N10Click(Sender: TObject);Button11Click(Sender:
TObject);StringGrid3KeyUp(Sender: TObject; var Key: Word;:
TShiftState);vvChange(Sender: TObject);isvChange(Sender:
TObject);N6Click(Sender: TObject);StringGrid3Set(Sender: TObject; ACol,:
Integer; const Value: String);Button3Click(Sender: TObject);Button12Click(Sender:
TObject);IzverChange(Sender: TObject);
{ Private declarations }
{ Public declarations };= record
x,y:Integer;:Integer;
end;:
TForm1;,pos2:Integer;,xx,yy,xb,yb,ugol,doroga,vver,i,j,k:Integer;,reb,reb2,del_ver,result:Boolean;:array[1..100]
of vv;:array of array of integer;Math, Unit2, Unit3, Unit4;
var i:Integer;:=0;i:=1 to pos do
begin(x>vers[i].x-rad) and (x<vers[i].x+rad) and (y>vers[i].y-rad) and
(y<vers[i].y+rad) then:=i;;;Matrix; //алгоритм
Флойда.(dost,
pos,pos);i:=1 to pos doj:=1 to pos doForm1.StringGrid3.Cells[j,i]<>'0'
then[i-1,j-1]:=1 else dost[i-1,j-1]:=0;i:=1 to pos doj:=1 to pos
dodost[j-1,i-1]=0 then doroga:=doroga+1;
for k:=0 to pos-1 do // ищем можно ли сократить
путь через третью вершину К
for i:=0 to pos-1 doj:=0 to pos-1
do[i,j]:= dost[i,j] or (dost[i,k] and dost[k,j]) ;i:=1 to pos doj:=1 to pos
dodost[j-1,i-1]=0 then vver:=vver+1;.StringGrid1.Cells[j,i]:=inttostr(dost[i-1,j-1]);
end;;TForm1.redrow; // перерисовка изображения
графа на картинкеi,j:Integer; // вспомогательные переменные
beginpos =0 then
exit;:=stringgrid3.ColCount-1;.Canvas.Pen.Mode := pmCopy;.Canvas.Brush.Color :=
clWhite;.Canvas.Rectangle(0,0,Image1.Width,Image1.Height); // очистка
канваса
без
мигания.Canvas.Pen.Width:=1;i:=1
to n do // рисуем дугиj:=1
to n dostrtoint(StringGrid3.Cells[i,j])>0
then.Canvas.MoveTo(vers[i].x,vers[i].y);.Canvas.lineTo(vers[j].x,vers[j].y);
/// красная точка направления.Canvas.pen.Color
:= clRed;
Image1.Canvas.Brush.Color :=
clRed;.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.9)-4,round(vers[j].y+(vers[i].y-
vers[j].y)*0.9)-4,(vers[j].x+(vers[i].x-
vers[j].x)*0.9)+4,round(vers[j].y+(vers[i].y- vers[j].y)*0.9)+4);.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.93)-3,round(vers[j].y+(vers[i].y-
vers[j].y)*0.93)-3,(vers[j].x+(vers[i].x-
vers[j].x)*0.93)+3,round(vers[j].y+(vers[i].y-
vers[j].y)*0.93)+3);.Canvas.ellipse(round(vers[j].x+(vers[i].x- vers[j].x)*0.95)-2,round(vers[j].y+(vers[i].y-
vers[j].y)*0.95)-2,(vers[j].x+(vers[i].x-
vers[j].x)*0.95)+2,round(vers[j].y+(vers[i].y-
vers[j].y)*0.95)+2);.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.97)-1,round(vers[].y+(vers[i].y- vers[j].y)*0.97)-1,(vers[j].x+(vers[i].x-
vers[j].x)*0.97)+1,round(vers[j].y+(vers[i].y-
vers[j].y)*0.97)+1);.Canvas.Pen.Color := clBlack;.Canvas.Brush.Color :=
clWhite;.Canvas.pen.Style:= psSolid ;;i:=1 to n do
begin // вершины - кружки с номером вершины
Image1.Canvas.Brush.Color:=RGB(234,228,36);.Canvas.Ellipse(vers[i].x-10,vers[i].y-10,vers[i].x+10,vers[i].y+10);.Canvas.TextOut(vers[i].x-3,vers[i].y-6,inttostr(i));;;TForm1.FormCreate(Sender:
TObject);:=0;:=0;:=false;;TForm1.Button2Click(Sender: TObject);:=false;:=-100;:=-100;.Canvas.Pen.Mode
:= pmNotXor;:= True;;TForm1.Image1MouseMove(Sender: TObject; Shift:
TShiftState; X,: Integer);ver
then.Canvas.Ellipse(xx-10,yy-10,xx+10,yy+10);:=x;:=y;.Canvas.Ellipse(x-10,y-10,x+10,y+10);;reb2
then.Canvas.MoveTo(xb,yb);.Canvas.LineTo(xx,yy);:=x;:=y;.Canvas.MoveTo(xb,yb);.Canvas.LineTo(x,y);:=x;:=y;;;TForm1.Image1MouseUp(Sender:
TObject; Button: TMouseButton;: TShiftState; X, Y:
Integer);j,k,i,i2,xx,yy:integer;del_ver then// удаление
вершины
//найти удаляемую вершину:=findver(x,y,10); //удалить
все ребра которые входят и выходят их этой вершины
ver:= false;:=
false;:=false;_ver:=false;
if k=0 then exit;i:=1 to
StringGrid3.ColCount-1 doi>=k then vers[i]:=vers[i+1];
// будем копировать на единицу назад столбцы,
если они стоят правее удаляемой вершины
for i:=1 to StringGrid3.RowCount-1
doj:=1 to StringGrid3.RowCount-1 doj>=k then
StringGrid3.Cells[i,j]:=StringGrid3.cells[i,j+1];j:=1 to StringGrid3.RowCount-1
doi:=1 to StringGrid3.RowCount-1 doi>=k then
StringGrid3.Cells[i,j]:=StringGrid3.cells[i+1,j];:=pos-1;.Value:=edit1.Value-1;.cells[0,0]:='*';;.Canvas.Pen.Mode
:= pmCopy;.Caption:= 'Разместить
город
'+IntToStr(pos+1);;ver then(pos);[pos].x:=x;[pos].y:=y;
xx:=-100;yy:=-100;[pos].num:=pos;
ver:=False;.Caption:= 'Разместить
город
'+IntToStr(pos+1);pos>1
then.ColCount:=StringGrid3.ColCount+1;.RowCount:=StringGrid3.RowCount+1;.Value
:=pos;;i:=1 to edit1.value+1 do
begin // рисуем новые номера вершин после изм.
количества вершин
StringGrid3.Cells[i,0]:=
inttostr(i);.Cells[0,i]:= inttostr(i);;i:=1 to edit1.value doi2:=1 to
edit1.value doStringGrid3.Cells[i2,i]='' then.cells[i2,i]:='0';
end;;;// перерисуем что получилось после
добавления вершины
end;reb2 then
begin:=false;:=false;:=0;:=0;:=findver(x,y,10);
If i <>0 then// если указали все верно из
одного кружка вершины в другой, то добавим в матрицу смежности запись
StringGrid3.Cells[findver(x,y,10),findver(xb,yb,10)]:='1';.Cells[findver(xb,yb,10),findver(x,y,10)]:='1';.cells[0,0]:='*';;;;;;reb
then:=x;:=y;:=x;:=y;:=True;.Canvas.MoveTo(0,0);.Canvas.LineTo(x,y);:=findver(x,y,10);i
<>0 then(n);.Cells[pos2,0]:=inttostr(i);
i:=findver(x,y,10); // найти к какой вершине мы
сейчас добавляем ребро;;:=false; // неудачная попытка добавить ребро
end;;;TForm1.Button1Click(Sender:
TObject);:=0;:=0;.Canvas.Pen.Mode :=
pmNotXor;:=true;;TForm1.Button9Click(Sender: TObject);ns,ms,
x,y,i,j:Integer;:real;:= 4*3.14/ edit1.value;:=(edit1.value);i:=1 to
edit1.value do((vers[i].x=0) or(vers[i].y=0)) then((findver(x,y,20)>0) or
(x<50) or ((y+50)>image1.Height) or (y<50) or ((x+50)>image1.Width))
do:=image1.Width-random(image1.Width*2);:=image1.Height-random(image1.Height*2);:=ns+
300+ trunc(cos(i*step+ms+ugol/100)*100);:=ms+ 150+
trunc(sin(i*step+ns+ugol/100)*100);;[i].x:=x;
vers[i].y:=y;;;;TForm1.Button5Click(Sender: TObject);
var x,y:Integer;:Integer;
step:real;:=2*3.14/ edit1.value;i:=1
to edit1.value do[i].x:= 300+ trunc(cos(i*step+ugol/100)*100);[i].y:= 150+
trunc(sin(i*step+ugol/100)*100);;;;TForm1.Button4Click(Sender:
TObject);_ver:=true;;TForm1.Button10Click(Sender: TObject);i,j:Integer;
// очистка
грида:=edit1.Value;:=edit1.Value;i:=1
to n doj:=1 to n do.cells[j,i]:='0';.Click;;TForm1.N5Click(Sender:
TObject);(0);;TForm1.N2Click(Sender: TObject);
begin.Click; // вызов открытия из меню
end;TForm1.N3Click(Sender: TObject);
begin.click; // вызов сохранения их меню
end;TForm1.N4Click(Sender: TObject);
// новый
графi,j:integer;.click;
// вначале
очистка
грида
edit1.Value:=1; // убираем лишние строки и
столбцы
label5.Caption:=' ';.click; // обновляем
картинку.Caption:=
'Разместить
город
'+IntToStr(pos+1);i:=0 to pos-1 doj:=0 to pos-1
do.Cells[i,j]:='0';.Cells[i,j]:='0';;;TForm1.StringGrid3KeyPress(Sender:
TObject; var Key: Char);(Sender as TStringGrid).col=(Sender as TStringGrid).row
// нельзя
ставить
на
главное
диагоналиkey
:= Chr(0);Key of
#8,'1','0':; // цифры и клавиша
<Backspace>key := Chr(0); // остальные символы запрещены
end;;TForm1.Edit1Change(Sender:
TObject);i,j : integer;
StringGrid3.ColCount:=edit1.Value+1;// при
изменении спинбокса нужно перерисовать
матрицу.RowCount:=edit1.Value+1;.ColCount:=edit1.Value+1;// при изменении
спинбокса нужно перерисовать матрицу
StringGrid1.RowCount:=edit1.Value+1;:=edit1.Value;
pos:=edit1.Value;
// надписи о номерах
for i:=1 to n+1 do.Cells[i,0]:=
inttostr(i);.Cells[0,i]:= inttostr(i);;i:=1 to n+1 do.Cells[i,0]:=
inttostr(i);.Cells[0,i]:= inttostr(i);;i:=1 to n doj:=1 to n
doStringGrid3.Cells[j,i]='' then.cells[j,i]:='0';;i:=1 to n doj:=1 to n
doStringGrid1.Cells[j,i]='' then.cells[j,i]:='0';;.Click; // обновить
картинку.Caption:=
'Разместить
город
'+IntToStr(pos+1);;;;TForm1.Image1MouseDown(Sender: TObject; Button:
TMouseButton; // по нажатию
на
имаже:
TShiftState; X, Y: Integer);button <>mbLeft then // если
нажали
левой
кнопкой.Popup(Mouse.CursorPos.X,
Mouse.CursorPos.y); // показать
контекстное
меню;TForm1.N7Click(Sender:
TObject);.Click ;;TForm1.N8Click(Sender: TObject);.Click
;;TForm1.N9Click(Sender: TObject);.Click;;TForm1.Button6Click(Sender:
TObject);i :integer;i:=1 to edit1.value do[i].x:=0; vers[i].y:=0;;.Click
;;TForm1.Button7Click(Sender: TObject);: TextFile;, i, k: Integer;: String;(not
OpenDialog1.Execute()) then exit;(f,OpenDialog1.FileName);(f);StringGrid3 do(f,
iTmp);:= iTmp;(f, iTmp);:= iTmp;.Value:=ColCount-1;i := 0 to ColCount - 1 dok :=
0 to RowCount - 1 do(f, strTemp);[i, k] :=
strTemp;;.Caption:='';;(f);StringGrid3.ColCount>10 then button6.Click else
button5.Click;// обновим
изображение.Caption:=
'Разместить
город
'+IntToStr(pos+1);;TForm1.Button8Click(Sender: TObject);: TextFile;, k: Integer;(not
SaveDialog1.Execute()) then exit; // проверяем
открылся
ли
диалог
загрузки(f,
SaveDialog1.FileName);(f);StringGrid3 do(f, ColCount);(f, RowCount);i := 0 to
ColCount - 1 dok := 0 to RowCount - 1 do(F, Cells[i,
k]);;(F);;TForm1.N10Click(Sender: TObject);
begin.Click; // вызов решения гамильтонова цикла
end;TForm1.Button11Click(Sender:
TObject);i,j,k: integer;:array of array of integer;pos<2 then exit;(dost,
pos,pos);i:=1 to pos doj:=1 to pos doStringGrid3.Cells[j,i]<>'0'
then[i-1,j-1]:=1 else dost[i-1,j-1]:=0;
for k:=0 to pos-1 do // ищем можно ли сократить
путь через третью вершину К
for i:=0 to pos-1 doj:=0 to pos-1
do[i,j]:= dost[i,j] or (dost[i,k] and dost[k,j]) ;dost[ isv.Value-1,
vv.Value-1]=0 then
label5.Caption:='Город НЕ достижим'
begin.Caption:='Город
достижим';i:=1
to pos doj:=1 to pos
do.Cells[j,i]:=inttostr(dost[i-1,j-1]);;;TForm1.StringGrid3KeyUp(Sender:
TObject; var Key: Word;: TShiftState);;;TForm1.vvChange(Sender:
TObject);vv.Value>pos then vv.Value:=pos;;TForm1.isvChange(Sender: TObject);isv.Value>pos
then isv.Value:=pos;;TForm1.IzverChange(Sender: TObject);izver.Value>pos
then izver.Value:=pos;;TForm1.N6Click(Sender:
TObject);.show;;redrow_result_true;i,j:integer;pos =0 then
exit;:=form1.stringgrid3.ColCount-1;.Image1.Canvas.Pen.Mode :=
pmCopy;.Image1.Canvas.Brush.Color :=
clWhite;.Image1.Canvas.Rectangle(0,0,form1.Image1.Width,form1.Image1.Height);
// очистка
канваса
без
мигания.Image1.Canvas.Pen.Width:=3;.Image1.Canvas.Pen.Color
:= clGreen;i:=1 to n do // рисуем
ребраj:=1
to n dostrtoint(form1.StringGrid3.Cells[i,j])>0
then.Image1.Canvas.MoveTo(vers[i].x,vers[i].y);.Image1.Canvas.lineTo(vers[j].x,vers[j].y);
/// красная
точка
направления.Image1.Canvas.pen.Color
:= clRed;.Image1.Canvas.Brush.Color := clRed;.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.9)-4,round(vers[j].y+(vers[i].y-
vers[j].y)*0.9)-4,(vers[j].x+(vers[i].x-vers[j].x)*0.9)+4,round(vers[j].y+(vers[i].y-
vers[j].y)*0.9)+4);.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.93)-3,round(vers[j].y+(vers[i].y-
vers[j].y)*0.93)-3,(vers[j].x+(vers[i].x-
vers[j].x)*0.93)+3,round(vers[j].y+(vers[i].y-
vers[j].y)*0.93)+3);.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.95)-2,round(vers[j].y+(vers[i].y- vers[j].y)*0.95)-2,(vers[j].x+(vers[i].x-
vers[j].x)*0.95)+2,round(vers[j].y+(vers[i].y-
vers[j].y)*0.95)+2);.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.97)-1,round(vers[j].y+(vers[i].y-
vers[j].y)*0.97)-1,(vers[j].x+(vers[i].x- vers[j].x)*0.97)+1,round(vers[j].y+(vers[i].y-
vers[j].y)*0.97)+1);.Image1.Canvas.Pen.Width:=3;.Image1.Canvas.Pen.Color :=
clGreen;.Image1.Canvas.Brush.Color := clWhite;.Image1.Canvas.pen.Style:=
psSolid ;;.Image1.Canvas.Pen.Width:=1;.Image1.Canvas.Pen.Color := clBlack;
for i:=1 to n do// вершины - кружки с номером
вершины
Form1.Image1.Canvas.Brush.Color:=RGB(234,228,36);.Image1.Canvas.Ellipse(vers[i].x-10,vers[i].y-10,vers[i].x+10,vers[i].y+10);.Image1.Canvas.TextOut(vers[i].x-3,vers[i].y-6,inttostr(i));;;redrow_result_false;i,j:integer;pos
=0 then exit;:=form1.stringgrid3.ColCount-1;.Image1.Canvas.Pen.Mode :=
pmCopy;.Image1.Canvas.Brush.Color :=
clWhite;.Image1.Canvas.Rectangle(0,0,form1.Image1.Width,form1.Image1.Height);
// очистка
канваса
без
мигания.Image1.Canvas.Pen.Width:=3;.Image1.Canvas.Pen.Color
:= clYellow;i:=1 to n do // рисуем
ребраj:=1
to n dostrtoint(form1.StringGrid3.Cells[i,j])>0
then.Image1.Canvas.MoveTo(vers[i].x,vers[i].y);.Image1.Canvas.lineTo(vers[j].x,vers[j].y);
/// красная
точка
направления.Image1.Canvas.pen.Color
:= clRed;.Image1.Canvas.Brush.Color :=
clRed;.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.9)-4,round(vers[j].y+(vers[i].y-
vers[j].y)*0.9)-4,(vers[j].x+(vers[i].x-vers[j].x)*0.9)+4,round(vers[j].y+(vers[i].y-
vers[j].y)*0.9)+4);.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.93)-3,round(vers[j].y+(vers[i].y-
vers[j].y)*0.93)-3,(vers[j].x+(vers[i].x-
vers[j].x)*0.93)+3,round(vers[j].y+(vers[i].y-
vers[j].y)*0.93)+3);.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.95)-2,round(vers[j].y+(vers[i].y-
vers[j].y)*0.95)-2,(vers[j].x+(vers[i].x-
vers[j].x)*0.95)+2,round(vers[j].y+(vers[i].y-
vers[j].y)*0.95)+2);.Image1.Canvas.ellipse(round(vers[j].x+(vers[i].x-
vers[j].x)*0.97)-1,round(vers[j].y+(vers[i].y- vers[j].y)*0.97)-1,(vers[j].x+(vers[i].x-
vers[j].x)*0.97)+1,round(vers[j].y+(vers[i].y-
vers[j].y)*0.97)+1);.Image1.Canvas.Pen.Width:=3;.Image1.Canvas.Pen.Color :=
clYellow;.Image1.Canvas.Brush.Color := clWhite;.Image1.Canvas.pen.Style:=
psSolid ;;.Image1.Canvas.Pen.Width:=1;.Image1.Canvas.Pen.Color := clBlack;
for i:=1 to n do// вершины - кружки с номером
вершины
Form1.Image1.Canvas.Brush.Color:=RGB(234,228,36);.Image1.Canvas.Ellipse(vers[i].x-10,vers[i].y-10,vers[i].x+10,vers[i].y+10);.Image1.Canvas.TextOut(vers[i].x-3,vers[i].y-6,inttostr(i));;;TForm1.StringGrid3Set(Sender:
TObject; ACol,: Integer; const Value: String);(Sender).Cells[ARow, ACol] :=
Value;;TForm1.Button3Click(Sender:
TObject);.Show;;.Click;;Dostizhimost(izver:integer);:=izver;:=0;:=0;pos<2
then exit;;i:=1 to pos dodost[izver-1,i-1]<>0
then:=true;.Label5.Caption:='Все
города
достижимы';;:=Round((doroga-pos)/(5*pos));:=Round(vver/pos);(doroga<=3)
and ((vver<5) or (vver=6) or (vver=10)) theni:=1 to pos doj:=1 to pos+1
dodost[izver-1,j-1]=0
then.StringGrid3.Cells[izver,j]:='1';.StringGrid3.Cells[j,izver]:='1';
Form1.Label5.Caption:='Все города достижимы';
result:=true;;;j:=1 to pos
dodost[izver-1,j-1]=0
then.StringGrid3.Cells[izver,j]:='1';.StringGrid3.Cells[j,izver]:='1';
Form1.Label5.Caption:='Все города достижимы';
Matrix;;;begin:=false;.Label5.Caption:='Не
все
города
достижимы';;;TForm1.Button12Click(Sender:
TObject);i,j:integer;(Form1.izver.Value);result then redrow_result_true else
redrow_result_false;;.Unit2; // модуль
формы
2 «О
программе»,
Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;=
class(TForm): TLabel;Label1Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm2;
{$R *.dfm}TForm2.Label1Click(Sender:
TObject);;;.Unit3; // модуль формы
3 «Задание»,
Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,,
StdCtrls,unit1;= class(TForm): TButton;: TLabel;Button1Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm3;
{$R *.dfm}TForm3.Button1Click(Sender:
TObject);;;.Unit4; // модуль формы
4 «Заставочная
форма»,
Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, ExtCtrls,
StdCtrls;= class(TForm): TTimer;: TButton;: TLabel;:
TImage;Button1Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm4;
{$R
*.dfm}TForm4.Button1Click(Sender: TObject);.Timer1.Enabled:=false;
close;;.
Приложение Б
Блок-схемы основных подпрограмм.
1. Достижимость до всех городов
(подпрограмма procedure
Dostizhimost(izver:integer))
2. Построение матрицы достижимости по
матрице смежности (подпрограмма Matrix)
Приложение В
Описание внешнего вида
пользовательского интерфейса
На рисунке представлена главная форма программы.
Компоненты главной формы:
- Image1;
- Buttons;
- SpinEdit;
- StringGrid;
- GroupBox;
- PageControl;
- MainMenu;
- PopupMenu
- Label;
На рисунке 1 отмечено 4 области:
. Визуальный редактор, который состоит из
4-х кнопок: «Разместить город», «Добавить дорогу», «Удалить город», «Задание»;
каждой из которых привязана своя подпрограмма.
. Решение, которое состоит из 3-х
счетчиков: а) - пункт А, б) пункт В, в) - пункт В; 2-х кнопок: «Проверить
достижимость», «Достижимость до всех городов»; и поля для рисования системы
дорог и городов.
. Меню программы, которое содержит в себе
2 подменю :
· Файл:
· О программе:
. Граф, который содержит в себе:
· Матрицу смежности:
· Матрицу достижимости:
· Управление графом:
· 2 кнопки: «Загрузить граф из файла»,
«Сохранить текущий граф в файл»;
· Счетчик городов.
Приложение Г
Тестовый случай 1
Рисунок 1
Тестовый случай 2:
Рисунок 2
Тестовый случай 3
Рисунок 3
Тестовый случай 4
Рисунок 4
Тестовый случай 5
Рисунок 5
Тестовый случай 6
Рисунок 6
Тестовый случай 7
Рисунок 7 (а)
Рисунок 7 (б)
Тестовый случай 8
Рисунок 8
Тестовый случай 9
Рисунок 9
Тестовый случай 10
Рисунок 10
Тестовый случай 11
Рисунок 11