Разработка алгоритма

Для приведенного примера приводится словесное описание алгоритма решения задачи «Нахождение кратчайшего пути от одного населенного пункту к другому».

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

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

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

Для реализации ввода данных используется процедура InputData, которая должна осуществлять ввод имён городов с клавиатуры. Если вместо названия города был нажат ввод, то процедура выводит список городов на экран, и пользователь, передвигая курсор и нажимая клавишу Enter составляет список дорог, соединяющих эти города между собой, при нажатии клавиши Esc процедура прекращает свою работу и выполняет возврат в главное меню.

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

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

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

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

Для поиска маршрута используется рекурсивная процедура findnext, которой при её вызове из передаются следующие параметры:

- a(vec) - вектор, каждому городу соответствует номер в маршруте или ноль, если города нет в маршруте;

- tv(integer) - город, следующий в маршруте;

- nv(integer) - город, в который необходимо добраться;

- lv(integer) - количество пройденных городов.

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

Ниже приведена обобщенная схема алгоритма работы основной программы, из которой видна организация взаимодействия программы с процедурами, находящимися в модуле ph.tpu. (рисунок 1)

В схеме используются следующие идентификаторы:

c- нажатая клавиша Enter (#13), Esc(#27)

sl- выбранный пункт меню (#80), (#72)

t- данные о городах

nt- число городов

r- данные о дорогах

nr- число дорог

i- счетчик

fv- вектор пройденных городов

nfv- количество городов

KItems-количество пунктов меню

Рисунок 1