Нахождение пути от одного населённого пункта к другому
Цель работы:
Разработать программу, осуществляющую нахождение пути от одного населённого пункта к другому.
Введение
В настоящее время индустрия производства компьютеров и программного обеспечения для них является одной из наиболее важных сфер экономики развитых стран. Ежегодно в мире продаются десятки миллионов компьютеров. Только в США объем продаж компьютеров составляет десятки миллионов долларов и постоянно продолжает расти.
В чем же причины такого стремительного роста индустрии персональных компьютеров и их сравнительная выгодность для многих деловых применений?
Простота использования, обеспеченная с помощью диалогового способа взаимодействия с компьютером.
Относительно высокие возможности по переработке информации, наличие программного обеспечения, а так же мощных систем для разработки нового программного обеспечения.
Использованная в отчёте программа может использоваться для решения задач, связанных с проложением маршрута дороги любого типа.
Определение достижимости населённых пунктов.
1.1 Анализ требований.
В списке задаются города (населённые пункты), а также дороги между ними (есть или нет), необходимо разработать программу с использованием модульного программирования, осуществляющую нахождение кратчайшего пути между населёнными пунктами, задаваемыми пользователем в процессе работы программы.
Решение поставленной задачи осуществляется следующим методом:
Cтроится граф, вершины которого - населённые пункты, а ребра - дороги между ними.
В процессе работы программы в данном графе с помощью рекуррентной процедуры находятся пути из одной вершины в другую. Данная процедура в качестве параметров получает массив пройденных вершин, текущую вершину и количество уже пройденных вершин. На каждом этапе процедура проверяет все, не пройденные достигнутые вершины, и либо находит заданный путь, если достигнута конечная вершина, либо вызывает саму себя для всех, не пройденных вершин.
Для организации данного алгоритма используется две процедуры: процедура нахождения всего пути и рекурсивная процедура поиска единичного маршрута.
Процедура нахождения всего пути осуществляет перебор всех населённых пунктов и вызов рекурсивной процедуры, которая осуществляет поиск маршрута между этими населёнными пунктами.
Средства решения задачи: используются средства логического программирования языка Turbo Pascal 7.0.
1.2 Проектирование.
Для реализации поставленной задачи программа должна выполнять следующие функции:
Ввод данных пользователем с клавиатуры - вводятся названия населённых пунктов и дороги, соединяющие их;
Вывод данных - вывод на экран списка населённых пунктов и дорог, соединяющий их.
Запись в файл - запись в файл, имя которого указывает пользователь в диалоговом режиме, названия населённых пунктов и существующих дорог между ними в виде текстовой информации;
Считывание файла с диска, с именем, которое указывает пользователь в диалоговом режиме
Вывод результата - пользователь задаёт начальный и конечный населённый пункт, между которыми необходимо проложить путь, на экране появляется маршрут, либо сообщение: "маршрут не найден".
Данная программа реализована с использованием принципа модульного программирования, главным преимуществом которого является простота использования, возможность подключения программой разных модулей, которые могли быть разработаны ранее, быстрое нахождение основного текста программы, а также исправление и отладка процедур при использовании другой программы или специальной программы-отладчика, которая подключает к себе данный модуль.
Все процедуры, используемые данной программой, находятся в unit-модуле ph.tpu и предназначены для использования основной программой, которая находится в файле path.pas.
Основная программа осуществляет вывод меню на экран, опрос клавиатуры и вызов процедуры, соответствующей нажатой клавише.
Для реализации ввода данных используется процедура InputData, которая осуществляет ввод имён городов с клавиатуры, если вместо названия города был нажат ввод, то процедура выводит список городов на экран и пользователь, передвигая курсор и, нажимая ввод, составляет список дорог, соединяющие эти города между собой, при нажатии клавиши Esc процедура прекращает свою работу и выходит в главное меню.
Для реализации вывода данных на экран используется процедура OutputData, которая осуществляет чтение в цикле массива городов и вывод его на экран, а также массива дорог, соединяющие эти города и выводит из на экран.
Для реализации запроса имени файла и записи данных в файл используется процедура Save, которая сначала выводит запрос на экран, осуществляет ввод имени файла, открывает файл, имя которого вводится пользователем с клавиатуры в текущем каталоге, в цикле из массива городов записывает на диск список городов, затем также список дорог, соединяющих их.
Для реализации запроса имени файла и чтения данных из файла в массив используется процедура load, которая сначала выводит запрос имени файла на экран, осуществляет ввод имени файла, открывает файл, имя которого вводится пользователем, считывает данные в массив городов, затем в массив дорог.
Для поиска пути между городами используется процедура FindPath, которая осуществляет вывод списка городов на экран, опрос клавиатуры, при этом пользователь может выбрать курсором начальный и конечный населённый пункт в своём пути, процедура FindPath вызывает с параметрами рекурсивную процедуру, которая производит поиск оптимального маршрута между выбранными городами.
Для поиска маршрута используется рекурсивная процедура findnext, которой при её вызове передаются следующие параметры:
a(vec) - вектор, каждому городу соответствует номер в маршруте или ноль, если города нет в маршруте;
tv(integer) - город, следующий в маршруте;
nv(integer) - город, в который необходимо добраться;
lv(integer) - количество пройденных городов.
На каждом этапе процедура проверяет все, не пройденные достигнутые вершины, и либо находит заданный путь, если достигнута конечная вершина, либо вызывает саму себя для всех, не пройденных вершин.
1.3 Кодирование
Краткая функциональная спецификация.
Процедура InputData
Назначение: Осуществляет ввод исходных данных пользователем с клавиатуры.
Входные данные: нет.
Выходные данные: нет.
Не вызывает никаких процедур.
Вызывается из основной программы.
Процедура OutputData
Назначение: Осуществляет вывод данных на экран.
Входные данные: нет.
Выходные данные: нет.
Не вызывает никаких процедур.
Вызывается из основной программы.
Процедура Load
Назначение: Осуществляет запрос имени, чтение файла данных с этим именем в массив городов и в массив дорог.
Входные данные: нет.
Выходные данные: нет.
Не вызывает никаких процедур.
Вызывается из основной программы.
Процедура Save
Назначение: Осуществляет запрос имени, запись в файл данных с этим именем массива городов и в массива дорог.
Входные данные: нет.
Выходные данные: нет.
Не вызывает никаких процедур.
Вызывается из основной программы.
Процедура FindPath
Назначение: Осуществляет поиск пути между городами.
Входные данные: нет.
Выходные данные: нет.
Вызывает findnext.
Вызывается из основной программы.
Процедура FindNext
Назначение: Осуществляет поиск маршрута.
Входные данные:
a(vec) - вектор, каждому городу соответствует номер в
маршруте или ноль, если города нет в маршруте;
tv(integer) - город, следующий в маршруте;
nv(integer) - город, в который необходимо добраться;
lv(integer) - количество пройденных городов.
Выходные данные: нет.
Вызывает findnext.
Вызывается из FindPath.
Основная программа
Осуществляет оформление экрана, вывод и обработку меню, опрос клавиатуры, вызов процедуры, соответствующей выбранному пункту меню.
1.4 Тестирование
Разработанное программное средство было протестировано методом функционального тестирования.
Введённые в программу данные показали, что результаты работы совпадают с вычисленными вручную.
Программы разработки.
Программа path
program path;
uses crt,ph;
var
t:town; {Данные о городах}
nt:integer; {Число городов}
r:road; {Данные о дорогах}
nr:integer; {Число дорог}
sl:integer; {Выбранный пункт меню}
c:char; {Нажатый символ}
i:integer; {Счетчик}
fv:vec; {Вектор пройденных городов}
nfv:integer; {Количество городов}
Const
KItems = 6; {Количество пунктов меню}
mas: array[1..KItems] of string =
{Инициализация пунктов меню}
('¦ Ввод данных ¦',
'¦ Вывод данных ¦',
'¦ Запись в файл ¦',
'¦ Считывание файла ¦',
'¦ Вывод результата ¦',
'L------ Выход -------');
{Основная программа}
begin
sl:=1;
{Городов и дорог нет}
nt:=0;
nr:=0;
repeat
textattr:=7; {Основной цвет меню}
clrscr;
for i:=1 to KItems do begin
gotoxy (25,i+3);
write (mas[i]); {Вывод пунктов меню}
end;
textattr:= 77; {Цвет активного пункта}
gotoxy (25,sl+3);
write (mas[sl]); {Вывод активного пункта}
c:=readkey; {Ввод символа с клавиатуры}
textattr:=7;
case c of {Определить код нажатой клавиши}
#13: case sl of {Клавиша Enter}
1: InputData;
2: OutputData;
3: Save;
4: Load;
5: FindPath;
end;
#0: begin {Анализ функциональных клавиш}
c:=readkey;
case c of
#80:
if sl #72:
if sl>1 then sl:=sl-1 else sl:=KItems; end end end; until
((c=#13) and (sl=6) or (c=#27)); textattr:=7; clrscr; end. Модуль
ph unit
ph; interface uses
crt; type town=
array [1..20] of string; {Данные
о
городах} road=
array [1..200] of record {Данные
о
дорогах} a:integer; b:integer; end; vec=array
[1..20] of integer; {Данные
о пройденных
городах} var t:town;
{Данные
о городах} nt:integer;
{Число городов} r:road;
{Данные
о дорогах} nr:integer;
{Число дорог} fv:vec;
{Вектор
пройденных
городов} nfv:integer;
{Количество
городов} procedure
InputData; procedure
OutputData; procedure
Save; procedure
Load; procedure
findnext(a:vec; tv:integer; nv:integer; lv:integer); procedure
FindPath; implementation {Ввод
данных} procedure
InputData; var i:integer;
{Счетчик} n:integer;
{Выбранный
начальный
город} sl:integer;
{Выбранный
город} c:char;
{Нажатый
символ} begin {Считывание
данных о городах} clrscr; nt:=1; writeln('Введите
название города
(Пустая строка
- закончить:
'); repeat write('
>'); readln(t[nt]); nt:=nt+1; until
(t[nt-1]=''); nt:=nt-2; {Проверка,
вводились ли
города} if
(nt>0) then begin {Да,
ввод
дорог} nr:=0; n:=0; sl:=1; repeat textattr:=7; clrscr; for
i:=1 to nt do begin gotoxy
(25,i+3); write
(t[i]); {Вывод
городов} end; textattr
:= 77; {Цвет активного
города} gotoxy
(25,sl+3); write
(t[sl]); {Вывод
активного
города} if
(n<>0) then begin textattr:=66;
{Цвет отмеченного
города} gotoxy
(25,n+3); write
(t[n]); {Вывод
отмеченного
города} end; textattr:=7; gotoxy(1,20); write('Дороги:
'); for
i:=1 to nr do write(' {',r[i].a,',',r[i].b,'}'); c:=readkey;
{Ввод символа
с клавиатуры} case
c of #13:
begin {Нажат
ENTER} {Либо
помечается
начальный
город} if
n=0 then n:=sl else {Либо
происходит
попытка добавить
дорогу} if
(n=sl) then n:=0 else begin nr:=nr+1; if
(n>sl) then begin i:=n; n:=sl; sl:=i; end;