Нахождение пути от одного населённого пункта к другому
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
{Вектор пройденных городов}
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&g