Нахождение пути от одного населённого пункта к другому
Цель работы:
Разработать программу, осуществляющую нахождение пути от одного населённого
пункта к другому.
Введение
В настоящее время индустрия производства компьютеров и программного
обеспечения для них является одной из наиболее важных сфер экономики
развитых стран. Ежегодно в мире продаются десятки миллионов компьютеров.
Только в США объем продаж компьютеров составляет десятки миллионов
долларов и постоянно продолжает расти.
В чем же причины такого стремительного роста индустрии персональных
компьютеров и их сравнительная выгодность для многих деловых применений?
Простота использования, обеспеченная с помощью диалогового способа
взаимодействия с компьютером.
Относительно высокие возможности по переработке информации, наличие
программного обеспечения, а так же мощных систем для разработки нового
программного обеспечения.
Использованная в отчёте программа может использоваться для решения
задач, связанных с проложением маршрута дороги любого типа.
Определение достижимости населённых пунктов.
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<KItems then sl:=sl+1 else sl:=1;
#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;
{Проверяется, нет ли такой?}
for i:=1 to nr-1 do
if ((r[i].a=n)and(r[i].b=sl)) then n:=0;
{Если нет - добавляется}
if n<>0 then begin
r[nr].a:=n;
r[nr].b:=sl;
end else nr:=nr-1;
n:=0;
sl:=1;
end;
end;
#0: begin {Анализ функциональных клавиш}
c:=readkey;
case c of
#80: if sl<nt then sl:=sl+1 else sl:=1;
#72: if sl>1 then sl:=sl-1 else sl:=nt;
end
end
end;
until (c=#27);
end;
end;
{Вывод данных}
procedure OutputData;
var
i:integer; {Счетчик}
begin
{Вывод списка городов}
clrscr;
writeln(' Города: ');
for i:=1 to nt do begin
gotoxy (10,i);
write (t[i]); {Вывод городов}
end;
{Вывод списка дорог}
gotoxy(1,20);
write(' Дороги: ');
for i:=1 to nr do write(' {',r[i].a,',',r[i].b,'}');
gotoxy(2,24);
write(' ESC- Выход');
{Ожидание ESC}
repeat until readkey=#27;
end;
{ Запись данных в файл}
procedure Save;
var
f:TEXT; {Файл}
name:string; {Имя файла}
n:integer; {Счетчик}
begin
clrscr;
writeln(' Запись данных ');
write(' Введите имя файла: ');
readln(name);
assign(f,name);
rewrite(f);
writeln(f,nt);
for n:=1 to nt do writeln(f,t[n]);
writeln(f,nr);
for n:=1 to nr do writeln(f,r[n].a,' ',r[n].b);
close(f);
end;
{Чтение из файла}
procedure Load;
var
f:TEXT; {Файл}
name:string; {Имя файла}
n:integer; {Счетчик}
begin
clrscr;
writeln(' Чтение данных ');
write(' Введите имя файла: ');
readln(name);
assign(f,name);
reset(f);
readln(f,nt);
for n:=1 to nt do readln(f,t[n]);
readln(f,nr);
for n:=1 to nr do readln(f,r[n].a,r[n].b);
close(f);
end;
{Рекурсивная процедура поиска маршрута.
Входные параметры:
a:vec - Вектор, каждому городу соответствует номер в маршруте
или ноль, если города нет в маршруте
tv:integer - Город, следующий в маршруте
nv:integer - Город, в который необходимо добраться
lv:integer - Количество пройденных городов}
procedure findnext(a:vec;tv:integer;nv:integer;lv:integer);
var
i:integer; {Счетчик}
begin
a[tv]:=lv; {Устанавливается в векторе
флаг, что город tv пройден}
if (tv=nv) then begin
{Если достигнут необходимый город}
if ((lv+1)<nfv)or(nfv=0) then begin
{Если найден первый либо более короткий маршрут - он становится найденным}
nfv:=lv+1;
fv:=a;
end;
end else begin
{Иначе - просмотр всех городов, в которые можно добраться из данного}
for i:=1 to nr do
{Если город еще не учитывался - запуск для него той же самой функции}
if ((r[i].a=tv)and(a[r[i].b]=0)) then findnext(a,r[i].b,nv,lv+1);
{Просмотр, но для дорог, где текущий город учитывался как второй}
for i:=1 to nr do
{Если город еще не учитывался - запуск для него той же самой функции}
if ((r[i].b=tv)and(a[r[i].a]=0)) then findnext(a,r[i].a,nv,lv+1);
end;
end;
{Нахождение пути}
procedure FindPath;
var
i:integer; {Счетчик}
j:integer; {Счетчик}
n:integer; {Исходный город}
sl:integer; {Выбираемый город}
c:char; {Считанный с клавиатуры символ}
v:vec; {Вектор для начала рекурсии}
begin
{Изначально первый город не выбран}
n:=0;
sl:=1;
nfv:=0; {Маршрут не найден}
{Цикл запроса городов и вывода результатов}
repeat
textattr:=7;
clrscr;
{Вывод поясняющей надписи}
gotoxy(2,20);
if (n=0) then write(' Выберите начальный пункт')
else writeln(' Выберите конечный пункт ');
{Вывод списка городов}
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(60,1);
if (nfv>0) then begin
write(' Найденный маршрут: ');
for j:=1 to nfv do
for i:=1 to nt do if fv[i]=j then begin
gotoxy(60,j+2);
write(t[i]);
end;
end else write(' Маршрут не найден ');
c:=readkey; {Ввод символа с клавиатуры}
case c of
#13: begin
{Либо фиксируется начальный город}
if n=0 then n:=sl else begin
{Либо убирается ошибочно выбранный город}
if (n=sl) then n:=0 else begin
{Либо происходит поиск нового маршрута}
nfv:=0; {Маршрута нет}
for i:=1 to 20 do v[i]:=0; {Ни одного пройденного
города}
findnext(v,n,sl,1);{Вызывается первый раз рекурсивная
процедура}
end;
n:=0;
sl:=1;
end;
end;
#0: begin {Анализ функциональных клавиш}
c:=readkey;
case c of
#80: if sl<nt then sl:=sl+1 else sl:=1;
#72: if sl>1 then sl:=sl-1 else sl:=nt;
end
end
end;
until (c=#27);
end;
end.
Результаты выполнения программы.
¦ Ввод данных ¦
¦ Вывод данных ¦
¦ Запись в файл ¦
¦ Считывание файла ¦
¦ Вывод результата ¦
+------ Выход ------+
Ввод данных:
Введите название города (Пустая строка - закончить):
>Город 1
>Город 2
>Город 3
>Город 4
>Город 5
>
Дороги: {1,3} {3,4} {2,5} {1,4} {2,4} {2,3}
Вывод результата:
Найденный маршрут:
Город 1 Город 1
Город 3 Город 2
Город 2 Город 3
Город 5 Город 4
Город 5
Список используемых источников
1. Белецкий Я. Турбо Паскаль с графикой для персональных компьютеров
/перевод с польского Д. И. Юренкова. - М. :Машиностроение, 1991.
2. Сергиевский М. В., Шалашов А. В. Турбо Паскаль 7.0; язык, среда
программирования. - М: Машиностроение, 1994.
3. Справочник по процедурам и функциям Borland Pascal With Objects 7.0. -
Киев: Диалектика, 1993.