Учебная работа. Реферат: Нахождение пути от одного населённого пункта к другому

Учебная работа. Реферат: Нахождение пути от одного населённого пункта к другому

Цель работы:

Введение

В истинное время промышленность производства компов и программного обеспечения для их является одной из более принципиальных сфер экономики продвинутых стран. Раз в год в мире продаются 10-ки миллионов компов. Лишь в США

В чем все-таки предпосылки такового быстрого роста промышленности индивидуальных компов и их сравнительная выгодность для почти всех деловых применений?

* Простота использования, богатая при помощи диалогового метода взаимодействия с компом.

* Относительно высочайшие способности по переработке инфы, наличие программного обеспечения, а так же массивных систем для разработки новейшего программного обеспечения.

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

Определение достижимости населённых пт.

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

{Если найден 1-ый или наиболее маленький маршрут — он становится отысканным}

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);

{Просмотр, но для дорог, где текущий город учитывался как 2-ой}

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

{Вначале 1-ый город не избран}

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; {Ни 1-го пройденного

городка}

findnext(v,n,sl,1);{Вызывается 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.

]]>