Смекни!
smekni.com

Нахождение пути от одного населённого пункта к другому (стр. 2 из 2)

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.